[PDF] Proof by Induction - University of Plymouth

View - Download Proof by Induction - University of Plymouth

Previous PDF

Next PDF

Intermediate Mathematics

Proof by Induction

R Horan & M LavelleTheaim of this package is to provide a short self assessment programme for students who want to understand the method of proof by induction.Copyright

Last Revision Date: February 12, 2006Version 1.0

Table of Contents

1.Introduction (Summation)

2.The Principle of Induction

3.Further Examples

4.Final Quiz

Solutions to Exercises

Solutions to Quizzes

The full range of these packages and some instructions, should they be required, can be obtained from our web pageMathematics Support Materials.

Section 1: Introduction (Summation) 3

1. Introduction (Summation)

Proof by induction involves statements which depend on the natural numbers,n= 1,2,3,.... It often usessummation notationwhich we now briefly review before discussing induction itself. We write the sum of the natural numbers up to a valuenas:

1 + 2 + 3 +···+ (n-1) +n=n?

i=1i.The symbol?denotes a sum over its argument for each natural numberifrom the lowest value, herei= 1, to the maximum value, herei=n. Example 1:Write out explicitly the following sums: a)6 i=3i,b)3 i=1(2i+ 1),c)4 i=12 i.

Section 1: Introduction (Summation) 4

The above sums when written out are:

a)6 i=3i= 3 + 4 + 5 + 6,b)3 i=1(2i+ 1) = (2×1 + 1) + (2×2 + 1) + (2×3 + 1) = 3 + 5 + 7,c)4 i=12 i= 21+ 22+ 23+ 24.It is important to realise that the choice of symbol for the variable we are summing over is arbitrary, e.g., the following two sums are identical:4 i=1i 3=4? j=1j

3= 13+ 23+ 33+ 43.The variable that is summed over is called adummy variable.

Section 1: Introduction (Summation) 5

QuizSelect from the answers below the value of5

i=22 i. (a)1024,(b)62,(c)60,(d)32.Exercise 1.Expand the sums(click on thegreenletters for solutions): (a)3 i=1(2i-1),(b)4 j=1(2j-1),(c)4 s=110 s,(d)3 j=112j ,(e)3 i=03(2i+ 1),(f)3 j=11j

2.Exercise 2.Express the following in summation notation.

(a)1 + 20 + 400 + 8,000,(b)-3-1 + 1 + 3 + 5 + 7.Hint:write a) as a sum of powers of20.

Section 2: The Principle of Induction 6

2. The Principle of Induction

Induction is an extremely powerful method of proving results in many

areas of mathematics. It is based upon the following principle.The Induction Principle:letP(n)be a statement which involves

a natural numbern, i.e.,n= 1,2,3..., thenP(n)is true for allnif a)P(1)is true, and b)P(k)?P(k+ 1)for all natural numbersk. The standardanalogyto this involves a row of dominoes: if it is shown that toppling one domino will make the next fall over (step b) and that the first domino has fallen (step a) then it follows that all of the dominoes in the row will fall over.Example 2:the result of adding the firstnnatural numbers is:

1 + 2 + 3 +···+n=n(n+ 1)2

;i.e.,P(n)isn i=1i=n(n+ 1)2 .This is proven on the next page.

Section 2: The Principle of Induction 7

Stepa)(the check): forn= 1,?

1 i=1i= 1 =1×22.? Stepb)(the induction step): assume the result is true forn=k, i.e., assumek i=1i=k(k+ 1)2 .The sum forn=k+ 1may be written k+1? i=1i=k? i=1i+ (k+ 1).Using the assumption this becomes k+1? i=1i=k(k+ 1)2 + (k+ 1) k(k+ 1) + 2(k+ 1)2 =(k+ 1)(k+ 2)2 which is the desired result forn=k+ 1.

Section 2: The Principle of Induction 8

It is always worth making the check, stepa), first. If it does not work

one knows that the result must be wrong and saves time.Example 3:the result of adding the odd natural numbers is:

1 = 1,

1 + 3 = 4,

1 + 3 + 5 = 9,

1 + 3 + 5 + 7 = 16,

1 + 3 + 5 + 7 + 9 = 25.This seems to indicate that

