How can I prove that 34n+2 + 26n+3 is divisible by 17 using induction?

[devious_]

I was asked to prove, using induction, that 3⁴ⁿ⁺² + 2⁶ⁿ⁺³ is divisible by 17. I tried to do it, but I couldn't get anywhere. Can someone give me a push in the right direction?

Here's my attempt:
f(k) = 3^4k+2 + 2^6k+3
f(k+1) = 3^4k+6 + 2^6k+9
And now, all I have to do is prove that f(k+1) - f(k) = 17m, but I couldn't do it.


I don't really see why induction is necessary anyway. Here's my induction-free attempt:

$$3^{4n+2} + 2^{6n+3} = 9^{2n+1} + 8^{2n+1} = (9+8) \sum^{2k+1}_{n=1} 9^{2k+1-n} \; 8^{n-1} = 17m$$

 

[mathman]

Your proof is incorrect - the factoring is wrong.

Proof of theorem: f(k+1)=81*3^4k+2+64*2^6k+3
=17*3^4k+2+64*f(k), where both terms in the sum are divisible by 17. You need also f(0)=17 to start with.

 

[devious_]

Thanks.

By the way, did you mean that my induction-free proof was wrong?

 

[mathman]

Yes: 9²ⁿ⁺¹+8²ⁿ⁺¹ does not factor as you wrote it. You confused it with an expression with a minus sign.

 

[devious_]

Ah yes, it's:
a^n + b^n = (a+b)[a^(n-1) - a^(n-2)b + ... + b^(n-1)], correct?

 

[HallsofIvy]

You mean like a^2+ b^2= (a+ b)(a-b )?

Oops, I guess it's not correct.

 

[dextercioby]

Nope,it the REALS,you can't factor $$a^{n}+b^{n}$$...

Daniel.

 

[Data]

Well, if n is odd you can, and his newest attempt at a factorization is correct. This makes his original proof right, with a small modification.

$$n \in \mathbb{N} \Longrightarrow 3^{4n+2} + 2^{6n+3} = 9^{2n+1} + 8^{2n+1} = 17\sum_{k=0}^{2n}(-1)^{k} \ 9^k \ 8^{2n-k}$$