https://brilliant.org/wiki/generating-functions-solving-recurrence-relations/
example 1
$a_{0} = 2$
$a_{n+1} = 3a_{n} , n\geq 0$
Let $G(x)$ be the generating function for the given sequence $\begin{Bmatrix} a_{n} \end{Bmatrix}$
$G(x) = a_{0} + a_{1}x + a_{2}x^2 + a_{3}x^3 + ..................$ $(1)$
$3x*G(x) = 3a_{0}x +3 a_{1}x^2 + 3a_{2}x^3 + 3a_{3}x^4 + ..................$ $(2)$
$1 - 2$
$(1-3x)*G(x) = a_{0} + (a_{1}-3a_{0})x +(a_{2} - 3 a_{1})x^2 + ..................$
since $a_{0} = 2$ and $a_{n+1} = 3a_{n}$ , we have
$(1-3x)*G(x) = a_{0} + (3a_{0}-3a_{0})x +(3a_{1} - 3 a_{1})x^2 + ..................$
$(1-3x)*G(x) = 2$
$G(x) = 2/(1-3x)$
$= 2[1 + (3x) + (3x)^2 + (3x)^3 + .................]$
$=2 + 6x + 18x^2 + .................$
example 2
If a+b+c+d=20, how many unique, non-negative integer solutions exist for (a,b,c,d)?
The variable $a$ contributes $[1 + x + x^2 + x^3 + .....................]$ , same for $b , c$ and $d$
So, the generating function G(x) = $[1 + x + x^2 + x^3 + .....................]*[1 + x + x^2 + x^3 + .....................]*[1 + x + x^2 + x^3 + .....................]*[1 + x + x^2 + x^3 + .....................]$
We need to find the coefficient of $x^{20}$ to get the result
$G(x) = (1/1-x)*(1/1-x)*(1/1-x)*(1/1-x)$
$G(x) = 1/(1-x)^4$
$G(x) = (1-x)^{-4}$
coefficient of $x^{20}$ is $\binom{4+20-1}{20}$ which is equal to $1771$
a. https://brilliant.org/wiki/negative-binomial-theorem/
b. http://mathworld.wolfram.com/NegativeBinomialSeries.html
