Prove $T(n)=2F(n+1)-1$ by induction. Please read body for full question.

Question

Given : $F(n)=F(n-1)+F(n-2)$ with $F(0)=0$ and $F(1)=1$. $T(n)$ is the total number of calls needed to calculate $F(n)$ using top-down approach.

By writing top-down approach program, I have calculated $T(n)$ i.e., $T(n)=T(n-1)+2$ where $T(0)=T(1)=1$.

I want to prove $T(n)=2F(n+1)-1$ by induction. I'm unable to solve this. Can you please help me out with this proof?

Answer 1

I want to prove T(n)=2F(n+1)−1 by induction. I'm unable to solve this.

If you can't solve it by induction that's probably because it isn't true.

We define $T(n) = T(n-1) + 2$ and we are conjecturing that $T(n)=2F(n+1)-1$.

Presumable the first few base cases work.

So we attempt the induction step:

Assume $T(n)=2F(n+1) -1$. Then $T(n+1) = T(n) +2 = 2F(n+1) -1+2 = 2F(n+1) +1$.

We need to show that this is equal to $2F(n+2)-1$. But $2F(n+2)-1 = 2(F(n+1) +F(n))-1=2F(n+1) + (2F(n) -1)$.

So our induction step will only work if $2F(n) - 1 = 1$. Not only does our induction step not succeed. It actively fails.

So our conjecture can't be true.

If $T(n) = 2F(n+1) -1$ then $T(n+1) \ne 2F(n+2)-1$ unless $F(n) = 1$. Thus it works for our base cases and it works for $n=3$ (because for $n=2$ we have $F(2)=1$ so our induction steps works for $n+1=2+1 =3$) but it fails for $n\ge 4$.

Just do it. $T(0) = T(1)=1; T(2)=1+2 = 3; T(3)=3+2 = 5$; and $T(4)=5+2 =7$.

While $F(0) = 0; F(1)=1; F(2)=1; F(3)=2; F(4)= 3; F(5)=5$

So $2F(0+1)-1=1=T(0); 2F(1+1)-1=1=T(1); 2F(2+1)-1=3=T(2); 2F(3+1)-1=5 =T(3)$ but $2F(4+1)-1=9\ne 7 = T(4)$.