Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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 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 at 22:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.