Prove, using induction

1. Mar 23, 2005

devious_

I was asked to prove, using induction, that 34n+2 + 26n+3 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) = 34k+2 + 26k+3
f(k+1) = 34k+6 + 26k+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$$

2. Mar 23, 2005

mathman

Your proof is incorrect - the factoring is wrong.

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

3. Mar 24, 2005

devious_

Thanks.

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

4. Mar 24, 2005

mathman

Yes: 92n+1+82n+1 does not factor as you wrote it. You confused it with an expression with a minus sign.

5. Mar 24, 2005

devious_

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

6. Mar 24, 2005

HallsofIvy

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

Oops, I guess it's not correct.

7. Mar 24, 2005

dextercioby

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

Daniel.

8. Mar 24, 2005

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}$$

Last edited: Mar 24, 2005