# Homework Help: Math Proof

1. Apr 16, 2012

### rtw528

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. Apr 16, 2012

### 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.
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]?

3. Apr 16, 2012

### rtw528

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?

4. Apr 16, 2012

### Staff: Mentor

Factor the expression on the right - what do you get?

5. Apr 16, 2012

### rtw528

1.75*(2^k)

6. Apr 16, 2012

### Staff: Mentor

What do you get in terms of 2k-2?

7. Apr 16, 2012

### rtw528

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
8. Apr 16, 2012

### Staff: Mentor

No, this is the right track. Note that 7 < 23.

9. Apr 16, 2012

### rtw528

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
10. Apr 16, 2012

### 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.

11. Apr 16, 2012

### rtw528

Thanks so much for your help.