n j=1(2j-1) =n2.We will now use induction to prove this result. Stepa)(the check): we have already seen the initial step of the proof, i.e., forn= 1,? 1 j=1(2j-1) = 1 = 12.?

Section 2: The Principle of Induction 9

Stepb)(the inductive step): weassumeit is true forn=k, i.e., assumek j=1(2j-1) =k2.and need toshowthat it follows that? k+1 j=1(2j-1) = (k+ 1)2. Write this sum (overk+1terms) as a sum over the firstktermsplus the final term (wherej=k+ 1) k+1? j=1(2j-1)= k? j=1(2j-1) + (2×(k+ 1)-1) =k2+ (2(k+ 1)-1)from the assumption =k2+ 2k+ 1 = (k+ 1)2.? This completes stepb)and by thePrinciple of Inductionwe have proven the result.

Section 2: The Principle of Induction 10

Exercise 3.Use thePrinciple of Inductionto prove the following results. Unless stated otherwise assumenis a natural number. (Click on thegreenletters for the solutions.) (a)n i=1i

2=n(n+ 1)(2n+ 1)6

,(b)n j=1j

3=n2(n+ 1)24

,(c)n j=12 j-1= 2n-1,(d)n j=0x j=1-xn+11-x,forx?= 1and integersn≥0. Hint:in the last exercise the check must be performed forn= 0. Induction can also be used to prove a great many other results. The next section treats some further applications.

Section 3: Further Examples 11

3. Further Examples

Example 3:forna natural number prove that:

1)ifn≥2,thenn

3-nis always divisible by3,2)n <2n.1)If a number is divisible by3it can be written as3rfor integerr

Stepa)(check): forn= 2,2

3-2 = 6 = 3×2; so divisible by3.?

Stepb)(induction step): assume that it is true forn=k, i.e.,assume thatk

3-k= 3r. Forn=k+ 1we have:

(k+ 1)3-(k+ 1) =k3+ 3k2+ 3k+ 1-(k+ 1) = (k3-k) + 3k2+ 3k = 3r+ 3k2+ 3kusing the assumption = 3(r+k2+k).?

The Principle of Induction thus implies thatn

3-nis indeed divisible

by3for alln≥2.

Section 3: Further Examples 12

2)Show by induction thatn <2nfor all natural numbersn.

Stepa)(check): forn= 1, since2

1= 2, it is true that1<21.?

Stepb)(induction step): assume it is true forn=k, i.e.,k <2k. Thenk+ 1<2k+ 1,since 1<2kfor any natural numberkand this implies that k+ 1<2k+ 2k= 2×2k= 2k+1Hencek+ 1<2k+1.? From the Principle of Induction,n <2nfor any natural numbern. QuizWhich of the following properties isnotnecessary for a natural numbernto be divisible by10? (a)10dividesn

2,(b)20divides4n,

(c)5dividesn/2,(d)100divides2n.

Section 3: Further Examples 13

Exercise 4.Use thePrinciple of Inductionto prove the following results. Assumenis a natural number. (Click on thegreenletters for the solutions.)(a)5 n-1is divisible by4,(b)9 n+ 3 is divisible by4,(c)3 n> n2,(d)? n j=11j .Exercise 5.Consider the following sequence of sums: 1

1×2;11×2+12×3;11×2+12×3+13×4;...(a)Calculate the sums and guess the general pattern.

(b)Prove your conjecture usingproof by induction.

Section 4: Final Quiz 14

4. Final Quiz

Begin Quiz

1.Select the sum which isnotequivalent to?

15 i=125i. (a)25 15? i=1i,(b)15 j=125j ,(c)75 i=15i,(d)5 15? j=15j .2.Select the expression below which is meaningless: (a)n j=1j j,(b)i i=12i,(c)n n? i=1i n,(d)2n? i=ni.3.In a proof by induction that6 n-1is divisible by5, which result may occur in the inductive step (let6 k-1 = 5r)? (N.B. you may need to re-arrange your equation.)(a)6 k+1-1 = 5(6r-1),(b)6 k+1-1 = 6(5r+ 1),(c)6 k+1-1 = 5(6r+ 1),(d)6 k+1-1 = 5×6r+ 7.End Quiz

