Induction, my first time; please be gentle.

[flyingpig]

Homework Statement

I like this thing call induction

Prove that for every integer n\geq 0 that

5| (9^n - 4^n)

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?

 

[Mark44]

Homework Statement

I like this thing call induction

Prove that for every integer n\geq 0 that

5| (9^n - 4^n)

The Attempt at a Solution

1) Base Case n = 0

9^0 - 4^0 = 0

9⁰ - 4⁰ = 5

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?

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

 

[flyingpig]

9⁰ - 4⁰ = 5

;;;
No.

 

[Mark44]

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

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

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

9^{k + 1} - 4^{k + 1} = 9*9^k - 4*4^k
= 4*9^k - 4*4^k + 5*9^k

Hopefully, you can do something with that.

 

[flyingpig]

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

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

 

[Mark44]

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

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

 

[Dick]

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

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

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?

 

[flyingpig]

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?

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

 

[Mark44]

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

 

[Dick]

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

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'.

 

[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?[/color]]

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.