Evaluate Sum of Products in The Form of $\sum_{\left\|\mathbf{x}\right\|=C}\prod_{i=0}^{n}\left(2+i\right)^{x_{i}}$

Question

Background

I recently came across the problem to prove the following:

$$ \sum_{\left\|\mathbf{x}\right\|_{1}=m-1}2^{x_{1}}3^{x_{2}} = 3^{m}-2^{m}, \phantom{x} \mathbf{x}\in\mathbb{N}_{0}^{2} $$

A proof by induction is available here. A combinatorial proof is also quite straightforward:

We have $m$ customers standing in a queue to visit one of three stalls.

LHS

The summand $2^{x_{1}}3^{x_{2}}$ is the number of possibillities where customer number $x_{1}+1$ is the first to visit the third stall. Therefore, the LHS is the total number of possibilities where at least one customer visit the third stall.

RHS

The RHS is simpler. Out of $3^{m}$ possibilities, we subtract those in which the third stall receives no customer: $2^{m}$.

Problem Statement

I wish to extend the problem and evaluate the following expression:

$$ \sum_{\left\|\mathbf{x}\right\|_{1}=m-n}\prod_{i=0}^{n}\left(2+i\right)^{x_{i}} = \phantom{x} ? \phantom{x}, \phantom{x} \mathbf{x}\in\mathbb{N}_{0}^{n+1} $$

My Attempt

Using a similar approach to the original problem, I was able to prove that

$$ \sum_{\left\|\mathbf{x}\right\|_{1}=m-2}2^{x_{1}}3^{x_{2}}4^{x_{3}} = \frac{1}{2}\left[ 4^{m}-2\cdot 3^{m}+2^{m} \right], \phantom{x} \mathbf{x}\in\mathbb{N}_{0}^{3} $$

Again we have $m$ customers standing in a queue, this time to visit one of four stalls.

LHS

The summand $2^{x_{1}}3^{x_{2}}4^{x_{3}}$ is the number of possibilities where customer number $x_{1}+1$ is the first to visit the third stall and customer number $x_{1}+x_{2}+2$ is the first to visit the fourth stall. The LHS is then the total number of possibilities where the third and fourth stalls have customer(s) and the third stall receives a customer before the fourth stall.

RHS

There are $4^{m}$ total possibilities. Of these:

• $3^{m}-2^{m}$ possibilities that third stall receive customer(s) but the fourth stall does not
• $3^{m}-2^{m}$ possibilities that fourth stall receive customer(s) but the third stall does not
• $2^{m}$ possibilities that neither the third nor the fourth stall receive any customer

Therefore, there are $4^{m}-2\cdot\left(3^{m}-2^{m}\right)-2^{m}=4^{m}-2\cdot 3^{m}+2^{m}$ possibilities where both the third and fourth stalls receive customer(s). In half of these possibilities, the third stall receives a customer before the fourth stall does.

Remaining Challenge

Using this approach, I can prove the problem for an arbitrary $n$. However, it quickly becomes too tedious. I am wondering if anyone knows a more straightforward alternative.

Answer 1

We have from first principles that we seek

$$[z^{m-n}] \prod_{q=0}^n \frac{1}{1-(2+q)z} = [z^{m-n}] (1-z) \prod_{q=1}^{n+2} \frac{1}{1-qz} \\ = [z^{m-n}] \prod_{q=1}^{n+2} \frac{1}{1-qz} - [z^{m-n-1}] \prod_{q=1}^{n+2} \frac{1}{1-qz} \\ = [z^{m+2}] \prod_{q=1}^{n+2} \frac{z}{1-qz} - [z^{m+1}] \prod_{q=1}^{n+2} \frac{z}{1-qz} = {m+2\brace n+2} - {m+1\brace n+2}.$$

We have for the first term

$$\frac{1}{(n+2)!} \sum_{j=0}^{n+2} (-1)^{n+2-j} {n+2\choose j} j^{m+2}$$

and the second

$$\frac{1}{(n+2)!} \sum_{j=0}^{n+2} (-1)^{n+2-j} {n+2\choose j} j^{m+1}$$

