6.3: Proof by mathematical induction II

Even where there is no confusion between mathematical induction and ‘scientific induction', students often fail to appreciate the essence of “proof by induction”. Before illustrating this, we repeat the basic structure of such a proof.

A mathematical result, or formula, often involves a parameter n, where n can be any positive integer. In such cases, what is presented as a single result, or formula, is a short way of writing an infinite family of results. The proof that such a result is correct therefore requires us to prove infinitely many results at once. We repeat that our only hope of achieving such a mind–boggling feat is

• to formulate the stated result for each value of n separately: that is, as a statement P(n) which depends on n;
• then to use bare hands to check the “beginning” – namely that the simplest case (usually P(1)) is true;
• finally to find some way of demonstrating that,

– as soon as we know that P(k) is true, for some (unknown) $k\ge 1$,

– we can prove that the next result $\mathbf{P}(k+1)$ is then automatically true

We can then conclude that

“every statement P(n) is true”,

or that

“P(n) is true, for all $n\ge 1$”

Problem 229 Prove the statement:

“5²ⁿ⁺² – 24n – 25 is divisible by 576, for all $\mathit{n}⩾1$”.

When trying to construct proofs in private, one is free to write anything that helps as ‘rough work'. But the intended thrust of Problem 229 is two–fold:

• to introduce the habit of distinguishing clearly between

  (i) the statement P(n) for a particular n, and

  (ii) the statement to be proved – namely “P(n) is true, for all $n\ge 1$”; and

• to draw attention to the “induction step” (i.e. the third bullet point above), where

  (i) we assume that some unspecified P(k) is known to be true, and

  (ii) seek to prove that the next statement $\mathbf{P}(k+1)$ must then be true.

The central lesson in completing the “induction step” is to recognize that:

to prove that $\mathbf{P}(k+1)$ is true, one has to start by looking at what $\mathbf{P}(k+1)$ says.

In Problem 229 $\mathbf{P}(k+1)$ says that

“$5^{2(k+1)+2}-24(k+1)-25$ is divisible by 576”.

Hence one has to start the induction step with the relevant expression

$$\begin{array}{cc}& 5^{2(k+1)+2}-24(k+1)-25,\hfill \end{array}$$

and look for some way to rearrange this into a form where one can use P(k) (which we assume is already known to be true, and so are free to use).

It is in general a false strategy to work the other way round – by “starting with P(k), and then fiddling with it to try to get $\mathbf{P}(k+1)$”. (This strategy can be made to work in the simplest cases; but it does not work in general, and so is a bad habit to get into.) So the induction step should always start with the hypothesis of $\mathbf{P}(k+1)$.

The next problem invites you to prove the formula for the sum of the angles in any polygon. The result is well–known; yet we are fairly sure that the reader will never have seen a correct proof. So the intention here is for you to recognise the basic character of the result, to identify the flaws in what you may until now have accepted as a proof, and to try to find some way of producing a general proof.

Problem 230 Prove by induction the statement:

“for each $n\ge 3$, the angles of any n–gon in the plane have sum equal to $(n-2)\pi$ radians.”

The formulation certainly involves a parameter $n\ge 3$; so you clearly need to begin by formulating the statement P(n). For the proof to have a chance of working, finding the right formulation involves a modest twist! So if you get stuck, it may be worth checking the first couple of lines of the solution.

No matter how P(n) is formulated, you should certainly know how to prove the statement P(3) (essentially the formula for the sum of the angles in a triangle). But it is far from obvious how to prove the “induction step”:

“if we know that P(k) is true for some particular $k\ge 1$, then $\mathbf{P}(k+1)$ must also be true”.

When tackling the induction step, we certainly cannot start with P(k)! The statement $\mathbf{P}(k+1)$ says something about polygons with $k+1$ sides: and there is no way to obtain a typical $(k+1)$–gon by fiddling with some statement about polygons with k sides. (If you start with a k–gon, you can of course draw a triangle on one side to get a $(k+1)$–gon; but this is a very special construction, and there is no easy way of knowing whether all $(k+1)$–gons can be obtained in this way from some k–gon.) The whole thrust of mathematical induction is that we must always start the induction step by thinking about the hypothesis of $\mathbf{P}(k+1)$ – that is in this case, by considering an arbitrary $(k+1)$–gon and then finding some guaranteed way of “reducing” it in order to make use of P(k).

The next two problems invite you to prove some classical algebraic identities. Most of these may be familiar. The challenge here is to think carefully about the way you lay out your induction proof, to learn from the examples above, and (later) to learn from the detailed solutions provided.

