Solve a recursion using generating functions? Given the recursive equation : 
$$F_n+F_{n-1}+⋯+F_0=3^n  , n\geq0$$
A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get : 
$$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1}  $$
Now subtracting both equations : 
$$F_n+F_{n-1}+⋯+F_0 - (F_{n-1}+F_{n-2}+⋯+F_0) = 3^n - 3^{n-1}  $$
$$ F_n = 3^n - 3^{n-1}$$
But how can I do that using generating functions ? any hints ? 
Thanks 
 A: Define $f(z):=\sum F_n z^n$ and $g(z):=\sum z^n=\frac{1}{1-z}$. You can see $\sum_{k=0}^{n}F_k$ as the coefficient of $f(z)g(z)$ in the $n$-th term. So we get $$f(z)g(z)=\sum_{k=0}^{\infty}3^nz^n.$$
From this we get $f(x)=\frac{1-z}{1-3z}=\frac{1}{3}+\frac{2}{3}\frac{1}{1-3z}=1+\sum_{k=1}^{\infty}\frac{2}{3}3^kz^k$. The coefficient of this is your F_n.
The way to think about these two functions $f$ and $g$ is to write $$\sum_{k=0}^{n}F_k$$ as $$\sum_{k=0}^{n}F_{k}G_{n-k}$$ which is a the coefficient of a product of two series. In this case we need $G_k=1$. That is why the two functions should be the $f$ and $g$ above.
So, yes, you multiply both sides by $z^n$ (or $z^{-n}$, or sometimes $z^n/n!$, or $z^n/n$, it depends on the recurrence the generating functions that are going to be useful) sum for all $n$. On both sides you get some series. The trick is to write them in terms of known functions and $f(z)$. There are some known operations on series that have easy translations into operations on the function. See here.
There is also this very good, and free(!) book.
