Lesson 2

The code above checks that the formula is true only for \(n<1000\). This still does not rule out the possibility that for some \(n \ge 1000\), the formula will fail. And we have already seen examples where such a check is misleading: for small \(n\), the greatest common divisor of the numbers \(n^{17}+9\) and \((n+1)^{17}+9\) is one. This property fails for the first time only at \[n=8424432925592889329288197322308900672459420460792433 \ .\] Finding such a number by brute force is simply impossible.

In any case, such a check on a computer can convince us that the formula is true only for some values of \(n\). This is somewhat reminiscent of software testing: when we test a program, it is almost always impossible to do so on all possible tests because their number is enormous. In our case, it is even more difficult: there are infinitely many positive integers! Therefore, to prove that a certain formula is true for all \(n\), we need a mathematical method.

This is where the method of mathematical induction comes to the rescue. With its help, we can prove statements of the following kind:

\(A(n)\) holds for all positive integers \(n\).

• \(1+3+5+\dotsb+(2n-1)=n^{2}\);


• \((1+x)^{n} \ge 1+xn\), for every \(x \in \mathbb{R}_{\ge 1}\);


• any triangulation of a convex \(n\)-gon consists of \((n-2)\) triangles.

The method consists of two steps:

• Base case (\(n=1\)).  Prove that \(A(1)\) holds.


• Inductive step (\(n \to n+1\)).  Fix \(n\ge1\) and prove that \(A(n+1)\) holds, assuming that \(A(n)\) holds. The statement that \(A(n)\) holds is called the induction hypothesis.

The domino effect clearly explains how these two steps are used. Imagine an infinite sequence of dominoes standing in a row. We know that if we push the first domino, all the dominoes will eventually fall. And this is true precisely by the principle of mathematical induction! Indeed, let \(A(n)\) be the statement "domino \(n\) will fall." Then we have the base case (\(A(1)\) is true because the first domino is pushed) and the inductive step (we know that if domino \(n\) falls, then domino \(n+1\) will also fall).

Let's show how to use the method of mathematical induction to prove the formula \[1+3+5+\dotsb+(2n-1)=n^{2}\] for all integers \(n \ge 1\).

• Base case \(n=1\).  For \(n=1\), the formula is true: \(1=1^{2}\).


• Inductive step \(n \to n+1\).  Suppose the formula is true for some \(n\ge1\). We will prove that it is also true for \((n+1)\). To do this, we express the sum of the first \(n+1\) odd numbers through the sum of the first \(n\) odd numbers and apply the induction hypothesis. \[\begin{align*}1+\dotsb+(2n-1)+(2n+1)&=\left(1+\dotsb+(2n-1)\right)+(2n+1)&\text{(regroup)}\\&=n^{2}+(2n+1)&\text{(hypothesis)}\\&=(n+1)^{2}.\end{align*}\]