induction

[Anzas]

prove that 3^(2n+1) + 4^(2n+1)
is divided by 7 for every natural n

[Zurtex]

What have you done so far?

[snoble]

this isn't that hard. It is just induction as you suspect. The only fact you need to know is that c_1n + c_2m \equiv b_1n + b_2m\, (mod\, k) if c_1\equiv b_1,\,c_2\equiv b_2\,(mod\, k).

So just write down your sequence a_n = 3^{2n+1}+4^{2n+1}. When a_n is in that form can you write down a_{n+1} without out modifying the exponent.

Hope those hints help.
Steven

[Anzas]

well assuming that 3^(2n+1) + 4^(2n+1) is divisible by 7
im writing down what needs to be proven for n=n+1

3^(2n+3) + 4^(2n+3) / 7 = some integer = Z

9*3^(2n+1)+16*4^(2n+1) / 7 = Z

3^(2n+1)+4^(2n+1) / 7 + 8*3^(2n+1)+15*4^(2n+1) / 7 = Z

the first term is divisible because of the induction assumption so that leaves me with
8*3^(2n+1)+15*4^(2n+1) / 7

here im stuck i can't find a way to show that this term is divisible by 7
i tried proving that with another induction but that led me no where.
i also tried transforming 8*3^(2n+1)+15*4^(2n+1) / 7 to
7*3^(2n+1)+7*4^(2n+1) / 7 + 3^(2n+1)+8*4^(2n+1) / 7

3^(2n+1)+4^(2n+1) + 3^(2n+1)+8*4^(2n+1) / 7
and that leaves me with the term 3^(2n+1)+8*4^(2n+1) / 7
that does not help me i can't find a way to show that its divisible by 7
any help/tips would be appreciated

sorry for not using latex by the way it would just take me too much time to type all this in latex :smile:

[snoble]

Oh you're so close!

(3^(2n+1)+4^(2n+1)) / 7 + (8*3^(2n+1)+15*4^(2n+1)) / 7
= (3^(2n+1)+4^(2n+1)) / 7 + (3^(2n+1)+4^(2n+1)) / 7 + (7*3^(2n+1)+14*4^(2n+1)) / 7

You just needed to do your trick one more time over

Hope that helps
Steven

[Anzas]

of course! i can't believe i didn't notice this thank you very much! :smile:

[Algebracus]

We can easily prove it without induction:

a_n = 3^{2n+1}+4^{2n+1}\equiv 3^{2n+1} + (-3)^{2n+1} \equiv 3^{2n+1}\cdot(1 + (-1)^{2n+1}) \equiv 0 (mod 7).