Problem 231 Prove by induction the statement:

“$1+3+5+\cdots +(2\mathit{n}-1)={\mathit{n}}^2$ holds, for all $\mathit{n}⩾1$”

The summation in Problem 231 was known to the ancient Greeks. The mystical Pythagorean tradition (which flourished in the centuries after Pythagoras) explored the character of integers through the ‘spatial figures’ which they formed. For example, if we arrange each successive integer as a new line of dots in the plane, then the sum “$1+2+3+\cdots +\mathit{n}$” can be seen to represent a triangular number. Similarly, if we arrange each odd number $2\mathit{k}-1$ in the sum “$1+2+3+\cdots +\mathit{n}$” as a “k-by-k reverse L-shape”, or gnomon (a word which we still use to refer to the L-shaped piece that casts the shadow on a sundial), then the accumulated L-shapes build up an n by n square of dots - the “1” being the dot in the top left hand corner, the “3” being the reverse L-shape of 3 dots which make this initial “1” into a 2 by 2 square, the “5” being the reverse L-shape of 5 dots which makes this 2 by 2 square into a 3 by 3 square, and so on. Hence the sum “$1+3+5+...+(2\mathit{n}-1)$” can be seen to represent a square number.

There is much to be said for such geometrical illustrations; but there is no escape from the fact that they hide behind an ellipsis (the three dots which we inserted in the sum between “5” and “$2\mathit{n}-1$”, which were then summarised when arranging the reverse L-shapes by ending with the words “and so on”). Proof by mathematical induction, and its application in Problem 231, constitute a formal way of avoiding both the appeal to pictures, and the hidden ellipsis.

Problem 232 The sequence

$2,5,13,35,\dots$

is defined by its first two terms ${\mathit{u}}_0=2,{\mathit{u}}_1=5$, and by the recurrence relation:

${\mathit{u}}_{\mathit{n}+2}=$5un+1−6un.

(a) Guess a closed formula for the n^th term u_n.

(b) Prove by induction that your guess in (a) is correct for all $$n⩾0.

Problem 233 The sequence of Fibonacci numbers

$0,1,1,2,3,5,8,13,\dots$

is defined by its first two terms ${\mathit{F}}_0=0,{\mathit{F}}_1=1$, and by the recurrence relation:

${\mathit{F}}_{\mathit{n}+2}={\mathit{F}}_{\mathit{n}+1}+{\mathit{F}}_{\mathit{n}}$ when $$n⩾0.

Prove by induction that, for all $$n⩾0,

${\mathit{F}}_{\mathit{n}}=\frac{{\alpha }^{\mathit{n}}-{\beta }^{\mathit{n}}}{\sqrt{5}},$whereα=1+52andβ=1−52

Problem 234 Prove by induction that

${}^{}$52n+1·2n+2+3n+2·22n+1

is divisible by 19, for all $$n⩾0.

Problem 235 Use mathematical induction to prove that each of these identities holds, for all $$n⩾1:

(a) $1+2+3+\cdots +\mathit{n}=\frac{\mathit{n}(\mathit{n}+1)}{2}$

(b) $\frac{1}{1·2}+\frac{1}{2·3}+\frac{1}{3·4}+\cdots +\frac{1}{\mathit{n}(\mathit{n}+1)}=1-\frac{1}{\mathit{n}+1}$

(c) $1+\mathit{q}+{\mathit{q}}^2+{\mathit{q}}^3+\cdots +{\mathit{q}}^{\mathit{n}-1}=\frac{1}{1-\mathit{q}}-\frac{{\mathit{q}}^{\mathit{n}}}{1-\mathit{q}}$

(d) $0·0!+1·1!+2·2!+\cdots +(\mathit{n}-1)·(\mathit{n}-1)!=\mathit{n}!-1$

(e) $($cosθ+isinθ)n=cosnθ+isinnθ.

Problem 236 Prove by induction the statement:

“$(1+2+3+\cdots +\mathit{n}{)}^2=1^3+2^3+3^3+\cdots +{\mathit{n}}^3$, for all $\mathit{n}⩾1$”.

We now know that, for all $$n⩾1:

$1+1+1+\cdots +1($nterms)=n.

And if we sum these “outputs” (that is, the first n natural numbers), we get the n^th triangular number:

$1+2+3+\cdots +\mathit{n}=\frac{\mathit{n}(\mathit{n}+1)}{2}={\mathit{T}}_{\mathit{n}}$.

The next problem invites you to find the sum of these “outputs”: that is, to find the sum of the first n triangular numbers.

Problem 237

(a) Experiment and guess a formula for the sum of the first n triangular numbers:

