Mathematical Methods for Physics and Engineering : A Comprehensive Guide

1.7 SOME PARTICULAR METHODS OF PROOF

1.7.1 Proof by induction

The proof of the binomial expansion given in subsection 1.5.2 and the identity

established in subsection 1.6.1 have already shown the way in which an inductive

proof is carried through. They also indicated the main limitation of the method,

namely that only an initially supposed result can be proved. Thus the method

of induction is of no use fordeducinga previously unknown result; a putative

equation or result has to be arrived at by some other means, usually by noticing

patterns or by trial and error using simple values of the variables involved. It

will also be clear that propositions that can be proved by induction are limited

to those containing a parameter that takes a range of integer values (usually

infinite).

For a proposition involving a parametern, the five steps in a proof using

induction are as follows.

(i) Formulate the supposed result for generaln.

(ii) Suppose (i) to be true forn=N(or more generally for all values of

n≤N;seebelow),whereNis restricted to lie in the stated range.

(iii) Show, using only proven results and supposition (ii), that proposition (i)

is true forn=N+1.

(iv) Demonstrate directly, and without any assumptions, that proposition (i) is

true whenntakes the lowest value in its range.

(v) It then follows from (iii) and (iv) that the proposition is valid for all values

ofnin the stated range.

(It should be noted that, although many proofs at stage (iii) require the validity

of the proposition only forn=N, some require it for allnless than or equal toN

• hence the form of inequality given in parentheses in the stage (ii) assumption.)

To illustrate further the method of induction, we now apply it to two worked

examples; the first concerns the sum of the squares of the firstnnatural numbers.

Prove that the sum of the squares of the firstnnatural numbers is given by

∑n

r=1

r^2 =^16 n(n+ 1)(2n+1). (1.60)

As previously we start by assuming the result is true forn=N. Then it follows that

N∑+1

r=1

r^2 =

∑N

r=1

r^2 +(N+1)^2

=^16 N(N+ 1)(2N+1)+(N+1)^2

=^16 (N+1)[N(2N+1)+6N+6]

=^16 (N+ 1)[(2N+3)(N+2)]

=^16 (N+1)[(N+1)+1][2(N+1)+1].