Proof by mathematical induction

[rock.freak667]

[SOLVED] Proof by mathematical induction

Homework Statement

Prove by mathematical induction that for all +ve integers n,$10^{3n}+13^{n+1}$ is divisible by 7.

Homework Equations

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!