I am trying to solve the following Recurrence relation using substitution method and I am stuck almost half way. I know the answer is 2^n but I can't reach it.

At first, my question is: Who decicdes the base cases? when do we take T(n)=1 for n=1 or T(n)=1 for n=0?

The work I have done till now is as follows:

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

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

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

Thus, using these, we can subsitute and we get

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

T(n) = 3T(n-2) + 2T(n-3) (add and then substitue again)

T(n) = 5T(n-3) + + 6T(n-4)

Now assume we go till k, but I am not able to generalize the usage of k and find a correct assumption that will lead to a result of time complexity of Big O of 2^n

  • $\begingroup$ You decide the base cases – it's your recurrence. $\endgroup$ Oct 19, 2018 at 2:22

2 Answers 2


The secret of effective substitution is to find the magic numbers -1 and 2. Look and behold.

$$ T(n)+T(n-1)=2T(n-1)+2T(n-2)=2(T(n-1)+T(n-2))$$ Let $S(n)=T(n)-(-1)T(n-1)$. Then $$S(n)=2S(n-1)=2^2S(n-2)=\cdots=2^{n-2}S(2)\tag{I}$$

$$ T(n)-2T(n-1)=-T(n-1)+2T(n-2)=-(T(n-1)-2T(n-2))$$ Let $R(n)=T(n)-2T(n-1)$. Then $$R(n)=-R(n-1)=R(n-2)=\cdots=(-1)^nR(2)\tag{II}$$

Eliminating $T(n-1)$ from formula ($\text{I}$) and ($\text{II}$), we obtain $$T(n)= \frac{2S(n) + R(n)}3=\frac{2^{n-1}S(2) + (-1)^nR(2)}3=\frac{S(2)}62^n + O(1)$$

So, $T(n) = O(2^n)$.

It is assumed in the above that S(2) and R(2) are defined or, what is equivalent, T(2) and T(1) are defined. Their actual values do not affect the conclusion.

In fact, we can be more precise. If $T(2)+T(n-1)>0$, i.e., $S(2) > 0$, we will have $T(n)=\Theta(2^n)$. If $T(2)+T(n-1)=0$, we will have $T(n)=O(1)$. If $T(2)+T(n-1)<0$, we will have $-T(n)=\Theta(2^n)$.

How to find those two magic numbers?

Consider T(n) as $x^2$, T(n-1) as $x$ and T(n-2) as 1. Then you get $x^2 = x + 2$. Solving that equation, you get $x=-1$ or $x=2$.

(Exercise.) Let $F(n)=F(n-1)+F(n-2)$ for $n\in\Bbb N$, $n\ge2$. Show $F(n)= O(\alpha^n)$, where $\alpha = \frac{1+\sqrt 5}2$.

  • 1
    $\begingroup$ You're missing a $T$ in your first equation $\endgroup$ Oct 19, 2018 at 11:02
  • $\begingroup$ Corrected. Also added an exercise. $\endgroup$
    – John L.
    Oct 19, 2018 at 12:56
  • $\begingroup$ When you define R(n), on the rhs you should have R(2) instead of S(2). Also, could you expand a bit on how you picked 6T(n)=4S(n)+2R(n)? $\endgroup$
    – Maiaux
    Jan 7, 2019 at 10:57
  • 1
    $\begingroup$ @Maiaux, updated. $\endgroup$
    – John L.
    Jan 7, 2019 at 12:37

I like the method "try it out and see what happens".

Calculate the next items of the sequence starting with 0,1 and starting with 1,0. You will soon see a pattern. And from the pattern it is obvious that the solutions are

$a \cdot 2^n + b \cdot (-1)^n$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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