Mathematical Writing - Vivaldi Franco 2014

Good Manners with Induction Proofs
Induction

Induction proofs are easy to structure, as there is a clear procedure to follow. But even if the steps in a proof are predictable, they should be spelled out clearly.

1. At the beginning of the proof, say with respect to what variable induction is performed, unless this is obvious.

We proceed by induction on the degree of the polynomial.

2. If the induction variable is , then in the inductive step it is considered good practice to go from to rather than from to .

3. In the inductive step, say at what point the induction hypothesis is used.

...where the last inequality follows from the induction hypothesis.

4. Say when the inductive step is complete.

This completes the induction.

If an induction argument is easy, then it may be tempting to skip it altogether.

Let , and let $x_{n+1}=x_n^2 , \,\,$ for $n\geqslant 1$ . Then $x_n=2^{2^{n-1}}$ .

The last sentence is a bit blunt, and it could be replaced by more considerate sentences, such as:

A straightforward induction argument shows that $x_n=2^{2^{n-1}}$ .

Then , $x_3=2^{2^2}$ , and, in general, $x_n=2^{2^{n-1}}$ .

Exercise 8.1

Prove the following formulae by induction, first analytically, then with a computer-assisted proof.

$\begin{aligned} 1.&\sum _{k=1}^n(2k-1)=n^2\\ 2.&\sum _{k=1}^n k!\cdot k=(n+1)!-1\\ 3.&\sum _{k=1}^nk^3=\left( \sum _{k=1}^n k\right) ^2\\ 4.&\sum _{k=1}^n \frac{1}{k(k+1)}=\frac{n}{n+1}\\ 5.&\sum _{k=2}^n\frac{1}{k^2-1}=\frac{3}{4}-\frac{2n+1}{2n(n+1)}\\ 6.&\prod _{k=0}^{n-1}(1+x^{2^k})={\frac{1-x^{2^n}}{1-x}}\qquad {x\not =1}. \end{aligned}$

Exercise 8.2

Prove by induction all identities and inequalities listed at the beginning of this chapter. (The Bernoulli inequality is proved in Sect. 8.3.)

Exercise 8.3

Prove the following statements by induction.

Exercise 8.4

Find each formula, and then prove it by induction.

Exercise 8.5

Identify the flaw in the proof of the following false statements.

1. WRONG THEOREM. For any natural number , the following holds:

$2+4+\cdots +2n=(n-1)(n+2).$

WRONG PROOF. Assume that $2+4+\cdots +2k=(k-1)(k+2)$ for some $k\in \mathbb {N}$ . Then

$\begin{aligned} 2+4+\cdots +2(k+1)&= (2+4+\cdots +2k) + 2(k+1)\\&= (k-1)(k+2)+ 2(k+1)\;\;\text {(by the induction hypothesis)}\\&= k(k+3) = ((k+1)-1))((k+1)+2) \end{aligned}$

which completes the induction. $\square$

2. WRONG THEOREM. For any $n\in \mathbb {N}$ , if $\max (i,j)=n$ for two natural numbers and , then . Thus any two natural numbers are equal.

WRONG PROOF. The statement is true for : if $\max (i,j)=1$ , then, necessarily, . Now assume the statement to be true for some $k\geqslant 1$ , and let be natural numbers such that $\max (i,j)=k+1$ . Then $\max (i-1,j-1)=k$ , and by the induction hypothesis, we have that . But then , and therefore our statement is true for . This completes the induction. $\square$

3. WRONG THEOREM. (Pólya⁸) In any group of horses, all horses have the same colour.

WRONG PROOF. The statement is clearly true for . Assume now that the statement is true for some $n=k\geqslant 1$ , and consider an arbitrary collection of horses.