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!

Math Proof

  1. Apr 16, 2012 #1
    1. Define a sequence of numbers in the following way:
    a[k]=a[k-1]+a[k-2]+a[k-3] for k≥3, s.t. a[0]=1, a[1]=2, a[2]=3, a[3]=6...
    *The numbers in brackets will be subscripts for the whole problem

    Prove that a[n]≤2^n using complete mathematical induction.

    This is what I have so far.
    We'll use complete mathematical induction, where P(n)=a[n]≤2^n
    P(0) is the statement a[0]≤2^0.
    This is true because 1≤1.
    Assume For all n, 0, 1, ..., k a[n]≤2^n is true.
    We want to show that for k+t that a[k+1]≤2^(k+1)
    Thus, a[k+1]=a[k]+a[k-1]+a[k-2]
    And 2^(k+1)=2(2^k)
    Therefore, a[k]+a[k-1]+a[k-2]≤2(2^k).

    I can't seem to get past this part. Any help would be greatly appreciated.
     
  2. jcsd
  3. Apr 16, 2012 #2

    Mark44

    Staff: Mentor

    "Thus" isn't the right word here since it doesn't follow from your assumption and what you want to show. a[k+1]=a[k]+a[k-1]+a[k-2] by definition of the sequence.
    Start with a[k+1] = a[k]+a[k-1]+a[k-2].
    On the right side, a[k] <= 2k, a[k-1] <= 2k - 1, and a[k-2] <= 2k - 2, right? So what can you say about a[k]+a[k-1]+a[k-2]?
     
  4. Apr 16, 2012 #3
    that a[k]+a[k-1]+a[k-2]≤2^k+2^(k-1)+2^(k-2). but how would I get to 2^(k+1) from here?
     
  5. Apr 16, 2012 #4

    Mark44

    Staff: Mentor

    Factor the expression on the right - what do you get?
     
  6. Apr 16, 2012 #5
    1.75*(2^k)
     
  7. Apr 16, 2012 #6

    Mark44

    Staff: Mentor

    What do you get in terms of 2k-2?
     
  8. Apr 16, 2012 #7
    2k-2(22+2+1), which is 2k-2(7). since neither this nor the other can get me to what I want, I made a mistake somewhere
     
    Last edited: Apr 16, 2012
  9. Apr 16, 2012 #8

    Mark44

    Staff: Mentor

    No, this is the right track. Note that 7 < 23.
     
  10. Apr 16, 2012 #9
    And since 7<23, they are not equal but since the first two are, you use ≤ instead of = or <. Also 2k-223≥7(2k-2)
     
    Last edited: Apr 16, 2012
  11. Apr 16, 2012 #10

    Mark44

    Staff: Mentor

    Basically you are showing that an+1 = an + an - 1 + an - 2 ≤ 2n-2(7) < 2n-2(8) = 2n+1

    IOW, that an+1 ≤ 2n+1.
     
  12. Apr 16, 2012 #11
    Thanks so much for your help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Math Proof
  1. Math proof (Replies: 2)

  2. Discrete Math Proof (Replies: 2)

  3. Discrete Math Proof (Replies: 4)

  4. Math Proofs: Relations (Replies: 4)

Loading...