## proof for k natural numbers

Hi, how would you show that 4^(k)+4 * 9^(k) $$\equiv$$ 0 (mod 5)
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 Note that 9 is congruent to 4 mod 5.
 Recognitions: Gold Member Checking a few small values of k shows it is not always true.

## proof for k natural numbers

 Quote by robert Ihnot Checking a few small values of k shows it is not always true.
I'm pretty sure that it is, in fact, always true.

 Quote by d_leet I'm pretty sure that it is, in fact, always true.
It is? If we have

$$4^{k+4} \cdot 9^{k}$$

Then letting $$k = 0$$ we get

$$4^{0+4} \cdot 9^{0} = 256$$

That is certainly not 0 mod 5. Next letting $$k = 1$$ we get

$$4^{1+4} \cdot 9^{1} = 9216$$

Also not 0 mod 5?
 Actually, what he meant was $$4^k + 4*9^k \equiv 0 \text{mod} 5$$. Hint. Try induction over $$k$$. You may rephrase it to: for every $$k \in N$$, there's an $$n \in N$$ such that $$4^k + 4*9^k = 5n$$.
 sorry for the typo i corrected it. so if i use induction than its easy for the base case K=0 which gives me 5 congruent 0 mod 5 which is true. Now, wsalem wrote that expression using the relationship a=mn+b with b=0. Now how am I supposed to use induction for k in this case when there is also n present.
 would really appreciate if someone could help me on this.
 Define $$P(k)$$ as the statement: $$4^k + 4*9^k = 5n$$ for some $$n \in N$$ For the inductive step. Suppose $$P(k)$$ hold, i.e there is an $$n \in N$$ such that : $$4^k + 4*9^k = 5n$$. Then you need to show that P(k+1) also holds, i.e there is an $$m \in N$$ such that $$4^{k+1} + 4*9^{k+1} = 5m$$.
 i know how induction works but i cant figure out what specific 4^k expression do i have to add/multiply to $$4^{k+1} + 4*9^{k+1} = 5m$$ make it work for m+1.
 No, you are missing the point of induction here! It is k we want to run induction over, not m, so it is pointless to say "m+1". The existence of a such m is merely for the statement P(k) to hold at a particular case. Inductive step: Suppose P(k) holds, then $$4^k = 5n - 4*9^k$$ Now $$4^{k+1} + 4*9^{k+1} = ....$$ now, for P(k+1) to hold, you must show that $$4^{k+1} + 4*9^{k+1} = 5*m$$ for some integer m.
 sorry i didnt mean m+1. What i'm saying is that there is some expression involving k which must be multiplied on either side of the equation. I don't know what that expression is.
 I gave it to you in the earlier reply. Think harder, it should be quite obvious by now!
 You know that $$4^k + 4 \cdot 9^k = 5m, k,m \in \mathbb{Z}$$ Now we want to show that $$4^{l+1} + 4 \cdot 9^{l+1} = 5n, l, n \in \mathbb{Z}$$ So let's work with our expression $$4^{l+1} + 4 \cdot 9^{l+1} = 4 \cdot 4^l + 4 \cdot 9 \cdot 9^l = 4 \cdot 4^l + 4 \cdot (4+5) \cdot 9^l = 4 \cdot 4^l + 4^{2} \cdot 9^l + 4 \cdot 5 \cdot 9^l = 4 \left(4^l + 4 \cdot 9^l) + 5 \cdot 4 \cdot 9^l$$ The first part you know is divisible by 5 from the hypothesis, the 2nd part has a factor of 5 so obviously it is too.
 I think holding the final answer to enable saadsarfraz to reach it would have been much better!

NoMoreExams,
 Quote by NoMoreExams You know that $$4^k + 4 \cdot 9^k = 5k, k \in \mathbb{Z}$$
This is incorrect, it is $$4^k + 4 \cdot 9^k = 5m$$ where $$k,m \in \mathbb{Z}$$
 Yes sorry I'll fix it

 Similar discussions for: proof for k natural numbers Thread Forum Replies General Math 7 Linear & Abstract Algebra 6 General Math 8 Calculus 4