1
$\begingroup$

$$ \sum_{m=1}^{\lfloor j/(k+1) \rfloor}(-1)^m\binom{n}m\binom{j-m(k+1)+n-1}{n-1} = \sum_{m=1}^{j-k} {j-k-1 \choose m-1}{n \choose m}m $$ (Actually $\not =$ see edit end of post)

  1. Is there a simple way to demonstrate this equality?
  2. Is there a way to express the 2nd term in a closed form?

Context

These expressions are two ways of representing the exclusion for the $[x^j]$ coefficient in the expansion $(1+x+x^2+x^3+\cdots+x^k)^n $ when $j>k$ . The first term is obtained by expressing the polynomial as $(1-x^k)^n \over (1-x)^{-n}$ using generating functions. We get:

$$[x^j]={n+j-1 \choose j} - \sum_{m=1}^{\lfloor j/(k+1) \rfloor}(-1)^m\binom{n}m\binom{j-m(k+1)+n-1}{n-1} $$ The second term is an attempt to get the $[x^j]$ coefficient using the multinomial theorem as follows:

$$(1+x+x^2+x^3+\cdots+x^{k})^{n}$$To get the $x^{10}$ coefficient when $k \geq j$ we tabulate every permutation that sums to $10$ and calculate its value with the multinomial theroem. How many permutations are there using one term, then how many using two terms...etc we get this:

\begin{array} {|r|r|}\hline Terms & Permutations & Multinomial Value \\ \hline 1 & 1/1! & n!/(n-1)! \\ \hline 2 & 9/2! & n!/(n-2)! \\ \hline 3 & 36/3! & n!/(n-3)! \\ \hline 4 & 84/4! & n!/(n-4)! \\ \hline 5 & 126/5! & n!/(n-5)! \\ \hline 6 & 126/6! & n!/(n-6)! \\ \hline 7 & 84/7! & n!/(n-7)! \\ \hline 8 & 36/8! & n!/(n-8)! \\ \hline 9 & 9/9! & n!/(n-9)! \\ \hline 10 & 1/10! & n!/(n-10)! \\ \hline \end{array} $$=\sum_{m=1}^{j}{{j-1 \choose m-1}\over m!}\cdot{n! \over n-m!} = \sum_{m=1}^{j}{j-1 \choose m-1}{n \choose m} $$ which as explained here is just another way of expressing $${n+j-1 \choose j}$$ When $k<j$ we need an exclusion which we can calculate similarly i.e. $$[x^{10}](1+x+x^2+x^3+\cdots+x^{5})^{n}$$ \begin{array} {|r|r|}\hline Terms & Permutations & Multinomial Value \\ \hline 1 & 1(1/1!) & n!/(n-1)! \\ \hline 2 & 2(4/2!) & n!/(n-2)! \\ \hline 3 & 3(6/3!) & n!/(n-3)! \\ \hline 4 & 4(4/4!) & n!/(n-4)! \\ \hline 5 & 5(1/5!) & n!/(n-5)! \\ \hline \end{array} $$=\sum_{m=1}^{j-k}{m{j-k-1 \choose m-1}\over m!}\cdot{n! \over n-m!} = \sum_{m=1}^{j-k}{j-k-1 \choose m-1}{n \choose m}m $$

Is there to express this in a closed form as a multiple of a single binomial coefficent? I don't see an easy way to deal with the $m$ at the end. Otherwise although the latter expression is simpler to formulate than the expression obtained by using generating functions, since it will require more steps to solve it seems to be of limited use... :(

Thank you.

EDIT After seeing Robpratt's answer I realized I was mistaken and the multinomial method is only equal to the first term of the generating-function series not the entire series(i.e. not the exclusion of the exclusion) and the equality does not hold.

$\endgroup$

1 Answer 1

2
$\begingroup$

The second sum is \begin{align} \sum_{m=1}^{j-k}{j-k-1 \choose m-1}{n \choose m}m &= \sum_{m=1}^{j-k}{j-k-1 \choose m-1}\frac{n}{m}{n-1 \choose m-1}m \\ &= n\sum_{m=1}^{j-k}{j-k-1 \choose m-1}{n-1 \choose m-1} \\ &= n\sum_{m=1}^{j-k}{j-k-1 \choose m-1}{n-1 \choose n-m} \\ &= n{n+j-k-2 \choose n-1} \end{align}

$\endgroup$
4
  • $\begingroup$ You got rid of that pesky $m$ so easily. Thanks. $\endgroup$ Dec 15, 2023 at 4:29
  • 1
    $\begingroup$ Glad to help. That is called absorption. $\endgroup$
    – RobPratt
    Dec 15, 2023 at 4:31
  • $\begingroup$ Looks like my initial result was too optimistic. The multinomial method is only solving the initial exclusion not the exclusion on the exclusion so the equality does not hold. $n{n+j-k-2 \choose n-1}$ is just the first term of the series generated by the power series method. Thanks again for your help $\endgroup$ Dec 15, 2023 at 4:49
  • $\begingroup$ Made a new post with an improved (and I hope accurate) identity. math.stackexchange.com/questions/4831914/… $\endgroup$ Dec 22, 2023 at 3:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .