Question

use induction to prove 13^n -1is amultiple of 12​

Answer 1

Step-by-step explanation:

Thm: for all natural numbers n≥12, n=3a+7b, for some natural numbers a, and b. (Natural numbers include 0 here).

My question about the following proof has to do with why we need to show 4 different cases, instead just the last one. I expand this question further at the end.

Proof: By strong induction

For all natural numbers n, such that n≥12, let P(n) be the statement "n=3a+7b."

Let n be an arbitrary natural number such that n≥12. Suppose for every 12≤k<n,P(k) is true.

We consider 4 cases.

Case#1: n=12

n=3(4)+0(7)

Case#2: n=13

n=3(2)+7(1)

Case#3: n=14

n=3(0)+7(2)

Case#4: n≥15 Then (n−3)≥12 and (n−3)<n. It follows from the induction hypothesis that P(n−3) is true, and so we can choose some a and b such that 3a+7b=(n−3). Thus, n=3a+7b+3=3(a+1)+7b. Since a+1 is a natural number, it follows that P(n) is true, and the implication follows. Since n was arbitrary, it is true for all such, and the theorem follows.

My question: Why do we need cases 1,2, and 3? Why can't I just assume that P(k) is true for all 12≤k<n,P(k), and then start with case 4 that says n≥15. Since I have assumed P(k) for all values less than n, I should be able to draw the same conclusions, as none seem dependent on the previous 3 cases.

If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.

Edit: changed c to b, also added MathJax delimiters