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$.
Train for Math Olympiads
Learn moreTheorem 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}$.
