Question: Given the recurrence equation for the recursive Fibonacci sequence program:
$T(n) = T(n-1) + T(n-2) + b$
$T(0) = T(1) = a$
Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, \forall n \geq 0$. Find a value for $c$ in the process.
Attempt at a Solution:
Base case for n=0: $f(0) = c$, so you have the constraint $a \leq c$
Base case for n=1: $f(1) = 2c$, so you have the constraint $a \leq 2c$
Inductive step:
- $T(n) = T(n-1) + T(n-2) + b$
- $T(n+1) = T(n) + T(n-1) + b$
- $T(n+1) = c2^n + c2^{n-1} + b$
I'm not really sure where to go after this, nor am I really sure if what I've done so far is of any value whatsoever.
Calculate. We get $T(2)=2a+b$, $T(3)=3a+2b$, $T(4)=5a+4b$, $T(5)=8a+7b$, $T(6)=13a+12b$, and so on. The coefficients grow fast, but not too fast.
For simplicity assume that $a$ and $b$ are non-negative.
We show by induction that $T(n)\le 2^n a+2^n b=(a+b)2^n$. For the induction step, suppose that $T(k-1)\le 2^{k-1}(a+b)$ and $T(k-2)\le 2^{k-2}(a+b)$. We need to show that $T(k)\le 2^k(a+b)$.
To do this it is enough to show that $2^{k-1}+2^{k-2}+1\le 2^k$. This is not difficult, since $1+2+\cdots +2^{k-1}=2^k-1$.
Detail: Let $c=a+b$. Let $A(n)$ be the assertion that $T(n)\le (a+b)2^n$ and $T(n+1)\le (a+b)2^{n+1}$. It is clear that $A(0)$ holds. We show that if $A(k)$ holds, then $A(k+1)$ holds. So we need to show that $T(k+1)\le (a+b)2^{k+1}$ and $T(k+2)\le (a+b)2^{k+2}$.
It is built into $A(k)$ that $T(k+1)\le (a+b)2^{k+1}$. So it is enough to show that $T(k+2)\le (a+b)2^{k+2}$.
We have $T(k+2)=T(k+1)+T(k)+b$. By the induction hypothesis, $T(k+1)\le (a+b)2^{k+1}$ and $T(k)\le (a+b)2^k$. Thus $$T(k+2)\le (a+b)2^{k+1}+(a+b)2^k +b\le (a+b)2^{k+1}+(a+b)2^k +a+b.\tag{1}$$ Thus from (1) we get $$T(k+2)\le (a+b)(2^{k+1}+2^k+1).$$ But $2^{k+1}+2^k+1 \le 2^{k+2}$. It follows that $T(k+2)\le (a+b)2^{k+2}$. This completes the induction step.