How can I solve this linear recursion? Let be $a_{0}=1,a_{1}=1,a_{n}=4a_{n-1}-2a_{n-2}$ if($n\ge 2)$ Should I first find the generating function of the recursion and after that? I solved it with Wolfram Alpha and after it the result is $\frac{1}{4}(2(2-\sqrt{2})^n +\sqrt{2}(2-\sqrt{2})^n+2(2+\sqrt{2})^n-\sqrt{2}(2+\sqrt{2})^n)$
I don't see the way how can I get this result.
 A: Solve the characteristic equation $r^2-4r+2=0$ to get $r_1=2-\sqrt{2}$ and $r_2=2+\sqrt{2}$. Then the general solution is $a_n=A (2-\sqrt{2})^n+B(2+\sqrt{2})^n$. 
For $n=0$you have $1=a_0=A+B$.
For $n=1$ you have $1=a_1=A(2-\sqrt{2})+B(2+\sqrt{2})$. 
From these two equations you will get $A$ and $B$.
A: I like to start by modifying the recurrence so that it’s valid for all $n\ge 0$ on the assumption that $a_n=0$ for $n<0$; this makes the manipulation of the infinite series a little simpler. In this case the result is
$$a_n=4a_{n-1}-2a_{n-2}+[n=0]-3[n=1]\;,\tag{1}$$
where the last two terms are Iverson brackets chosen to make sure that $a_0=a_1=1$. Now multiply $(1)$ by $x^n$ and sum over $n\ge 0$; if $g(x)=\sum_{n\ge 0}a_nx^n$ is the generating function, the result is
$$\begin{align*}
g(x)&=4\sum_{n\ge 0}a_{n-1}x^n-2\sum_{n\ge 0}a_{n-2}x^n+1-3x\\
&=4x\sum_{n\ge 0}a_{n-1}x^{n-1}-2x^2\sum_{n\ge 0}a_{n-2}x^{n-2}+1-3x\\
&=4xg(x)-2x^2g(x)+1-3x\;.
\end{align*}$$
Solving this for $g(x)$, we find that
$$g(x)=\frac{1-3x}{1-4x+2x^2}\;.$$
The next step is to expand this in partial fractions, which requires factoring the denominator. Suppose that $1-4x+2x^2=(1-\alpha x)(1-\beta x)$; then $\alpha+\beta=4$ and $\alpha\beta=2$, and it’s not hard to solve to find that $\alpha=2+\sqrt2$ and $\beta=2-\sqrt2$. Thus,
$$g(x)=\frac{A}{1-\alpha x}+\frac{B}{1-\beta x}$$
for some constants $A$ and $B$. Solve for $A$ and $B$. At that point you'll have
$$\begin{align*}
g(x)&=A\sum_{n\ge 0}(\alpha x)^n+B\sum_{n\ge 0}(\beta x)^n\\
&=\sum_{n\ge 0}\left(A\alpha^n+B\beta^n\right)x^n
\end{align*}$$
and can conclude that $a_n=A\alpha^n+B\beta^n$ for $n\ge 0$.
