# Proof by mathematical induction

1. Feb 17, 2008

### rock.freak667

[SOLVED] Proof by mathematical induction

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.

2. Feb 17, 2008

### 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

3. Feb 17, 2008

### 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.

4. Feb 17, 2008

### scottie_000

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

5. Feb 17, 2008

### 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?

6. Feb 17, 2008

### scottie_000

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

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?