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...
 A: 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*}
A: 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\,$.
A: A number of responses have provided correct solutions to your problem, but not to a more general one. I'll provide a solution for all such problems of the form $f_n=af_{n-1}+bf_{n-2}$ with $f(0)=f_0 \ \&\  f(1)=f_1$.
There have been many extensions of the sequence with adjustable (integer) coefficients and different (integer) initial conditions, e.g., $f_n=af_{n-1}+bf_{n-2}$. (You can look up Pell, Jacobsthal, Lucas, Pell-Lucas,  and Jacobsthal-Lucas sequences.) Maynard has extended the analysis to $a,b\in\mathbb{R}$, (Ref: Maynard, P. (2008), “Generalised Binet Formulae,” $Applied \ Probability \ Trust$; available at http://ms.appliedprobability.org/data/files/Articles%2040/40-3-2.pdf.)
We have extended Maynard's analysis to include arbitrary $f_0,f_1\in\mathbb{R}$. It is relatively straightforward to show that
$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{f_0}{2} (\alpha^n+\beta^n) $$
where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.
The result is written in this form to underscore that it is the sum of a Fibonacci-type and Lucas-type Binet-like terms. It will also reduce to the standard Fibonacci and Lucas sequences for $a=b=1 \ \text{and} \ f_0=0, f_1=1$.
So, specializing to your case, we can show that
$$T_n=\frac{3^n+(-1)^n}{2}$$
in agreement with the other responses, but leaving you with a method for all other such problems.
A: You can reduce what you have down to this:
$$T_k=2T_{k-1}+3T_{k-2}$$
You can use a process similar to the one that Binet used when deriving the explicit formula for the fibonacci sequence. First notice that as $n$ approaches infinity, these two ratios approach each other:
$$\frac{T_k}{T_{k-1}}\approx \frac{T_{k-1}}{T_{k-2}}$$
Let us denote the ratio that it approaches by $r$. Then we can say that for large $n$,
$$\frac{T_k}{T_{k-1}}\approx r$$
$$\frac{2T_{k-1}+3T_{k-2}}{T_{k-1}}\approx r$$
$$2+\frac{3T_{k-2}}{T_{k-1}}\approx r$$
$$2+\frac{3}{r}\approx r$$
$$2r+3\approx r^2$$
$$r^2-2r-3\approx 0$$
And, by the quadratic formula,
$$r\approx \frac{2\pm \sqrt{16}}{2}$$
$$r\approx 1\pm 2$$
Let us denote these two values of $r$ with
$$r_+=3$$
and
$$r_-=-1$$
Then we can express $T_k$ as
$$T_k=ar_+^k+br_-^k$$
Where $a$ and $b$ are some constants. Now, to solve for $a$ and $b$, we want to use the first two terms of our sequence; namely, $1$ and $1$, so that
$$1=ar_+^0+br_-^0$$
and
$$1=ar_+^1+br_-^1$$
Now we need only solve this system for $a$ and $b$. Let us simplify this to
$$a+b=1$$
$$3a-b=1$$
And we get $a=\frac{1}{2}$ and $b=\frac{1}{2}$. Then your final formula will be
$$T_k=\frac{1}{2}(3)^k+\frac{1}{2}(-1)^k$$