Solutions to Exercises 15

Solutions to Exercises

Exercise 1(a)The sum3

i=1(2i-1)may be written as 3 i=1(2i-1) = (2×1-1) + (2×2-1) + (2×3-1) = 1 + 3 + 5 = 9.One sees that the sequence2i-1, whereiis an integer, generates the odd integers.

Click on thegreensquare to return

Solutions to Exercises 16

Exercise 1(b)We can write:4

j=1(2j-1) =3? j=1(2j-1) + (2×4-1),and from the previous exercise we have shown that 3 i=1(2i-1) = 9.Sinceiis a dummy variable it could just as well be calledj, thus 4

j=1(2j-1) = 9 + (2×4-1) = 16.Note that this result, and the last one, are perfect squares! We will

prove a general version of this below.

Click on thegreensquare to return

Solutions to Exercises 17

Exercise 1(c)The series4

s=110 sis 4 s=110 s= 101+ 102+ 103+ 104 = 11,110.Click on thegreensquare to return?

Solutions to Exercises 18

Exercise 1(d)The series3

j=112jmay be written as 3 j=112j= (12×1) + (12×2) + (12×3) = 12×(1 + 2 + 3),which shows us that we could have simply extracted the constant factor3 j=112j= 123? j=1jThe numerical value of the series is 3 j=112j= 12×(1 + 2 + 3) = 72.Click on thegreensquare to return?

Solutions to Exercises 19

Exercise 1(e)To calculate the series3

i=03(2i+ 1)it is simplest to extract the common factor3: 3 i=03(2i+ 1) = 33? i=0(2i+ 1) = 3× {(2×0 + 1) + (2×1 + 1) +(2×2 + 1) + (2×3 + 1)} = 3{1 + 3 + 5 + 7} = 48.Note that the sequence2i+ 1also generates the odd integers.

Click on thegreensquare to return?

Solutions to Exercises 20

Exercise 1(f)The series3

j=11j

2may be written as

3 j=11j 2=11 2+12 2+13 2 = 1 + 14 +19 = 1 +

9 + 436

= 1 + 1336

36 + 1336

4936
.Click on thegreensquare to return?

Solutions to Exercises 21

Exercise 2(a)To write1 + 20 + 400 + 8,000as a sum, note that

1 = 20

0,

20 = 20

1,

400 = 20

2,

8,000 = 203.This shows that we may write

1 + 20 + 400 + 8,000 =3?

j=020 j.or, alternatively,

1 + 20 + 400 + 8,000 =4?

i=120 i-1.Click on thegreensquare to return?

Solutions to Exercises 22

Exercise 2(b)The sum-3-1+1+3+5+7is a sum over a consecutive range of odd integers. It may be written in many different ways. Here are three possibilities.-3-1 + 1 + 3 + 5 + 7 =4? j=-1(2j-1),or6 i=1[(2j-1)-4].or3 j=-4(2j+ 1).There are many other possibilities.

Click on thegreensquare to return

Solutions to Exercises 23

Exercise 3(a)We are asked to prove thatn

i=1i

2=n(n+ 1)(2n+ 1)6

.Stepa),checkwheni= 1:1 i=1i

2= 12= 1 =1(1 + 1)(2×1 + 1)6

Stepb)assumethe result forn=k, so forn=k+ 1:

k+1? i=1i 2=k? i=1i

2+ (k+ 1)2=k(k+ 1)(2k+ 1)6

+ (k+ 1)2assumption k(k+ 1)(2k+ 1) + 6(k+ 1)26extract common factor(k+ 1)= (k+ 1)[2k2+k+ 6k+ 6]6 =(k+ 1)[2k2+ 7k+ 6]6 (k+ 1)(k+ 2)(2k+ 3)6 =(k+ 1)(k+ 2)(2[k+ 1] + 1)6

Click on thegreensquare to return?

Solutions to Exercises 24

Exercise 3(b)To prove thatn

j=1j

3=n2(n+ 1)24

,firstcheckit forn= 1: i.e.,? 1 j=1j3= 1 =12×224 Inductive step:assume it is true forn=k, then forn=k+ 1k+1? j=1j 3=k? j=1j

3+ (k+ 1)3

