Solving T(n)=T(n−1)+2T(n−2) using substitution

Question

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

Answer 1

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

Answer 2

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$