Use generating functions to solve recurrence equation. Let $a_0=1, a_1=1$.  Use generating functions to solve recurrence equation $a_{n+2}= a_{n+1} + 2a_n$ for $n \geq0$
I have no idea how to solve this, any help is appreciated.
 A: The method of generating functions associate to your sequence the (formal) power series
 $$ f(x)=\sum_{n=0}^\infty a_n x^n. $$
Note that $\displaystyle\frac{f(x)-a_0}x=\sum_{n=0}^\infty a_{n+1}x^n$, so in the case that concerns us,
 $$ 2f(x)+\frac{f(x)-a_0}x=\sum_{n=0}^\infty (2a_n+a_{n+1})x^n=\sum_{n=0}^\infty a_{n+2}x^n=\frac{f(x)-a_0-a_1x}{x^2}. $$
This means that $$ 2x^2f(x)+xf(x)-a_0x=f(x)-a_0-a_1x. $$
Since $a_0=a_1=1$, this simplifies to 
 $$ f(x)=\frac1{1-x-2x^2}. $$
The point of this is that we can actually find the power series associated to this function, and therefore obtain a formula for the $a_n$. In this case, using the method of partial fractions, we find that 
 $$ f(x)=\frac{\frac13}{1-(-x)}+\frac{\frac23}{1-2x}, $$
and we can expand this using that $\displaystyle\sum_{n=0}^\infty (rx)^n=\frac1{1-rx}$ for any $r$. We get
 $$ f(x)=\frac13\sum_{n=0}^\infty(-x)^n+\frac23\sum_{n=0}^\infty(2x)^n=\sum_{n=0}^\infty\left(\frac{(-1)^n+2^{n+1}}3\right)x^n, $$
so $$ a_n=\frac{(-1)^n+2^{n+1}}3. $$
(Naturally, you can verify that this works, as the formula gives you that $a_0=a_1=1$ and $a_{n+2}=a_{n+1}+2a_n$.)
Some comments: The manipulation is purely formal, that is, we do not need to worry about establishing that the series converge in some interval. In this case they do, but one can operate purely algebraically without worrying about it. A good introductory reference for these matters is Formal power series, by Ivan Niven, winner of the 1970 Lester R. Ford award for outstanding exposition.
Note that the denominator of the rational function we obtained is $1-x-2x^2$. If $a_{n+2}=\alpha a_{n+1}+\beta a_n$, the denominator would have been $1-\alpha x-\beta x^2$. The numerator in this case was $1$. If $a_{n+2}=\alpha a_{n+1}+\beta a_n$, it would have been $a_0+(a_1-a_0\alpha)x$. It follows that the general formula for $a_n$ has the form $Ar^n+Bs^n$ where $r\ne s$ are the roots of the quadratic $1-\alpha x-\beta x^2$ and $A,B$ are some constants. If the quadratic has repeated roots (that is, if $r=s$), this changes slightly to $(A+Bn)r^n$. Similar results hold for recurrences with more terms. 
Other (formal) approaches are possible. For example, we could consider instead the exponential generating series, $$ f(x)=\sum_{n=0}^\infty \frac{a_n}{n!}x^n. $$
In this case, we have $$f'(x)=\sum_{n=0}^\infty\frac{a_{n+1}}{n!}x^n $$ and $$ f''(x)=\sum_{n=0}^\infty\frac{a_{n+2}}{n!}x^n, $$
and identifying $f$ becomes now a matter of solving a linear differential equation. Now $f$ is a linear combination of exponentials $e^{rx}$ and $e^{sx}$ with $r,s$ as before.
Another approach uses linear algebra: There is a matrix $A$ (with constant coefficients) that transforms $(a_n\, a_{n+1})^T$ into $(a_{n+1}\, a_{n+2})^T$. ($T$ indicates transpose.) The numbers $r,s$ now correspond to the roots of the characteristic polynomial of $A$. The formula for the $a_n$ is obtained from a formula for $A^n$, which can be obtained from its Jordan canonical form.
A: Let $$g(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots,$$ $$-xg(x)=-a_0x-a_1x^2-a_2x^3-\cdots-a_nx^{n+1}-\cdots,$$ $$-2x^2g(x)=-2a_0x^2-a_1x^3-a_2x^4-\cdots-a_nx^{n+2}-\cdots.$$ Adding these three sums gives us $$(1-x-2x^2)g(x)=a_0+(a_1-a_0)x+(a_2-a_1-2a_0)x^2+\cdots.$$ Since $a_0=1$, $a_1=1$, $a_2=3$ and so on, we see that $$(1-x-2x^2)g(x)=1$$ and so $$g(x)={1\over (1-x-2x^2)}={1\over (1+x)(1-2x)}.$$ Using partial fraction decomposition we have $${1\over (1+x)(1-2x)}={A\over 1+x}+{B\over 1-2x}.$$ So Solving for $A$ and $B$ we obtain $A={1\over 3}$ and $B={2\over 3}$. This gives us $${1\over 3}\cdot{1\over 1-(-x)}+{2\over 3}\cdot{1\over 1-2x}.$$ Using the geometric series we have $${1\over 3}\sum_{n=0}^\infty(-1)^nx^n+{2\over 3}\sum_{n=0}^\infty(-2)^nx^n.$$ Thus $$a_n={1\over 3}(-1)^n+{2\over 3}(-2)^n.$$
A: The method of using generating functions to solve recurrence relations can be found in the following link. 
http://faculty.tru.ca/smcguinness/M270F11/M270F11notes3.pdf
Look at some examples and I am sure you'll quickly figure out that out. 
