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

Difficult induction proof

  1. Oct 13, 2011 #1
    1. The problem statement, all variables and given/known data

    [itex]2^{2n-1} + 3^{2n-1} is a number divisible by 5.[/itex]

    Prove by induction.

    2. Relevant equations

    3. The attempt at a solution

    Firstly, solving for n = 1 is true.

    I've re-written the statement to be:

    [itex]2^{2n-1} + 3^{2n-1} = 5L[/itex]

    where L is any natural number.

    Now, I assume that it is true for n = k, and then show that if that is so, then it must be true for k + 1.

    My problem, is that I don't know what to do to the right side of the equation here to keep a valid statement.

    [itex]2^{2k-1} + 3^{2k-1} = 5L[/itex]

    [itex]2^{2k+1} + 3^{2k+1} = 5L????[/itex]

    What do you do to 5L to keep a valid equation?
  2. jcsd
  3. Oct 13, 2011 #2


    User Avatar
    Science Advisor

    You have to move it, move it! since, as you said, you cannot yet state anything about P(k+1)

    Just write the expression as you did:


    And try using the fact of P(k) that 22k-1+32k-1=5L , to

    show the expression P(k+1) is also divisible by 5 .
  4. Oct 13, 2011 #3
    So, what are you saying? Repeat induction for the new function?
  5. Oct 13, 2011 #4


    User Avatar
    Science Advisor

    No; sorry, I used k instead of n, but it is the same thing. Use your knowledge of the fact that the expression for n is divisible by 5 to show that the expression for n+1 is also divisible by 5; just manipulate and rewrite the expression for n+1 to show it is divisible by 5, using the fact that the expression for n is also divisible by 5.
  6. Oct 13, 2011 #5


    User Avatar
    Science Advisor

    [tex]2^{2(n+1)-1}+ 3^{2(n+1)-1}= 2^{2n+ 1}+ 3^{2n+1}[/tex]
    [tex]= 4(2^{2n-1})+ 9(3^{2n-1})[/tex]

    and 9= 5+ 4.
    Last edited by a moderator: Oct 13, 2011
  7. Oct 13, 2011 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    In Latex, use "\text{ text with s p a c e s. }" to display text.

    Just pick another integer: [itex]2^{2k+1} + 3^{2k+1} = 5M[/itex]
    Last edited: Oct 13, 2011
  8. Oct 13, 2011 #7
    I don't understand how 9=5+4 in that spot proves anything.
  9. Oct 13, 2011 #8


    User Avatar
    Science Advisor

    9a+ 4b= (5+4)a+ 4b= 5a+ 4(a+ b)

    Saying anything more would be giving away the answer.
  10. Oct 13, 2011 #9
    I think I'm seeing it now.

    My end result using your algebra implies 4 times the statement initially assumed to be a multiple of 5, plus 5 times another statement (which is of course a multiple of 5 since it is being multiplied by 5), and a multiple of 5 plus a multiple of 5 is of couse a multiple of 5.

    Does it sound like I have a grasp of the proof?
  11. Oct 13, 2011 #10


    User Avatar
    Science Advisor

    Yes. You have, as I said, 9a+ 4b= (5+4)a+ 4b= 5a+ 4(a+ b). If you have already shown that a+ b is a multiple of 5, that is, a+ b= 5n for some n, then 9a+ 4b= 5a+ 4(5n)= 5(a+4n).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook