Why is $\sum_{n=0}^{\infty}{ n+1 \choose n }x^{n} = \frac{1}{(1-x)^2}$ when computing recurrences with generating functions?

Question

Like the title says. I don't know how one gets from $G(x) = \frac{2}{1-2x} - \frac{1}{(1-x)^2}$ to $G(x) = 2\sum2^nx^n - \sum{n+1 \choose n}x^n$. I know this gives $a_{n} = 2^{n+1}-n-1$. I get the first term getting to $2^{n+1}$, but how does the second term work out? Moreover, what would $\frac{1}{(x-1)^2}$ or $\frac{1}{(x-1)^3}$? I don't know how to translate them when the quantity is raised to a power or when the 1 in the denominator is negative. Please help. Thank you

Answer 1

Answer

We have the following expression:

$$ \left(\sum_{i=0}^{\infty}x^{i}\right)^{2} = \sum_{a=0}^{\infty}\sum_{b=0}^{\infty}x^{a+b} $$

Now let's group the summands on the RHS based on the value of $a+b=n$ where $n\in\{0,1,2,...\}$. Using stars and bars, the number of integer solutions to $a+b=n$ is $\binom{n+1}{1}=\binom{n+1}{n}$. Therefore, the expression can be written as:

$$ \left(\sum_{i=0}^{\infty}x^{i}\right)^{2} = \sum_{n=0}^{\infty}\binom{n+1}{n}x^{n} $$

The LHS is equivalent to $\left(\frac{1}{1-x}\right)^{2}$

Generalization

$$ \left(\sum_{i=0}^{\infty}x^{i}\right)^{m} = \sum_{a_{1}=0}^{\infty} \sum_{a_{2}=0}^{\infty} ... \sum_{a_{m}=0}^{\infty} x^{a_{1}+a_{2}+...+a_{m}} $$

Again, using stars and bars, the number of integer solutions to $a_{1}+a_{2}+...+a_{m}=n$ is $\binom{n+m-1}{m-1}$. Therefore the expression is equivalent to:

$$ \left(\sum_{i=0}^{\infty}x^{i}\right)^{m} = \sum_{n=0}^{\infty}\binom{n+m-1}{m-1}x^{n} $$

The LHS is equal to $\left(\frac{1}{1-x}\right)^{m}$