1. Not finding help here? Sign up for a free 30min 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!

Proof by Induction Involving Divisibility

  1. Feb 20, 2015 #1
    1. The problem statement, all variables and given/known data
    Let P(n): 7|(34n+1-52n-1. Prove that P(n) is true for every natural number n.

    2. Relevant equations
    *I know that proving by induction requires a proving P(1) true, and then proving P(k+1) true.
    *If a|b, then b=a*n, for some n∈ℤ

    3. The attempt at a solution
    I have proved the "base case" for P(1). Long story short, for n=1, you wind up with 7|238 by definition of divisibility since 238=7(34). So P(1) is true.

    The next part is where it gets tricky - Assuming P(k) is true, that is, 7|(34k+1-52k-1, which is the inductive hypothesis. Then proving for P(k+1). What I have so far is...
    7|7|(34(k+1)+1-52(k+1)-1
    =34k+5-52k+1
    =34 * 34k+1-51*52k
    =34 * 34k+1-(3*52k+2*52k)
    =34 * 34k+1-3*52k-2*52k
    =..............

    Now I don't know what to do! I know I have to get it to the point where I can use the inductive hypothesis, which is what I'm trying to do, but I've hit a wall, or taken a wrong turn when split the 5 into a two and a three. Any ideas?
     
  2. jcsd
  3. Feb 20, 2015 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Here's a short hint 3^4=81=56+25=56+5^2 and 56 is divisible by 7.
     
  4. Feb 21, 2015 #3
    Ok yes I see that, but am having trouble using it. Are the steps that I have taken so far correct? Or have I done more than necessary. What I'm saying is, can I use this information about 3^4 from the step that I left off at?
     
  5. Feb 21, 2015 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Convince yourself that ##P(k+1)=81*3^{4k+1}-25*5^{2k-1}##. Use that ##81=56+25##. See how you can express that in terms of ##P(k)##?
     
  6. Feb 21, 2015 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    This is badly written: the "equation" you wrote, namely
    [tex] 7|7|(3^{4(k+1)+1} - 5^{2(k+1)-1} \\
    = 3^{4k+5} - 5^{2k+1} \\
    \vdots
    [/tex]
    does not even make sense.

    To say it properly, here is a hint: letting ##F(n) = 3^{4n+1} - 5^{2n-1}##, prove that for positive integer ##k##, ##F(k) = 7j## for some positive integer ##j## implies ##F(k+1) = 7 m## for some positive integer ##m##.
     
  7. Feb 21, 2015 #6
    Thank you for you help, Dick! I understand now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted