1
$\begingroup$

This is my question:

Given $n$ and $k$, find the coefficient of $x^n$ in $(1+x+x^2+x^3+\cdots)^k$

The largest term needed in each block is $n-k+1$, and that's all I have figured out. I'm guessing the answer includes $n-k+1$ choose something.

I don't even know if I can solve this, but any help would be appreciated!

2 Answers 2

2

One failproof way of doing this using the generating function:

$\frac{1}{1-x}=1+x+x^2+\ldots$

So you are interested in the $n$'th coefficient of $1/(1-x)^k$ which amounts to taking $n$ derivatives and evaluating at $x=0$, then multiplying by 1/n!:

$\frac{1}{n!}\left.\frac{d^n }{dx^n}(1-x)^{-k}\right|_{x=0}=\frac{1}{n!}k(k+1)\cdots (k+n-1)=\frac{(k+n-1)!}{n!(k-1)!}$

Gee, that looks awfully like $\binom{k+n-1}{n}$ (or $\binom{k+n-1}{k-1}$ depending on your tastes)... Perhaps that will give you a hint of a direct combinatorics approach.

1

We have

$(1+x+x^2+x^3+\cdots)^k = (1+x+x^2+ \cdots) (1+x+x^2 + \cdots)\cdots(1+x+x^2+ \cdots)$

where there are $k$ of the $(1 + x + x^2 + \cdots)$.

To form the term $x^n$, we need to pick $\displaystyle x^{j_i}, 1 \leq i \leq k$ from each of the $k$ factors, such that $j_1 + j_2 + j_3 + \cdots + j_k = n$. This is a partition of $n$ into $k$ parts. The number of ways to do this is known to be $\displaystyle {n+k-1 \choose k-1}$.