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

  1. Aug 6, 2005 #1
    I need to prove by mathematical induction that all positive numbers of the form 5^n-4n+15 are divisible by 16 where n is a natural number(1,2,3,4,5...).

    So far
    P(1) = 5^1-4*1+15 = 16 true for P(1)
    AssumeP(k) is true.

    5^k-4k + 15 is disible by 16.

    Now for P(k+1)

    P(k+1)=5^(k+1) -4(k+1)+ 15 I don't know how to prove it is divisible by 16?

    Normally with these the P(k+1) usually equals a sum of 2 numbers that collecting like terms,etc. comes to the same style as the original equation except with k+1 where n is. Thanks for your time.
     
  2. jcsd
  3. Aug 6, 2005 #2

    VietDao29

    User Avatar
    Homework Helper

    So you know:
    [tex]5 ^ k - 4k + 15[/tex] is divisible by 16.
    You will try to arrange [tex]5 ^ {k + 1} - 4(k + 1) + 15[/tex] into something like:
    [tex]5 ^ k - 4k + 15 + ?[/tex] Since [tex]5 ^ k - 4k + 15[/tex] is divisible by 16, you just need to prove '?' is divisible by 16.
    Here we go:
    [tex]5 ^ {k + 1} - 4(k + 1) + 15 = ... = 5 ^ k - 4k + 15 + 4(5 ^ k - 1)[/tex]
    You need to prove [tex]4(5 ^ k - 1)[/tex] is divisible by 16. In other words, you need to prove: [tex]5 ^ k - 1[/tex] is divisible by 4 (You can prove this by induction or:
    [tex]a ^ {\alpha} - 1 = (a - 1)(a ^ {\alpha - 1} + a ^ {\alpha - 2} + a ^ {\alpha - 3} + ... + a ^ {2} + a + 1}) \mbox{, }\alpha \in \mathbb{N} ^ *[/tex]).
    Viet Dao,
     
  4. Aug 6, 2005 #3
    How did you get from:

    5^(k+1) -4(k+1) + 15 = 5^k - 4k + 15 + 4(5^k -1)
     
  5. Aug 6, 2005 #4

    VietDao29

    User Avatar
    Homework Helper

    Okay, so you notice: In [tex]5 ^ {k + 1} - 4(k + 1) + 15[/tex], there is -4k, and + 15, but there is no [itex]5 ^ k[/itex], so you will plus and then subtract [itex]5 ^ k[/itex]:
    [tex]5 ^ {k + 1} - 4(k + 1) + 15 = 5 ^ {k + 1} - 4k - 4 + 15 = 5 ^ k - 4k + 15 + 5 ^ {k + 1} - 5 ^ k - 4 = ...[/tex]
    Can you go from here?
    Viet Dao,
     
  6. Aug 6, 2005 #5
    [tex]5 ^ {k + 1} - 4(k + 1) + 15 [/tex]
    [tex]=5*5^k-4k-4+15[/tex]
    [tex]=5^k+4*5^k-4k-4+15[/tex]
    [tex]=5^k-4k+15+4(5^k-1)[/tex]

    where '*' means multiplication
     
    Last edited: Aug 6, 2005
  7. Aug 7, 2005 #6

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

    Deryk, the way to solve an induction problem like this is to make maximum use of your induction hypothesis.
    If you have the expression:

    [tex]5^{k+1}-4(k+1)+15 = 5 \cdot 5^k-4k +11[/tex]
    and you assume that
    [tex]5^k-4k +15[/tex]
    is divisible by 16, then you should try to get this expression for P(k) into your expression for P(k+1).
    How to do that? The most obvious way seems to be to factor out the 5, right? That'll bring the 5^(k+1) back to 5^k and we can worry about the rest later. So you get:

    [tex]5(5^k-4k+15)+ 16k-64[/tex]
     
  8. Aug 10, 2005 #7

    I can see that:

    [tex]5(5^k-4k+15)+ 16k-64[/tex]

    Is equal to P(k) + 16(n element of reals)

    But I m not sure I understand how it was induced into the equation.

    Here is where I am stuck.

    I've found:

    [tex] 5 \cdot 5^k-4k +11[/tex]

    naturally.

    The difference between [itex] 5\cdot 5^k [/itex] and [itex] (5^k-4k+15) [/itex] is [itex] 5\cdot(-4k+15) [/itex]

    therefore it is necessary to add [itex] 5\cdot(-4k+15) [/itex] to -4k and +11 to complete the equation. It seems to me to be right except if it is I have a sign problem.

    I am learning induction too so it is helpful for me to work through this problem now, can you tell me which part I have done wrong.
     
  9. Aug 10, 2005 #8

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

    It doesn't need to be that complicated. You want add something to [itex]5(5^k-4k+15)[/itex] to make it equal to [itex]5 \cdot 5^k-4k +11[/itex] in order to get the same equation. Clearly you already have the [itex]5\cdot 5^k[/itex], you have -20k, so you add 16k to get -4k, and you have (5)(15)=75, so you subtract 64 to get 11.

    [tex]5(5^k-4k+15)+ 16k-64=5\cdot 5^k-4k+11[/tex]

    I hope that was clear enough, it's just arithmetic. Don't know how to explain it better.
     
  10. Aug 10, 2005 #9

    Thanks Galileo for your reply, I worked out my mistake before I got here it was just a stupid mistake of adding and adding dumb really. :rolleyes:

    I just wanted to say that your explanation has helped me the most to grasp the concepts so thanks Reaallly much. o:) :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by induction
  1. Proof by induction (Replies: 6)

  2. Proof by induction (Replies: 0)

  3. Proof by Induction (Replies: 9)

  4. Induction Proof (Replies: 5)

  5. Induction Proof (Replies: 1)

Loading...