Collect both to get

$$\frac{1}{(n+2)!} \sum_{j=0}^{n+2} (-1)^{n+2-j} {n+2\choose j} (j-1) j^{m+1} \\ = \frac{1}{(n+1)!} \sum_{j=1}^{n+2} (-1)^{n+2-j} {n+1\choose j-1} (j-1) j^m.$$

This is

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{n!} \sum_{j=2}^{n+2} (-1)^{n-j} {n\choose j-2} j^m.}$$

For example with $n=2$ we get

$$\frac{1}{2} \left[ (-1)^{2-2} {2\choose 2-2} 2^m + (-1)^{2-3} {2\choose 3-2} 3^m + (-1)^{2-4} {2\choose 4-2} 4^m \right] \\ = \frac{1}{2} [ 2^m - 2 \times 3^m + 4^m]$$

matching the result by OP.

Answer 2

Let $n \in \{1, 2, \ldots\}$, and let $r_1, \ldots, r_n$ be distinct. Then consider the generating function

\begin{align*} f(x) = \sum_{m=0}^{\infty} z^m \sum_{\substack{\mathbf{x} \in \mathbb{N}_0^{n} \\ \|\mathbf{x}\|_{1}=m}}\prod_{i=1}^{n} r_i^{x_{i}}. \end{align*}

Rearranging, we get

\begin{align*} f(x) &= \sum_{\mathbf{x} \in \mathbb{N}_0^{n}}\prod_{i=1}^{n} (r_i z)^{x_{i}} = \prod_{i=1}^{n} \frac{1}{1 - r_i z} \\ &= \sum_{k=1}^{n} \frac{r_k^{n-1}}{\prod_{i \in [n] \setminus\{k\}} (r_k - r_i)} \cdot \frac{1}{1 - r_k z} \\ &= \sum_{m=0}^{\infty} \biggl( \sum_{k=1}^{n} \frac{r_k^{m+n-1}}{\prod_{i \in [n] \setminus\{k\}} (r_k - r_i)} \biggr) z^m. \end{align*}

In the second step, we utilized partial fraction decomposition. Hence it follows that

$$ \sum_{\substack{\mathbf{x} \in \mathbb{N}_0^{n} \\ \|\mathbf{x}\|_{1}=m}}\prod_{i=1}^{n} r_i^{x_{i}} = \sum_{k=1}^{n} \frac{r_k^{m+n-1}}{\prod_{i \in [n] \setminus\{k\}} (r_k - r_i)}, $$

or equivalently,

$$ \bbox[color:navy; padding:8px; border:1px navy dotted; background:#feffed;]{\sum_{\substack{\mathbf{x} \in \mathbb{N}_0^{n} \\ \|\mathbf{x}\|_{1}=m-n+1}}\prod_{i=1}^{n} r_i^{x_{i}} = \sum_{k=1}^{n} \frac{r_k^m}{\prod_{i \in [n] \setminus\{k\}} (r_k - r_i)}.} $$

Example 1. If $n = 2$, $r_1 = 2$ and $r_2 = 3$, then

$$ \sum_{\substack{\mathbf{x} \in \mathbb{N}_0^{2} \\ \|\mathbf{x}\|_{1}=m-1}} 2^{x_1}3^{x_2} = \frac{2^m}{2-3} + \frac{3^m}{3-2} = 3^m - 2^m. $$

Example 2. If $n = 3$, $r_1 = 2$, $r_2 = 3$, and $r_3 = 4$, then

\begin{align*} \sum_{\substack{\mathbf{x} \in \mathbb{N}_0^{3} \\ \|\mathbf{x}\|_{1}=m-2}} 2^{x_1}3^{x_2}4^{x_3} &= \frac{2^m}{(2-3)(2-4)} + \frac{3^m}{(3-2)(3-4)} + \frac{4^m}{(4-2)(4-3)} \\ &= \frac{1}{2}[4^m - 2 \cdot 3^m + 2^m]. \end{align*}