Mathematical Methods for Physics and Engineering : A Comprehensive Guide

(Darren Dugan) #1

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].

Free download pdf