Solving Fibonacci recurrence relation

Question

I just started learn how to do data structure and algorithm and i think this is like one of the hardest subject i picked up as compared to doing programming. I have such a hard time understanding hence i do need a little help.

For example, how does this happened?

T(n) = T(n-1) + $n^4$

T(n) = (T(n-2) + $n^4$) + $n^4$

T(n) = ((T(n-3) + $n^4$) + $n^4$) + $n^4$

...

T(n) = (T(1)) + (n+1)$n^4$

T(n) is in the order of θ(1) + $n^5$ + $n^4$

After the 3rd line of T(n), how did the T(n) after that formulate?

Hence, without understanding that i got problem trying to solve this Fibonacci recurrence relation of

T(n) = 2T(n-1) + 1

By solving this, i should be able to get the upper bound and lower bound complexity of the algorithm. Hence, I did it by expanding them like this

T(0) = 2 //base condition

T(1) = 2 //base condition

T(n) = 2T(n-1) + c

T(n) = 2T(n-2) + c + c

T(n) = 2T(n-3) + c + c + c

....

T(n) = 2T(n-k) + kc

Then i'm stuck at this. Any assistance on that ?

Answer 1

In your first question (which, by the way, is slightly wrong), it's helpful to look at a recurrence relation like $$ T(n)=T(n-1)+n^4 $$ as $$ T(\fbox{stuff})=T(\fbox{stuff}-1)+\fbox{stuff}^4 $$ so, as you did, we have the following sequence of results: $$\begin{align} T(\fbox{n}) &= T(\fbox{n}-1)+\fbox{n}^4 = T(n-1)+n^4\\ &= \left[T(\fbox{n-1}-1)+\fbox{n-1}^4]\right]+n^4=T(n-2)+(n-1)^4+n^4\\ &= \left[T(\fbox{n-2}-1)+\fbox{n-2}^4]\right]+n^4=T(n-3)+(n-2)^4+(n-1)^4+n^4\\ \end{align}$$ where at each step, we're using the "stuff" formulation to replace $T(n)$, $T(n-1)$, $T(n-2)$ and so on. The idea here is that we have problems with the $T(.)$ terms on both sides of the inequality, so we want to drive the one on the right down to a constant. With a bit more work we obtain: $$\begin{align} T(n)&=T(n-1)+n^4\\ &=T(n-2)+(n-1)^4+n^4\\ &=T(n-3)+(n-2)^4+(n-1)^4+n^4\\ &=T(n-4)+(n-3)^4+(n-2)^4+(n-1)^4+n^4\\ \end{align}$$ Look at the terms in parentheses. It certainly appears that the general equation will be $$ T(n) = T(n-k)+(n-k+1)^4+(n-k+2)^4+(n-k+3)^4+\dotsm+n^4 $$ and, picking $k$ so that $n-k=1$ we get to the base case, $T(1)$, which presumably we know, so we have $$ T(n)=T(1)+2^4+3^4+4^4+5^4+\dotsm+n^4=\Theta(n^5) $$

---

The second relation, $T(n)=2T(n-1)+1$ (not a Fibonacci relation, BTW) we can do pretty much what we did before: $$\begin{align} T(n)&=2T(n-1)+1\\ &=2\left[2T(n-2)+1\right]+1 &\text{expanding $T(n-1)$}\\ &\quad=2^2T(n-2)+2+1\\ &=2^2\left[2T(n-3)+1\right]+2+1 &\text{expanding $T(n-2)$}\\ &\quad=2^3T(n-3)+4+2+1\\ &=2^3\left[2T(n-3)+1\right]+2+1 &\text{expanding $T(n-3)$}\\ &\quad=2^4T(n-3)+8+4+2+1 \end{align}$$ Now it should be pretty easy to spot the pattern and do essentially what we did above to get the closed form for $T(n)$. I'll leave that part to you.

---

For completeness, I should mention that there are gaping holes in the above. The general forms we guessed in both problems are just that, guesses. To be thorough, we should prove them correct, typically by induction.

Answer 2

Hint

Actually, you are not having the right understanding. One way to deal with your question is:

$$T(n)=2T(n-1)+c\quad(1)$$

then

$$T(n+1)=2T(n)+c\quad(2)$$

so $(2)-(1)$

$$T(n+1)-T(n)=2(T(n)-T(n-1))$$

now call $a(n)=T(n)-T(n-1)$ then you get

$$a(n+1)=2a(n)$$

which is a geometric sequence.

and also

$$\sum_{i=1}^{n}a(i)=T(n)-T(0)$$

Can you finish?

Answer 3

Problems of this type, say $T_n=AT_{n-1}+B$, which I call a short Fibonacci sequence, can be converted to a generalize Fibonacci form, i.e., $f_n=af_{n-1}+bf_{n-2}$, as follows

$$T_n=AT_{n-1}+B\\ T_{n-1}=AT_{n-2}+B$$

so that eliminating $B$ we get

$$T_n=(A-1)T_{n-1}-AT_{n-2}$$

Going through a formal derivation of the generalized Fibonacci sequence, as described here, we can show that

$$T_n=\frac{[(A-1)T_0+B]A^n-B}{A-1}$$

This gives us a solution, once and for all such short Fibonacci sequences. In the present case, we have $A=2,~B=1$, so that

$$T_n=[T_0+1]2^n-1$$

I have verified these results numerically.