Induction problem: Tk+1 = Tk + Tk-1 + Tk-2

[Calley]

Homework Statement

Induktion problem seeming problematic

Relevant Equations

It says that we have sequence starting with T1, T2,T3...
and that Tk+1 = Tk + Tk-1 + Tk-2. it also says that T1=T2=T3=1. Then states that Tk<=2^k,
for all K= 1, 2 ,3....

I have come to the conclusion that the sequence is 1 1 1 3 5 9...

trying to do induktion and I get Tp+1=2^p+1, which means that 2^p +2p-1 + 2p-2 <=2^p+1 and this is not really solvable in any satisfactory way. What am I doing wrong?

 

[PeroK]

I'm not sure I understand where you are having the problem. Can you post what you are trying to do for the inductive step?

 

[Calley]

Step one Base it works for k=4.

Step two: If it works for k=4 it works for k=p

Step three: if it works for k=p it also works for k+1 =p+1

so Tp+1 <=2^p+1 ==> Tp + Tp-1 +Tp-2 <=2^p+1
==> 2^p + 2^p-1 +2^p-2 <=2^p+1

 

[PeroK]

Step two: If it works for k=4 it works for k=p

I don't understand this.

Step three: if it works for k=p it also works for k+1 =p+1

This is called the inductive step. Can you post your attempt at this step?

Although, it should be $k = p +1$.

 

[Calley]

I don't understand this.This is called the inductive step. Can you post your attempt at this step?

I fixed it a bit. pls check. it does state that Tk<=2^k not Tk<=2^k+1

 

[PeroK]

I fixed it a bit. pls check. it does state that Tk<=2^k not Tk<=2^k+1

Sorry, I missed this post, as I didn't get an alert.

Step one Base it works for k=4.

Step two: If it works for k=4 it works for k=p

Step three: if it works for k=p it also works for k+1 =p+1

so Tp+1 <=2^p+1 ==> Tp + Tp-1 +Tp-2 <=2^p+1
==> 2^p + 2^p-1 +2^p-2 <=2^p+1

You shouldn't start with what you want to prove. A lot of students seem to make this mistake and have the implication the wrong way round. You want to prove that $$T_{p} \le 2^p \ \Rightarrow \ T_{p+1} \le 2^{p+1}$$The inductive step, therefore, starts by assuming $T_{p} \le 2^p$.

 

[Calley]

Sorry, I missed this post, as I didn't get an alert.You shouldn't start with what you want to prove. A lot of students seem to make this mistake and have the implication the wrong way round. You want to prove that $$T_{p} \le 2^p \ \Rightarrow \ T_{p+1} \le 2^{p+1}$$The inductive step, therefore, starts by assuming $T_{p} \le 2^p$.

I have done that. Here is where I'm a bit lost. Not sure how to proceed.

Tp+Tp-1+Tp-2 =<2^p+1 ?

 

[PeroK]

I have done that. Here is where I'm a bit lost. Not sure how to proceed.

Tp+Tp-1+Tp-2 =<2^p+1 ?

I didn't see you do it! After you write the hypothesis for the inductive step. Assume:
$$T_{p} \le 2^p$$The next step is generally to calculate $T_{p+1}$. Therefore:
$$T_{p+1} = T_p + T_{p-1} + T_{p-2} \le \dots$$

 

[PeroK]

PS In this case there is actually a subtlely in the use of induction that you need to be aware of.

 

[Calley]

PS In this case there is actually a subtlely in the use of induction that you need to be aware of.

Tp + Tp-1+Tp-2 <= 2^p+1
2^p + 2^p-1 + 2^p-2 <= 2^p+1

what I am getting is 3p-3<=p+1 and i can't draw any conclusion here.

or switch the 2^p+1 into other parts on the right hand?

 

[PeroK]

Tp + Tp-1+Tp-2 <= 2^p+1
2^p + 2^p-1 + 2^p-2 <= 2^p+1

what I am getting is 3p-3<=p+1 and i can't draw any conclusion here.

To be honest, I haven't see any coherent mathematics from you yet. The statements you are writing are disjointed from each other and don't follow explicitly from what was previously assumed. In particular, you still seem to be working from the assumption that what you are trying to prove is true.

Induction is pure mathematics and in order to do a proof by induction, you must learn to get the correct flow of mathematical logic. Many students struggle with this. The mistakes you are making are very common. There's nothing wrong with struggling, but to make progress you need to try to understand how I am tackling the problem.

To recap, what we have (this is the level of work that will be expected from you):

1) By inspection $T_k < 2^k$ for $k = 1, 2, 3$.

2) Let $p \ge 3$, and assume $T_k \le 2^k$ for $k = 1, 2, \dots p$. Therefore:
$$T_{p+1} = T_p + T_{p-1} + T_{p-2} \le \dots$$

 

[docnet]

A template for writing proof by induction from my professor's notes (it has been really helpful to me) :

:)

 

[vela]

2^p + 2^p-1 + 2^p-2 <= 2^p+1

what I am getting is 3p-3<=p+1 and i can't draw any conclusion here.

We need to see your work, not just what you end up with. Frankly, I'm mystified how you ended up with $3p-3 \le p+1$.