0
$\begingroup$

This question already has an answer here:

I can't figure out how to solve this recurrence relation using the iteration method:

$$T(n) = \begin{cases} 0, & \text{if $n=0$} \\ 1, & \text{if $n=1$} \\ 3T(n-1)+ 4T(n-2), & \text{if $n >1$} \end{cases}$$

$\endgroup$

marked as duplicate by Raphael Nov 17 '14 at 11:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

Hint: Let $S(n) = T(n+1) + T(n)$. We have $S(0) = 1$, and for $n > 0$, $$ S(n) = T(n+1) + T(n) = [3T(n) + 4T(n-1)] + T(n) = 4(T(n) + T(n-1)) = 4S(n-1). $$ Can you take it from here?

$\endgroup$

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