Solve the recurrence relation $a_{r+2} - 3a_{r+1} + 2a_r = 0, a_0 = 1, a_1 =3$ using generating functions.
This problem comes from this website about discrete mathematics.
In the solution, the generating function $G(t)$ was defined as $\sum_0^\infty a_r t^r$. Multiplying the recurrence relation by $t^r$ results in $\sum_0^\infty a_{r+2} t^r - 3\sum_0^\infty a_{r+1} t^r + 2\sum_0^\infty a_r t^r =0$, so:
$$\frac{G(t) - a_0 - a_1 t}{t^2} - 3 \frac{G(t) - a_0}{t} + 2G(t)= 0 $$
and substituting the initial conditions, then factoring the denominator gives $G(t) = \frac{2-3t}{(1-t)(1-2t)}$.
Using partial fractions, where $G(t)$ is assumed to be in the form $\frac{A}{1-t} + \frac{B}{1-2t}$ tells us that $G(t) = \frac{1}{1-t} + \frac{1}{1-2t}$.
I get the solution all the way until this point. How do they jump from $\frac{1}{1-t} + \frac{1}{1-2t}$ to $a = 1 + 2^r$ ?
$$\frac{1}{1-t} = 1+t+t^2+t^3 + \cdots + t^r$$
represents the sequence: $1, 1, 1, 1 \cdots$
$$\frac{1}{1-2t} = 1+2t+(2t)^2+(2t)^3 + \cdots + (2t)^r$$
and what sequence does this represent?
Add the two sequences together to get your answer.