How to find the closed form of the following generating function?

Question

$$\sum_{m\geq0}\big[\sum_{k=0}^n \binom{k}{m}\big]z^m $$

It is supposed to be $$\frac{(x+1)^{n+1}-1}{x}$$ according to Mathematica.

How is it solved?

Answer 1

Rearrange across terms so you are considering a fixed $k$ rather than a fixed $m$ in the secondary sum (can be done, because we find that actually only finitely many terms are non-zero).

You end up getting, for each $k$, the sum $$ \sum_{m \geq 0} \binom km x^m. $$

But $\binom km = 0$ whenever $m > k$. So you get $$ \sum_{m = 0}^k \binom km x^m $$ which is just the binomial expansion of $(x + 1)^k$.

So your whole sum becomes $$ \sum_{k = 0}^n (x + 1)^k $$ but this is just the truncated power series, which satisfies $$ (x+1)^{n+1} - 1 = ((x+1) - 1) \sum_{k = 0}^n (x+1)^k $$

So your sum is equal to $$ \frac{(x+1)^{n+1} - 1}{(x+1) - 1} = \frac{(x+1)^{n+1} - 1}{x} $$