Is there some strategy to find the general term of a recursive sequence? Given $(a_{n})_{n \in \mathbb{N}}$,
$a_{0} = 2, a_{1} = 4, a_{n+2} = 4a_{n+1} - 3a_{n}$, 
is there any way to find the general term? I reckoned that every $a_{i}$ is a factor of 2, and then the series becomes 1, 2, 5, 14, 41, ..., and obviously that's $a_{i} = 3(a_{i-1}) - 1$ (if $i≠0$) but even then I just can't get rid of these damn recursive clauses.
Any help? Is there some way to tackle this kind of problems?
 A: Yes! Consider a second order linear recurrence relation:
$$a_n = b a_{n-1} + c a_{n-2}.$$
The standard method is to consider the characteristic equation:
$$r^2 = br + c.$$
Find the roots of this equation (using the quadratic formula, for example). If it has two different (possibly complex) roots $r_1, r_2$, then the recurrence relation has the general solution
$$a_n = Ar_1^n + Br_2^n,$$
where $A, B$ are constants determined by your initial values. When you get a repeated root $r$, the solution becomes instead
$$a_n = (An + B)r^n.$$
So, in your case, your characteristic equation becomes
$$r^2 = 4r - 3 \iff r^2 - 4r + 3 = 0 \iff (r - 3)(r - 1) = 0 \iff r = 1 \text{ or } 3,$$
so your general solution is
$$a_n = A1^n + B3^n = A + 3^n B.$$
Since $a_0 = 2$, $2 = A + B$. Since $a_1 = 4$, $4 = A + 3B$. Solving simultaneously yields $A = B = 1$, so the solution is $a_n = 1 + 3^n$.
On the other hand, if you have a good guess at a general solution (from computing terms, and noting that they seem to be powers of $3$ with $1$ added to them), then you can always prove the formula true using induction.
A: Yes, there is. Usually, you try a particular form of solution - $a_n=A\cdot p^n$ where $A$ and $p$ are constants. You can determine which values $p$ can take from the difference equation, and you can work out the corresponding values of $A$ with the initial conditions. Since this is a second order equation, you should get $$a_n=A_1 {p_1}^n+A_2{p_2}^n$$ for some specific numbers $A_1,A_2,p_1,p_2$.
A: Writing each pair of consecutive terms as a linear combination of the previous pair of consecutive terms,
$$\pmatrix{a_{n}\\a_{n-1}} = \pmatrix{4&-3\\1&0}\pmatrix{a_{n-1}\\a_{n-2}}= \cdots = \pmatrix{4&-3\\1&0}^{n-1}\pmatrix{a_{1}\\a_{0}}$$
The question becomes how to represent the matrix power in close form, which is by diagonalisation.
$$\begin{align*}
\pmatrix{4-\lambda&-3\\1&0-\lambda} &= 0\\
(4-\lambda)(-\lambda) +3 &= 0\\
(\lambda-3)(\lambda-1) &= 0
\end{align*}$$
(This characteristic equation has the same roots as the ones given in the other answers.)
For $\lambda = 3$, $$\pmatrix{4&-3\\1&0}\pmatrix{3\\1} = 3\pmatrix{3\\1}$$
For $\lambda = 1$, $$\pmatrix{4&-3\\1&0}\pmatrix{1\\1} = \pmatrix{1\\1}$$
So
$$\begin{align*}
\pmatrix{4&-3\\1&0}^{n-1} &= \pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{3&1\\1&1}^{-1}\\
&= \frac12\pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{1&-1\\-1&3}\\
a_n &= \pmatrix{1&0}\pmatrix{a_{n}\\a_{n-1}}\\
&= \pmatrix{1&0}\pmatrix{4&-3\\1&0}^{n-1}\pmatrix{a_{1}\\a_{0}}\\
&= \pmatrix{1&0}\pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{3&1\\1&1}^{-1}\pmatrix{4\\2}\\
&= \pmatrix{1&0}\pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{1&-1\\-1&3}\pmatrix{2\\1}\\
&= \pmatrix{3&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{1\\1}\\
&= 3^n+1
\end{align*}$$
A: The various solutions here suggest & show how to use the linear homogeneous recursive algorithm to solve
$$a_{n+2} = 4a_{n+1} - 3a_{n} \tag{1}\label{eq1}$$
This is generally the best way to proceed. Nonetheless, you can also use the method suggested in the answer by Theo Bendit. Consider first trying a few values to see if you can find any pattern. You are given that $a_0 = 2$ and $a_1 = 4$, so $a_2 = 4(4) - 3(2) = 10$. You've checked additional terms to notice that, when dividing by $2$, each term is $a_{i+1} = 3a_i - 1$. With the factor of $2$, it becomes $a_{i+1} = 3a_i - 2$. This suggests using something close to a power of $3$. You may then notice that $a_n = 3^n + 1$ works for all these values. To prove this works for all $n$, you can use induction. It's already been shown to work for $n \le 2$. Consider it's true for all $n \le k$ for some integer $k \ge 2$. Then from \eqref{eq1}, you get that
\begin{align}
a_{k + 1} &= 4a_k - 3a_{k-1} \\
&= 4\left(3^k + 1\right) - 3\left(3^{k-1} + 1\right) \\
&= 4\left(3^k\right) + 4 - 3^k - 3 \\
&= 3\left(3^k\right) + 1 \\
&= 3^{k+1} + 1 \tag{2}\label{eq2}
\end{align}
It's also true for $n = k + 1$, thus completing the inductive procedure to show that
$$a_n = 3^n + 1 \tag{3}\label{eq3}$$
