proof for k natural numbers

saadsarfraz

Hi, how would you show that 4^(k)+4 * 9^(k) [tex]\equiv[/tex] 0 (mod 5)

d_leet

Note that 9 is congruent to 4 mod 5.

robert Ihnot

Checking a few small values of k shows it is not always true.

d_leet

I'm pretty sure that it is, in fact, always true.

NoMoreExams

It is? If we have

[tex] 4^{k+4} \cdot 9^{k} [/tex]

Then letting [tex] k = 0 [/tex] we get

[tex] 4^{0+4} \cdot 9^{0} = 256 [/tex]

That is certainly not 0 mod 5. Next letting [tex] k = 1 [/tex] we get

[tex] 4^{1+4} \cdot 9^{1} = 9216 [/tex]

Also not 0 mod 5?

wsalem

Actually, what he meant was [tex]4^k + 4*9^k \equiv 0 \text{mod} 5[/tex].

Hint. Try induction over [tex]k[/tex]. You may rephrase it to: for every [tex]k \in N[/tex], there's an [tex]n \in N[/tex] such that [tex]4^k + 4*9^k = 5n[/tex].

saadsarfraz

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.

saadsarfraz

would really appreciate if someone could help me on this.

wsalem

Define [tex]P(k)[/tex] as the statement: [tex]4^k + 4*9^k = 5n[/tex] for some [tex]n \in N[/tex]

For the inductive step.
Suppose [tex]P(k)[/tex] hold, i.e there is an [tex]n \in N[/tex] such that : [tex]4^k + 4*9^k = 5n[/tex].
Then you need to show that P(k+1) also holds, i.e there is an [tex]m \in N[/tex] such that [tex]4^{k+1} + 4*9^{k+1} = 5m[/tex].

saadsarfraz

i know how induction works but i cant figure out what specific 4^k expression do i have to add/multiply to [tex]
4^{k+1} + 4*9^{k+1} = 5m
[/tex] make it work for m+1.

wsalem

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 [tex]4^k = 5n - 4*9^k[/tex]
Now [tex]4^{k+1} + 4*9^{k+1} = ....[/tex]

now, for P(k+1) to hold, you must show that [tex]4^{k+1} + 4*9^{k+1} = 5*m[/tex] for some integer m.

saadsarfraz

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.

wsalem

I gave it to you in the earlier reply. Think harder, it should be quite obvious by now!

NoMoreExams

You know that

[tex] 4^k + 4 \cdot 9^k = 5m, k,m \in \mathbb{Z} [/tex]

Now we want to show that

[tex] 4^{l+1} + 4 \cdot 9^{l+1} = 5n, l, n \in \mathbb{Z} [/tex]

So let's work with our expression

[tex] 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 [/tex]

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.

wsalem

I think holding the final answer to enable saadsarfraz to reach it would have been much better!

wsalem

NoMoreExams,
This is incorrect, it is [tex] 4^k + 4 \cdot 9^k = 5m[/tex] where [tex]k,m \in \mathbb{Z} [/tex]

NoMoreExams

Yes sorry I'll fix it