# Solve Recurrence Equation with Induction

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.

-
Thanks! However, I've been told this is not acceptable. Basically using base cases $T(0)$ and $T(1)$, realize that $c \geq a$, then prove by induction (we assume $T(k)$ is true for $k-1$ and $k-2$) for $k \geq 2$. You have to prove: $T(k) = c2^{k-1} + c2^{k-2} + b \leq c2^k$ I'm not sure what to do for this... You can't use the $1+2+...+2^{k-1} = 2^k - 1$ because of the $b$ term. All I can get is $c \geq\ (4b)/2^k$. – bauer2010 Jan 31 '14 at 15:14
To answer your comment, I have written out a detailed version of the answer. One could find a cheaper $c$, but the question did not ask for that. – André Nicolas Jan 31 '14 at 22:55