Proving a[n]≤2^n using Mathematical Induction

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

 

[Mark44]

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]

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

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.

Start with a[k+1] = a[k]+a[k-1]+a[k-2].
On the right side, a[k] <= 2^k, a[k-1] <= 2^{k - 1}, and a[k-2] <= 2^{k - 2}, right? So what can you say about a[k]+a[k-1]+a[k-2]?

 

[rtw528]

So what can you say about a[k]+a[k-1]+a[k-2]?

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?

 

[Mark44]

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

 

[rtw528]

1.75*(2^k)

 

[Mark44]

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

 

[rtw528]

2^k-2(2²+2+1), which is 2^k-2(7). since neither this nor the other can get me to what I want, I made a mistake somewhere

 

[Mark44]

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

 

[rtw528]

And since 7<2³, they are not equal but since the first two are, you use ≤ instead of = or <. Also 2^k-22³≥7(2^k-2)

 

[Mark44]

Basically you are showing that a_n+1 = a_n + a_{n - 1} + a_{n - 2} ≤ 2^n-2(7) < 2^n-2(8) = 2ⁿ⁺¹

IOW, that a_n+1 ≤ 2ⁿ⁺¹.

 

[rtw528]

Thanks so much for your help.