Solve the following recurrence relation:
$a_k=2 a_{k-1}+3a_{k-2}$ with $a_0=1$ and $a_1=2$.
I have expanded the recurrence relation:
$$a_k=2 (2 a_{k-2}+3 a_{k-3})+ 3(2 a_{k-3}+3 a_{k-4})= 2^2 a_{k-2}+ 2^2 \cdot 3 \cdot a_{k-3}+ 3^2 a_{k-4}= 2^3 a_{k-3}+ 3 \cdot 2^2 \cdot a_{k-4}+3 \cdot 2^3 a_{k-4}+ 3^2 \cdot 2^2 \cdot a_{k-5}+ 3^2 \cdot 2 a_{k-5}+3^3 a_{k-6}$$
Do we continue with the same way? Or is there an other way to solve the recurrence relation?
Also, is there an other way rather than the expansion of the terms and the use of the characteristic equation?
EDIT: Also suppose that we have to solve the recurrence relation
$$d_k=4 d_{k-2}, \text{ where } d_0=1 \text{ and } d_1=-1.$$
I have done the following:
\begin{align*}d_k=4d_{k-2}&=2^2d_{k-2} \\ &=2^2\left (2^2d_{(k-2)-2}\right )=2^4d_{k-4} \\ & =2^4\left (2^2d_{(k-4)-2}\right )=2^6d_{k-6} \\ & = 2^6\left (2^2d_{(k-6)-2}\right )=2^8d_{k-8} \\ & = \ldots \\ & = 2^id_{k-i}\ , \ \ i \text{ even}\end{align*}
If $k$ even, then at the last step we have for $i=k$ (since $k$ is the maximum even number $\leq k$) : $d_k=2^kd_{k-k}=2^kd_0=2^k$.
If $k$ odd, then at the last step we have for $i=k-1$ (since $k-1$ is the maximum even number $\leq k$) : $d_k=2^{k-1}d_{k-(k-1)}=2^{k-1}d_1=-2^{k-1}$.
How can we find the general form for the terms of the recurrence relation? Or do we distinguish cases when $k$ is even and odd?
I would use the characteristic equation method, it's quick and straightforward. The following is an ad hoc solution for this particular recurrence relation, just for fun. We have $$a_k=2a_{k-1}+3a_{k-2}$$ $$a_k+a_{k-1}=3a_{k-1}+3a_{k-2}$$ Now we can set $b_k=a_k+a_{k-1}$ and get $$b_k=3b_{k-1}\qquad b_1=a_1+a_0=3$$ Which implies $b_k=3^k$. Finally $$a_k=b_k-a_{k-1}\implies a_k=3^k-a_{k-1}\qquad a_0=1$$ $$a_k=3^k-3^{k-1}+3^{k-2}-\cdots+(-1)^k=(-1)^k\cdot\frac{(-3)^{k+1}-1}{(-3)-1}$$ $$a_k=\frac{3^{k+1}+(-1)^k}{4}$$