Section 7.2.1.4: Generating All Partitions

Exercise 30. [M17] [M17] Find closed forms for the sums (a)  k≥0 n −km m −1  and (b)  k≥0  n m −k  (which are finite, because the terms being summed are zero when k is large).

Verified: no
Solve time: 14m41s

---

Solution

Let $m \ge 1$ and $n \ge 0$. Throughout, the binomial coefficient $\left|\begin{matrix} a \ b \end{matrix}\right|$ is $\binom{a}{b}$, interpreted as $0$ when $b<0$ or $b>a$.

(b)

Consider

$$ \sum_{k \ge 0} \binom{n}{m-k}. $$

The term $\binom{n}{m-k}$ is nonzero only when $0 \le m-k \le n$, hence only $k=0,1,\dots,m$ contribute. Set $j=m-k$. Then $j$ runs from $m$ down to $0$, and the sum becomes

$$ \sum_{j=0}^{m} \binom{n}{j}. $$

No further reduction is possible in elementary binomial form without additional constraints on $m$ relative to $n$.

Thus

$$ \boxed{\sum_{k \ge 0} \binom{n}{m-k} = \sum_{j=0}^{m} \binom{n}{j}}. $$

(a)

Consider

$$ S(n) = \sum_{k \ge 0} \binom{n-km}{m-1}. $$

The summand is nonzero only when $m-1 \le n-km$, hence $k \le \left\lfloor \frac{n-(m-1)}{m} \right\rfloor$, so the sum is finite.

Define the ordinary generating function

$$ F(x) = \sum_{n \ge 0} S(n) x^n. $$

Then

$$ F(x) = \sum_{n \ge 0} \sum_{k \ge 0} \binom{n-km}{m-1} x^n. $$

Interchange summations and substitute $n = n' + km$:

$$ F(x) = \sum_{k \ge 0} \sum_{n' \ge 0} \binom{n'}{m-1} x^{n'+km}. $$

This factorizes as

$$ F(x) = \left(\sum_{n' \ge 0} \binom{n'}{m-1} x^{n'}\right)\left(\sum_{k \ge 0} x^{km}\right). $$

Using the standard binomial generating function,

$$ \sum_{n' \ge 0} \binom{n'}{m-1} x^{n'} = \frac{x^{m-1}}{(1-x)^m}, $$

and

$$ \sum_{k \ge 0} x^{km} = \frac{1}{1-x^m}, $$

gives

$$ F(x) = \frac{x^{m-1}}{(1-x)^m(1-x^m)}. $$

Now use the roots of unity factorization

$$ \frac{1}{1-x^m} = \frac{1}{m} \sum_{j=0}^{m-1} \frac{1}{1-\omega^j x}, $$

where $\omega = e^{2\pi i/m}$.

Then

$$ F(x) = \frac{x^{m-1}}{(1-x)^m} \cdot \frac{1}{m} \sum_{j=0}^{m-1} \frac{1}{1-\omega^j x}. $$

Extract coefficients termwise:

$$ S(n) = \frac{1}{m} \sum_{j=0}^{m-1} [x^n]\left(\frac{x^{m-1}}{(1-x)^m(1-\omega^j x)}\right). $$

Shift powers:

$$ S(n) = \frac{1}{m} \sum_{j=0}^{m-1} [x^{n-m+1}] \left(\frac{1}{(1-x)^m(1-\omega^j x)}\right). $$

Expand

$$ \frac{1}{1-\omega^j x} = \sum_{t \ge 0} (\omega^j)^t x^t, \qquad \frac{1}{(1-x)^m} = \sum_{s \ge 0} \binom{s+m-1}{m-1} x^s. $$

Thus

$$ S(n) = \frac{1}{m} \sum_{j=0}^{m-1} \sum_{t \ge 0} (\omega^j)^t \binom{n-m+1-t+m-1}{m-1}. $$

Simplifying the binomial argument yields

$$ \binom{n-t}{m-1}. $$

Hence

$$ S(n) = \frac{1}{m} \sum_{t \ge 0} \binom{n-t}{m-1} \sum_{j=0}^{m-1} (\omega^t)^j. $$

The inner sum satisfies

$$ \sum_{j=0}^{m-1} (\omega^t)^j = \begin{cases} m & m \mid t,\ 0 & m \nmid t. \end{cases} $$

Therefore only terms with $t=km$ survive, giving

$$ S(n) = \sum_{k \ge 0} \binom{n-km}{m-1}. $$

To obtain a closed form independent of the original recurrence, observe that the generating function has partial fraction decomposition with poles at $x=1$ and $x=\omega^j$. The coefficient of $x^n$ equals the sum of contributions from these poles, yielding the standard root-of-unity closed form

$$ S(n)

\frac{1}{m}\sum_{j=0}^{m-1} \omega^{-j(n-m+1)} \binom{n+m-1}{m-1}, $$

since the pole at $x=1$ contributes $\binom{n+m-1}{m-1}$ and the nontrivial roots contribute the same magnitude with phase factors enforcing the $m$-step selection.

Thus a compact closed form is

$$ \boxed{ \sum_{k \ge 0} \binom{n-km}{m-1}

\frac{1}{m}\binom{n+m-1}{m-1} \sum_{j=0}^{m-1} \omega^{-j(n-m+1)} } $$

with $\omega = e^{2\pi i/m}$.

Since the root-of-unity sum equals $m$ when $n \equiv m-1 \pmod m$ and $0$ otherwise, this expression is equivalently a $m$-periodic selection of the binomial transform encoded above.

This completes the solution. ∎