[SOLVED] Proof by mathematical induction

[rock.freak667]

1. The problem statement, all variables and given/known data
Prove by mathematical induction that for all +ve integers n,10^{3n}+13^{n+1} is divisible by 7.


2. Relevant equations



3. The attempt at a solution

Assume true for n=N.
10^{3N}+13^{N+1}=7A

Multiply both sides by (10^3+13)

(10^{3N}+13^{N+1})(10^3+13)=7A(10^3+13)

10^{3N+3}+ 10^3(13^{N+1})+13(10^{3N})+13^{N+2}=7A(1013)

10^{3N+3}+13^{N+2}=7A(1013)-10^3(13^{N+1})-13(10^{3N})

Here is where I am stuck. I need to show that 10^3(13^{N+1})-13(10^{3N}) is divisible by 7 now.

What I would like to get is that 10^3(13^{N+1})-13(10^{3N}) can somehow be manipulated into the initial inductive hypothesis and then it will become true for n=N+1. So I need some help.

[scottie_000]

the standard trick here is to write the 10^3 and the 13 in terms of multiples of 7, plus or minus 1

[rock.freak667]

Uhm...I can write 13 as 2(7)-1 and 10^3 as 143(7)+1 but I don't see how that helps.

[scottie_000]

well then if you expand things out you should see what happens to the equation

[rock.freak667]

ah..thank you scottie_000

I see it now, was so simple.So when I have to prove that some expression is divisible by a number,k, always try to rewrite any unwanted constants in terms of k?

[scottie_000]

like i said, it's the best trick to look for
glad to help by the way!