1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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