Exercise 1603Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Generating function for binomial coefficients

#generating function#binomial#formal power series

Statement

Compute $\sum_{n\ge0}\binom{n}{k}x^n$ for fixed $k$ .

Hint

$\binom{n}{k}$ is zero for $n<k$ . The generating function is $x^k/(1-x)^{k+1}$ .

Show solutionHide solution

Solution

Known. $\sum_{n\ge0}\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}$ .

Derivation. Start from $\sum_{m\ge0}x^m=\frac{1}{1-x}$ , differentiate $k$ times and divide by $k!$ : $\sum_{m\ge k}\binom{m}{k}x^{m-k}=\frac{1}{(1-x)^{k+1}}$ . Substitute $m=n$ , multiply by $x^k$ .

Conclusion. $\sum_n\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}$ .

Generating function for binomial coefficients

Statement

Solution

More problems in Counting principles