Solve by using substitution method $T(n) = T(n-1) + 2T(n-2) + 3$ given $T(0)=3$ and $T(1)=5$ 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?

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