Generating function to find $a_n$ formula Use generating function to find formula of $a_n$. 
Given $a_0 = 1$, $a_1 = 2$, and $a_n = 2a_{n - 1} - a_{n - 2}$ for $n \geq 2$
Let $G(x) = \sum_{n \geq 0}a_nx^n$. Multiply both sides of $a_n = 2a_{n - 1} - a_{n - 2}$ by $x^n$ and sum over all $n$ for recurrence holds, that's for $n \geq 2$. We get $$\sum_{n \geq 2}a_nx^n = 2 \sum_{n \geq 2}a_{n - 1}x^n - \sum_{n \geq 2}a_{n - 2}x^n$$.
Manipulate each term we got, $$\underbrace{\sum_{n \geq 2}a_nx^n + a_1x + a_0}_{=G(x)} -a_1x - a_0  = 2x(\underbrace{\sum_{n \geq 2}a_{n - 1}x^{n - 1} + a_0}_{G(x)} - a_0) - x^2\sum_{n \geq 2}a_{n - 2}x^{n - 2}$$
Simplify, we got $$G(x) - 2x - 1 = 2x(G(x) - 1) - x^2G(x)$$ 
 Solve for $G(x)$, $$G(x) = 2xG(x) - 2x + 2x - x^2G(x) + 1$$
$$G(x)(x^2 - 2x + 1) = 1$$
$$G(x) = \frac{1}{x^2 - 2x + 1} = \frac{1}{(x -  1)^2}$$
I'm stuck here because it doesn't look like we can do partial fraction to find the coefficient $A$ and $B$, in fact, I think this is already in the form of partial fraction, however, I'm not sure how to generate a power series from here. Any suggestion?
 A: $\dfrac1{(x-1)^2}=1+2x+3x^2+...$

Without generating function, you could say $a_n-a_{n-1}=a_{n-1}-a_{n-2}$, 
so by induction $a_n-a_{n-1}=a_1-a_0=1,$
so $a_n-a_{n-1}+a_{n-1}-a_{n-2}+...+a_1-a_0=a_n-a_0=n$, so $a_n=n+1$.
A: And if you believe that
the binomial theorem
works for any exponent:
$\begin{array}\\
\dfrac1{(1-x)^m}
&=(1-x)^{-m}\\
&=\sum_{n=0}^{\infty} \binom{-m}{n}(-1)^nx^n\\
&=\sum_{n=0}^{\infty} (-1)^nx^n\dfrac{\prod_{k=0}^{n-1}(-m-k)}{n!}\\
&=\sum_{n=0}^{\infty} (-1)^nx^n(-1)^n\dfrac{\prod_{k=0}^{n-1}(m+k)}{n!}\\
&=\sum_{n=0}^{\infty} x^n\dfrac{\prod_{k=0}^{n-1}(m+n-1-k)}{n!}\\
&=\sum_{n=0}^{\infty} x^n\dfrac{\prod_{k=0}^{n-1}(m+n-1-k)\prod_{k=n}^{m+n-2}(m+n-1-k)}{n!\prod_{k=n}^{m+n-2}(m+n-1-k)}\\
&=\sum_{n=0}^{\infty} x^n\dfrac{\prod_{k=0}^{m+n-2}(m+n-1-k)}{n!\prod_{k=1}^{m-1}(m-k)}\\
&=\sum_{n=0}^{\infty} x^n\dfrac{\prod_{k=1}^{m+n-1}k}{n!\prod_{k=1}^{m-1}k}\\
&=\sum_{n=0}^{\infty} x^n\dfrac{(m+n-1)!}{n!(m-1)!}\\
&=\sum_{n=0}^{\infty} x^n\binom{m+n-1}{n}\\
\end{array}
$
A: You know that $\frac1{1-x}=\sum_{n\ge 0}x^n$; now take the derivative.
There is in fact a more general result:
$$\frac1{(1-x)^{k+1}}=\sum_{n\ge 0}\binom{n+k}n x^n=\sum_{n\ge 0}\binom{n+k}k x^n.$$
In your case $k=1$.
