Solve by using substitution method $T(n) = T(n-1) + 2T(n-2) + 3$ given $T(0)=3$ and $T(1)=5$

Question

I'm stuck solving by substitution method:

$$T(n) = T(n-1) + 2T(n-2) + 3$$ given $T(0)=3$ and $T(1)=5$

I've tried to turn it into homogeneous by subtracting $T(n+1)$:

$$A: T(n) = T(n-1) + 2T(n-2) + 3$$ $$B: T(n+1) = T(n) + 2T(n-1) +3$$

$$A - B = T(n) - T(n+1) = T(n-1) + 2T(n-2) + 3 - (T(n) + 2T(n-1) + 3)$$

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

Assume $T(n) = x^{n}$

$$2x^{n} - x^{n+1} - x^{n-1} + 2x^{n-2} = 0$$

Dividing each side by $x^{n-2}$ leaves me with the impossible (beyond the scope of this class) equation:

$$2x^2 - x^3 - x + 2 = 0$$

How can I solve this using substitution method?

Answer 1

suppose we look for a constant solution $t_n = a.$ then $a$ must satisfy $a = a+2a + 3.$ we pick $a = -3/2.$ make a change a variable $$a_n = t_n + 3/2, t_n = a_n - 3/2.$$ then $a_n$ satisfies the recurrence equation $$a_n= a_{n-1}+ 2a_{n-2}, a_0 = 9/2, a_1=13/2.$$ now look for solutions $$a_n = \lambda^n \text{ where }\lambda^2-\lambda - 2 = 0\to \lambda = 2, -1$$ the solution is $$a_n = c2^n + d(-1)^n, c+d = 9/2, 2c-d = 13/2$$ which gives you $$c = 11/3, d = 5/6.$$ finally $$t_n = \frac{11}3\, 2^n +\frac 56 \, (-1)^n -\frac32. $$

Answer 2

Hints

Suppose $T(n) = \alpha$ for some constant $\alpha$. You will see that for a particular value $ T(n) = \alpha $ will be a particular solution to the equation (maybe this is what is meant by method of substitution).

Now solve the homogeneous equation $ T(n) - T(n- 1) - 2 T(n - 2) = 0 $ and find its general solution $ f(t) $. Then the general solution to you equation will be $ f(t) + \alpha $ where $ \alpha $ is the particular solution found above.