k2(k+ 1)24 + (k+ 1)3 k2(k+ 1)2+ 4(k+ 1)34 (k+ 1)2[k2+ 4(k+ 1)]4 =(k+ 1)2(k+ 2)24 which, by thePrinciple of Induction, proves the result.

Click on thegreensquare to return?

Solutions to Exercises 25

Exercise 3(c)To prove thatn

j=12 j-1= 2n-1,firstcheckit forn= 1: i.e.,? 1 j=121-1= 1 = 21-1.? In theinductive stepfirst assume it is true forn=k, then for n=k+ 1k+1? j=12 j-1=k? j=12 j-1+ 2k+1-1 = 2 k-1 + 2k = 2×2k-1 = 2k+1-1.? which, by thePrinciple of Induction, proves the result.

Click on thegreensquare to return?

Solutions to Exercises 26

Exercise 3(d)To prove thatn

j=0x j=1-xn+11-x,forx?= 1firstcheckit forn= 0: i.e.,? 0 j=0xj=x0= 1 =1-x0+11-x.? In theinductive stepassume it is true forn=k, so forn=k+ 1k+1? j=0x j=k? j=0x j+xk+1

1-xk+11-x+xk+1

1-xk+1+ (1-x)(xk+1)1-x

1-xk+21-x.?

which, by thePrinciple of Induction, proves the result.

Click on thegreensquare to return?

Solutions to Exercises 27

Exercise 4(a)To prove that5

n-1 is divisible by4,firstcheckit forn= 1: i.e.,5

1-1 = 5-1 = 4 = 4×1.?

Inductive step:assume it is true forn=k, i.e.,assume5 k-1 = 4r, whereris an integer. Then forn=k+ 15 k+1-1 = 5×5k-1 = 5×(4r+ 1)-1,since5 k= 4r+ 1= 4×5r+ 5-1 = 4×(5r+ 1).? which, from thePrinciple of Induction, proves the result.

Click on thegreensquare to return

Solutions to Exercises 28

Exercise 4(b)To prove that9

n+ 3 is divisible by4,firstcheckit forn= 1: i.e.,9

1+ 3 = 9 + 3 = 12 = 4×3.?

Inductive step:assume it is true forn=k, i.e.,assume9 k+3 = 4r, whereris an integer. Then forn=k+ 19 k+1+ 3 = 9×9k+ 3 = 9×(4r-3) + 3 = 4×9r-27 + 3 = 4×5r-24 = 4×(5r-6).? which, from thePrinciple of Induction, proves the result.

Click on thegreensquare to return

Solutions to Exercises 29

Exercise 4(c)To prove that3

n> n2, i.e.,3 n-n2>0, using proof by induction, we firstcheckit forn= 1: i.e.,3

1= 3>12= 1.?

Inductive step:now assume it is true forn=k, i.e.,assumethat3 k-k2>0. Forn=k+ 13 k+1-(k+ 1)2= 3×3k-(k+ 1)2 = 3(3 k-k2+k2)-(k+ 1)2 = 3(3 k-k2) + 3k2-k2-2k-1 = 3(3 k-k2) +k2+k2-2k-1quotesdbs_dbs29.pdfusesText_35

[PDF] Travaux dirigés d 'informatique industrielle : bascules synchrones

[PDF] exercices sur les integrales generalisees - IECL

[PDF] Exercices - Formules intégrales de Cauchy - Inégalités de Cauchy

[PDF] TD 8 : Les boucles en langage C - Lipn

[PDF] TD 5 : Chaînes de caractères - Cedric/CNAM

[PDF] Tableaux et pointeurs (corrigé) 1 Tableaux

[PDF] fiche exo chap1 corrige

[PDF] Exercices d 'électromagnétisme

[PDF] limites et continuité - Philippe DEPRESLE

[PDF] trigonometrie - exercices corriges - Free

[PDF] Polycopié de cours et d exercices dirigés 1ère partie

[PDF] 1 Logique des propositions - Ensiie

[PDF] Corrigés - La Chaire EPPP

[PDF] MANAGEMENT De la QUALITE TOTAL - Jamiati

[PDF] MANAGEMENT De la QUALITE TOTAL - Jamiati