# Induction, my first time; please be gentle.

1. Sep 13, 2011

### flyingpig

1. The problem statement, all variables and given/known data

I like this thing call induction

Prove that for every integer $$n\geq 0$$ that

$$5| (9^n - 4^n)$$

3. The attempt at a solution

1) Base Case n = 0

$$9^0 - 4^0 = 0$$

Clearly it is true

2) Take n = k + 1

$$9^{k + 1} - 4^{k + 1} = 9^k 9 - 4^k 4 = 9^k (4 + 5) - 4^k 4 = 9^k 5 + 9^k 4 - 4^k 4 = 9^k 5 + 4(9^k - 4^k)$$

Now here is the problem. I know I did it correctly, but I don't know what to do with $$9^k 5 + 4(9^k - 4^k)$$ I know that 4 won't matter because I proved 1) and that 5 behind the 9^k would also disappear. But how do I formally say that?

2. Sep 14, 2011

### Staff: Mentor

90 - 40 = 5
You seem to be missing your induction hypothesis; i.e., that 5 | 9k - 4k. Another way to say this is that 9k - 4k = 5M for some integer M.

3. Sep 14, 2011

### flyingpig

;;;
No.

4. Sep 14, 2011

### Staff: Mentor

Scratch that - you were right. I think it's getting late.

Anyway, by the Induction Hypothesis, you know that 9k - 4k is divisible by 5, which means that 9k - 4k = 5M for some integer M.

The rest of the proof hinges on showing that 9k + 1 - 4k + 1 can be related back to 9k - 4k in some way.

9k + 1 - 4k + 1 = 9*9k - 4*4k
= 4*9k - 4*4k + 5*9k

Hopefully, you can do something with that.

5. Sep 14, 2011

### flyingpig

Even with 9k - 4k = 5M, I don't know what to do with

4*(9k - 4k) + 5*9k

6. Sep 14, 2011

### Staff: Mentor

4*(9k - 4k) + 5*9k = 4* 5M + 5*9k

Can you show that this last expression is divisible by 5?

7. Sep 14, 2011

### Dick

Your first term is divisible by 5 from the induction hypothesis. Your second term is divisible by 5 just by looking at it. So the sum is divisible by 5. Yes?

8. Sep 14, 2011

### flyingpig

Yeah but I don't know how to write it properly.

9. Sep 14, 2011

### Staff: Mentor

Look at the expression on the right side of the equation in post #6. Factor 5 from each term.

10. Sep 14, 2011

### Dick

4*5*M+5*9^k=5*(4*M+9^k). That's 5 times an integer. I'm pretty sure anyone would believe that is divisible by 5. I'm not sure what you mean by 'write it properly'.

11. Sep 15, 2011

### flyingpig

1) Base Case n = 0

$$S(n): 9^n - 4^n$$

$$9^0 - 4^0 = 0$$

Clearly it is true

2) Assume that $$5|(9^n - 4^n)$$ is true, then we can show that S(n + 1) is also true, i.e.

$$S(n + 1) = 9^{n + 1} - 4^{n + 1} = 5M$$ (1) [Would it better to write $$5| 9^{n + 1} - 4^{n + 1}$$ instead because it is confusing with what is below?]

Assuming that S(n) is true, then $$\exists M \in \mathbb{Z}$$ such that

$$9^n - 4^n = 5M$$

Thus

$$9^{n + 1} - 4^{n + 1} = 9^n 9 - 4^n 4 = 9^n (4 + 5) - 4^n 4 = 9^n 5 + 9^n 4 - 4^n 4 = 9^n 5 + 4(9^n - 4^n) = 5M + 4^n + 4(5M) = 25M + 4^n$$

Since $$25M + 4^n \in \mathbb{Z}$$, it is clear that (1) is true by the Principles of Mathematical Induction.

Q.E.D.