# 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,…