${\mathit{T}}_1+{\mathit{T}}_2+{\mathit{T}}_3+\cdots +{\mathit{T}}_{\mathit{n}}=1+3+6+\cdots +\frac{\mathit{n}(\mathit{n}+1)}{2}.$

(b) Prove by induction that your guessed formula is correct for all $$n⩾1.

A We now know closed formulae for

“$1+2+3+\cdots +\mathit{n}$”

and for

“$1·2+2·3+3·4+\cdots +(\mathit{n}-1)\mathit{n}$”.

The next problem hints firstly that these identities are part of something more general, and secondly that these results allow us to find identities for the sum of the first n squares:

$1^2+2^2+3^2+\cdots +{\mathit{n}}^2$

for the first n cubes:

$1^3+2^3+3^3+\cdots +{\mathit{n}}^3$

and so on.

Problem 238

(a) Note that$\mathrm{}$

$1·2+2·3+3·4+\cdots +\mathit{n}(\mathit{n}+1)=1·(1+1)+2·(2+1)+3·(3+1)+\cdots +\mathit{n}·(\mathit{n}+1)$.

Use this and the result of Problem 237 to derive a formula for the sum:${\mathrm{}}^{}$

$1^2+2^2+3^2+\cdots +{\mathit{n}}^2$.

(b) Guess and prove a formula for the sum

$1·2·3+2·3·4+3·4·5+\cdots +(\mathit{n}-2)(\mathit{n}-1)\mathit{n}$.

Use this to derive a closed formula for the sum:

$1^3+2^3+3^3+\cdots +{\mathit{n}}^3$.

It may take a bit of effort to digest the statement in the next problem. It extends the idea behind the “method of undetermined coefficients” that is discussed in Note 2 to the solution of Problem 237(a).

Problem 239

(a) Given $\mathit{n}+1$ distinct real numbers

${\mathit{a}}_0,{\mathit{a}}_1,{\mathit{a}}_2\mathrm{,...,}{\mathit{a}}_{\mathit{n}}$

find all possible polynomials of degree n which satisfy

$$fa0=fa1=fa2=⋯=fan−1=0,fan=b

for some specified number b.

(b) For each $$n⩾1, prove the following statement:

Given two labelled sets of $\mathit{n}+1$ real numbers

${\mathit{a}}_0,{\mathit{a}}_1,{\mathit{a}}_2\mathrm{,...},{\mathit{a}}_{\mathit{n}}$,

and

${\mathit{b}}_0,{\mathit{b}}_1,{\mathit{b}}_2,\dots ,{\mathit{b}}_{\mathit{n}}$,

where the a_i are all distinct (but the b need not be), there exists a polynomial f_n of degree n, such that

$$fna0=b0,fna1=b1,fna2=b2,…,fnan=bn.

We end this subsection with a mixed bag of three rather different induction problems. In the first problem the induction step involves a simple construction of a kind we will meet later.

Problem 240 A country has only 3 cent and 4 cent coins.

(a) Experiment to decide what seems to be the largest amount, N cents, that cannot be paid directly (without receiving change).

(b) Prove by induction that “n cents can be paid directly for each $\mathit{n}>\mathit{N}$”.

Problem 241

(a) Solve the equation $\mathit{z}+\frac{1}{\mathit{z}}=1$. Calculate ${\mathit{z}}^2$, and check that ${\mathit{z}}^2+\frac{}{}$1z2 is also an integer.

(b) Solve the equation $\mathit{z}+\frac{1}{\mathit{z}}=2$. Calculate ${\mathit{z}}^2+\frac{}{}$1z2, and check that ${\mathit{z}}^2+\frac{}{}$1z2 is also an integer.

(c) Solve the equation $\mathit{z}+\frac{1}{\mathit{z}}=3$. Calculate ${\mathit{z}}^2+\frac{}{}$1z2, and check that ${\mathit{z}}^2+\frac{}{}$1z2 is also an integer.

(d) Solve the equation $\mathit{z}+\frac{1}{\mathit{z}}=\mathit{k}$, where k is an integer. Calculate z², and check that ${\mathit{z}}^2+\frac{}{}$1z2 is also an integer.

(e) Prove that if a number z has the property that $z+\frac{1}{z}$ is an integer, then ${\mathit{z}}^{\mathit{n}}+\frac{}{}$1zn is also an integer for each $$n⩾1.

Problem 242 Let p be any prime number. Use induction to prove:

“${\mathit{n}}^{\mathit{p}}-\mathit{n}$ is divisible by p for all $\mathit{n}⩾1$”.