Search

Induction Proofs: Worked examples (page 3 of 3)

Sections: Introduction, Examples of where induction fails, Worked examples

• (*)  For n > 1,  2 + 22 + 23 + 24 + ... + 2n = 2n+1 – 2

Let n = 1. Then:

2 + 22 + 23 + 24 + ... + 2n = 21 = 2

...and:

2n+1 – 2 = 21+1 – 2 = 22 – 2 = 4 – 2 = 2

So (*) works for n = 1.

Assume, for n = k, that (*) holds; that is, that

2 + 22 + 23 + 24 + ... + 2k = 2k+1 – 2

Let n = k + 1.

2 + 22 + 23 + 24 + ... + 2k + 2k+1

= [2 + 22 + 23 + 24 + ... + 2k] + 2k+1

= [2k+1 – 2] + 2k+1

= 2×2k+1 – 2

= 21×2k+1 – 2

= 2k+1+1 – 2

= 2(k+1)+1 – 2

Then (*) works for n = k + 1.

Note this common technique: In the "n = k + 1" step, it is usually a good first step to write out the whole formula in terms of k + 1, and then break off the "n = k" part, so you can replace it with whatever assumption you made about n = k in the previous step. Then you manipulate and simplify, and try to rearrange things to get the right-hand side of the formula in terms of k + 1.

• (*)  For n > 1, 1×2 + 2×3 + 3×4 + ... + (n)(n+1) = (n)(n+1)(n+2)/3

Then the left-hand side of (*) is 1×2 = 2
and the right-hand side of (
*) is (1)(2)(3)/3 = 2.

So (*) holds for n = 1. Assume, for n = k, that (*) holds; that is, assume that

1×2 + 2×3 + 3×4 + ... + (k)(k+1) = (k)(k+1)(k+2)/3

Let n = k + 1. The left-hand side of (*) then gives us:

1×2 + 2×3 + 3×4 + ... + (k)(k+1) + (k+1)((k+1)+1)
= [1×2 + 2×3 + 3×4 + ... + (k)(k+1)] + (k+1)((k+1)+1)

= [(k)(k+1)(k+2)/3] + (k+1)((k+1)+1)

= (k)(k+1)(k+2)/3 + (k+1)(k+2)

= (k)(k+1)(k+2)/3 + 3(k+1)(k+2)/3

= (k+3)(k+1)(k+2)/3

= (k+1)(k+2)(k+3)/3

= (k+1)((k+1)+1)((k+1)+2)/3

...which is the right-hand side of (*). Then (*) works for all n > 1.

• (*)  For n > 5, 4n < 2n.
• This one doesn't start at n = 1, and involves an inequality instead of an equation. (If you graph 4x and 2x on the same axes, you'll see why we have to start at n = 5, instead of the customary n = 1.)

Let n = 5.

Then 4n = 4×5 = 20, and 2n = 25 = 32.

Since 20 < 32, then (*) holds at n = 5.

Assume, for n = k, that (*) holds; that is, assume that 4k < 2k

Let n = k + 1.

The left-hand side of (*) gives us 4(k + 1) = 4k + 4, and, by assumption,

[4k] + 4 < [2k] + 4

Since k > 5, then 4 < 32 < 2k. Then we get

2k + 4 < 2k + 2k = 2×2k = 21×2k = 2k+1

Then 4(k+1) < 2k+1, and (*) holds for n = k + 1.

Then (*) holds for all n > 5.

• (*)  For all n > 1, 8n – 3n is divisible by 5.

Let n = 1.

Then the expression 8n – 3n evaluates to 81 – 31 = 8 – 3 = 5, which is clearly divisible by 5.

Assume, for n = k, that (*) holds; that is, that 8k – 3k is divisible by 5.

Let n = k + 1.

Then:

8k+1 – 3k+1 = 8k+1 – 3×8k + 3×8k – 3k+1

= 8k(8 – 3) + 3(8k – 3k) = 8k(5) + 3(8k – 3k)

The first term in 8k(5) + 3(8k – 3k) has 5 as a factor (explicitly), and the second term is divisible by 5 (by assumption). Since we can factor a 5 out of both terms, then the entire expression, 8k(5) + 3(8k – 3k) = 8k+1 – 3k+1, must be divisible by 5.

Then (*) holds for n = k + 1, and thus for all n > 1.

<< Previous  Top  |  1 | 2 | 3  |  Return to Index

 Cite this article as: Stapel, Elizabeth. "Induction Proofs: Worked Examples." Purplemath. Available from     https://www.purplemath.com/modules/inductn3.htm. Accessed [Date] [Month] 2016

Study Skills Survey

Tutoring from Purplemath
Find a local math tutor