Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by mathematical induction

  1. Feb 17, 2008 #1


    User Avatar
    Homework Helper

    [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,[itex]10^{3n}+13^{n+1}[/itex] is divisible by 7.

    2. Relevant equations

    3. The attempt at a solution

    Assume true for n=N.

    Multiply both sides by ([itex]10^3+13[/itex])


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


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

    What I would like to get is that [itex]10^3(13^{N+1})-13(10^{3N})[/itex] 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. jcsd
  3. Feb 17, 2008 #2
    the standard trick here is to write the 10^3 and the 13 in terms of multiples of 7, plus or minus 1
  4. Feb 17, 2008 #3


    User Avatar
    Homework Helper

    Uhm...I can write 13 as 2(7)-1 and 10^3 as 143(7)+1 but I don't see how that helps.
  5. Feb 17, 2008 #4
    well then if you expand things out you should see what happens to the equation
  6. Feb 17, 2008 #5


    User Avatar
    Homework Helper

    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?
  7. Feb 17, 2008 #6
    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?