# 6. Induction

Proof by induction is a method of proving (countably) infinitely many propositions at a time. A proof by induction consists of a basis step and an induction step. In the basis step one proves the proposition for the simplest possible case. Then one proves that if the proposition holds for a specific case, then this implies that the proposition also holds for the next case. We can illustrate the procedure as an infinite line of domino bricks; the basis step corresponds to falling the first domino brick while the induction step corresponds to that if one brick falls, the next will also fall. It is not hard to realize that we in this case will fall all bricks by falling the first.

Axiom of induction: Let Pn be a proposition depending on the integer n. If

1) Basis step: P1 is true (proposition is true for n=1)
2) Induction steg: Pp implies Pp+1, that is, if the proposition is true for n=p then it must also be true for n=p+1

then the proposition is true for all integers n=1,2,3,…

Example 1: We note that 61=6, 62=36, 63=216, 64=1296, that is, the first 4 integer powers of 6 has the last digit 6. Let us show that this true for all positive integer powers 6n.
Basis step:
61=6 has last digit 6.

Induction step: We assume that the proposition is true for n=p, that is, 6phas last digit 6. This we can write as

for some integer k. If this assumption holds, we have for 6p+1 that

that is, 6p+1 also has last digit 6.

Since we have shown that the proposition holds for the basis step n=1 as well as that the assumption that the proposition holds for n=p implies that it also holds for n=p+1, it follows from the principle of induction that the proposition is true for all integers n=1,2,3,…

Example 2: Show that

Basis step: We have that

Induction step: We assume that the formula is correct for n=p, that is

We want to show that it then also must hold that

We have that

Since we have shown that the proposition holds for the basis step n=1 as well as that the assumption that the proposition holds for n=p implies that it also holds for n=p+1, it follows from the principle of induction that the proposition is true for all integers n=1,2,3,…

Example 3: Show that

is divisible by 7 for every n=1,2,3,…
Basis step: We have that

is divisible by 7.
Induction step: We assume that

is divisible by 7, that is, that

for some integer k. Then

is also divisible by 7.
Since we have shown that the proposition holds for the basis step n=1 as well as that the assumption that the proposition holds for n=p implies that it also holds for n=p+1, it follows from the principle of induction that the proposition is true for all integers n=1,2,3,…

Example 4: Show that

for n=10,11,12,…
Basis step:

Induction step: Assume that the inequality holds for n=p, that is

We want to show that it then also must hold for n=p+1, that is

We have that

since p>9.

Since we have shown that the proposition holds for the basis step n=10 as well as that the assumption that the proposition holds for n=p implies that it also holds for n=p+1, it follows from the principle of induction that the proposition is true for all integers n=10,11,12,…

Example 5: Show that

for n=2,3,4,…
Basis step:

Induction step: Assume that the inequality holds for n=p, that is

We want to show that it then also must hold for n=p+1, that is

We have according to the induction assumption that

If we could have shown that

we would have been finished. However,

Since we have shown that the proposition holds for the basis step n=2 as well as that the assumption that the proposition holds for n=p implies that it also holds for n=p+1, it follows from the principle of induction that the proposition is true for all integers n=2,3,4,…

Example 6: Show that the recurrence equation

has the solution

Basis step:

Induction step: Assume that the formula is correct for n=p, that is

Then we have that

that is, the formula is correct also for n=p+1. Since we have shown that the proposition holds for the basis step n=0 as well as that the assumption that the proposition holds for n=p implies that it also holds for n=p+1, it follows from the principle of induction that the proposition is true for all integers n=0,1,2,3,…

Example 7: Fibonacci‘s sequence {an}={1,1,2,3,5,8,13,21,…} is defined recursively by

Show that the fibonacci numbers

for n=1,2,3…
Basis step:

Induction step: Assume that the inequality holds for n=p and for n=p-1, that is

We want to show that it also must hold for n=p+1, that is

We have according to the induction assumption that

Since we have shown that the proposition holds for the basis step n=0,n=1as well as that the assumption that the proposition holds for n=p-1 and n=pimplies that it also holds for n=p+1, it follows from the principle of induction that the proposition is true for all integers n=1,2,3,…