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$ – Yuval Filmus Oct 19 '18 at 2:22

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$.

| cite | improve this answer | |
  • 1
    $\begingroup$ You're missing a $T$ in your first equation $\endgroup$ – Daniel Martin Oct 19 '18 at 11:02
  • $\begingroup$ Corrected. Also added an exercise. $\endgroup$ – John L. Oct 19 '18 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 '19 at 10:57
  • 1
    $\begingroup$ @Maiaux, updated. $\endgroup$ – John L. Jan 7 '19 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$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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