Find the coefficient of $x^{31}$ in $(1+x+x^2+x^3+\ldots)^k$

Question

Find the coefficient of $x^{31}$ in $(1+x+x^2+x^3+\ldots)^k$, where $k$ is a natural number

Background: I have to use generating functions to do this

I have thought about using the product rule, defining $f(x)=1+x+x^2+x^3+\ldots$ and $g(x)=(f(x))^k$ but this doesn't seem too useful since I dont know the value of $k$, and even if I knew it, if it were a large number the process would be very tedious. Could someone help me please?

Answer 1

Since

$$\sum_{n\ge 0}x^n=\frac1{1-x}\;,$$

you’re interested in the coefficient of $x^{31}$ in

$$\frac1{(1-x)^k}=\sum_{n\ge 0}\binom{n+k-1}nx^n\;,\tag{1}$$

which is $\binom{30+k}{31}$. $(1)$ is a standard result easily proved by induction on $k$.

Answer 2

As Brian's solution is algebraic, here is a combinatorial proof: Let $m$ be a non-negative integer and $k$ be a positive integer. Then the coefficient of $x^m$ in the expansion of $$(1+x+x^2+x^3 +\cdots)^k$$ is the number of weak $k$-compositions of $m.$ This is the number of ways in which $m$ indistinguishable balls can be placed into $k$ distinguishable boxes such that empty boxes are allowed. By the sticks-and-stones method, this number is $\binom{m+k-1}{k-1}.$ So the answer is $$\binom{30+k}{k-1}=\binom{30+k}{31}.$$

Answer 3

If you imagine expanding the given product, all the terms that contribute to the coefficient of $x^{n}$ must come from exponents that sum up to $31$, so your coefficient will be the number of solutions $(a_1,a_2,\dots,a_k)$ to the equation $$a_1+a_2+\dots+a_k=n,$$ where each $a_i$ is an integer in $[0,n]\cap\mathbb Z$. This is a classic problem in combinatorics sometimes known as the "Stars and Bars" problem, whose answer is $$\binom{n+k-1}{n}.$$ See How to use stars and bars? for an explanation.