Find an explicit expression for the general term of a recurrence relation

Find the formula for the $k$-th term in terms of $k$. $$T(0) = T(1) = 1, T(k+2) = 2T(k+1) + 3T(k)$$

First I rearranged the relation: $$T(k) = \frac{T(k+2)-2T(k+1)}{3}$$

I am not sure where to go from here...


Assume $T(k)= \lambda^k$ ... this give $\lambda^2-2\lambda-3=0$ which has roots $\lambda=-1,3$. So the general solution will be a linear combination of these ... \begin{eqnarray*} T(k)=A(-1)^k+B3^{k} \end{eqnarray*} $A $ & $ B$ are easily found from the initial conditions to be $A=B= \frac{1}{2}$ So the solution is \begin{eqnarray*} T(k)=\frac{(-1)^k+3^{k}}{2}. \end{eqnarray*}


Hint (assuming no knowledge of the standard methods to solve linear homogeneous recurrences):

$$T(k+2) = 2T(k+1) + 3T(k) \;\;\iff\;\; T(k+2)+T(k+1)=3\big(T(k+1) + T(k)\big)$$

With $U(k)=T(k)+T(k-1)\,$:

$$U(k+2) = 3 \cdot U(k+1) = 3^2 \cdot U(k) = \cdots = 3^{k+1} \cdot U(1) = 3^{k+1}$$

This reduces the problem to solving the (simpler) recurrence $\;T(k+1)=-T(k) + 3^k\,$.