Mathematical Induction: Combinatorics

Mathematical Induction is used to prove that the statement of the problem $P(n)$ is true for all natural numbers $n$. Mathematical Induction consists of proving the following three theorems.

Theorem 1 (Base of Induction): The statement of the problem is true for $n = 1$.

Theorem 2 (Inductive Step): If the statement is true for some $n = k$, then it must also be true for $n = k + 1$.

Theorem 3 (Peano Axiom): If Theorems 1 and 2 hold, then the statement of the problem is true for all natural numbers $n$.

 

Problem (Singapore, 2010)

Numbers $1$, $2$, …, $n$ are placed on the circumference in some order. Distinct numbers $i$ and $j$, form a friendly pair if they are not neighbors and on one or both of the arcs connecting $i$ and $j$, all numbers in between them are greater than both $i$ and $j$. Determine the minimal number of friendly pairs.

Solution

Answer: $n-3$.

Theorem 1 (Base of Induction): The statement of the problem is obviously true for $n = 3$.

 

Theorem 2 (Inductive Step): Let us assume that the statement holds for $n = k$ and prove that it will hold for $n=k+1$.

Consider the induction by the total number of numbers $n$ and show that there are $n-3$ such pairs. Consider the largest number and delete it.

By the inductive hypothesis

Theorem 3 (Peano Axiom): Since Theorems 1 and 2 hold, then the inequality is true for all $n \in \mathbb{N}$.

---