Prove sum-product identity

Question

I have verified numerically the following identity, for several values of $m,n$:

$$\sum_{i_1, \ldots, i_m = 1}^n \prod_{k = 1}^{m - 1} (\delta_{i_k, i_{k + 1}} a_k + (1 - \delta_{i_k, i_{k + 1}}) b_k) = n \prod_{k = 1}^{m - 1} (a_k + (n - 1) b_k)$$

Here $m,n$ are positive integers and $a_k,b_k$ are given numbers.

But I have not been able to prove it. There is probably some trick to simplify the math that I am missing.

This is not homework. I just stumbled upon this during a very specific research problem.

Answer 1

The special cases $n=1$ or $m=1$ can be shown easily. We denote with $[n]=\{1,\ldots,n\}$. Let $m,n$ be integers $>1$.

We obtain \begin{align*} \color{blue}{n\prod_{k=1}^{m-1}}&\color{blue}{\left(a_k+(n-1)b_k\right)}\\ &=n\sum_{S\subseteq[m-1]}\left(\prod_{q\in S}a_q\right)(n-1)^{m-1-|S|}\left(\prod_{q\in[m-1]\setminus S}b_q\right)\tag{1}\\ &=\sum_{S\subseteq[m-1]}\sum_{j_1=1}^n\left(\prod_{q\in S}a_q\right)(n-1)^{m-1-|S|}\left(\prod_{q\in[m-1]\setminus S}b_q\right)\tag{2}\\ &=\sum_{S\subseteq[m-1]}\sum_{j_1=1}^n\sum_{{j_2,\ldots,j_m=1}\atop{{j_k=j_{k+1},k\in S}\atop{j_k\ne j_{k+1}, k\in [m-1]\setminus S}}}^n \left(\prod_{q\in S}a_q\right)\left(\prod_{q\in[m-1]\setminus S}b_q\right)\tag{3}\\ &=\sum_{S\subseteq[m-1]}\sum_{{j_1,\ldots,j_m=1}\atop{{j_k=j_{k+1},k\in S}\atop{j_k\ne j_{k+1}, k\in [m-1]\setminus S}}}^n \prod_{q=1}^{m-1}\left(\delta_{j_q,j_{q+1}}a_q+\left(1-\delta_{j_q,j_{q+1}}\right)b_q\right)\tag{4}\\ &\,\,\color{blue}{=\sum_{j_1,\ldots,j_m=1}^n \prod_{q=1}^{m-1}\left(\delta_{j_q,j_{q+1}}a_q+\left(1-\delta_{j_q,j_{q+1}}\right)b_q\right)}\tag{5} \end{align*} and the claim follows.

Comment

• In (1) we multiply out the product noting that each of the $m-1$ factors contributes either $a_k$ or $(n-1)b_k$. We order the terms, so that for $k\in S\subseteq[m-1]$ we have $j_k=j_{k+1}$ and for $k\in[m-1]\setminus S$ we have $j_k\ne j_{k+1}$.

• In (2) we use $\displaystyle{\sum_{j_1=1}^n1}=n$.

• In (3) we use $\displaystyle{\sum_{{j_1,\ldots,j_m=1}\atop{{j_k=j_{k+1},k\in S}\atop{j_k\ne j_{k+1}, k\in [m-1]\setminus S}}}^n1}=(n-1)^{m-1-|S|}$. Note that for $k\in S$, $1\leq j_k\leq n$ we have $\displaystyle{\sum_{{j_{k+1}=1}\atop{j_k=j_{k+1}}}^n1=1}$ and $\displaystyle{\sum_{{j_{k+1}=1}\atop{j_k\ne j_{k+1}}}^n1=n-1}$.

• In (4) we reorder the product by letting the bound variable $q$ go from $1$ to $n$ and connect $a_k$ and $b_k$ with $S$ using the kronecker delta symbol.

• In (5) we just reorder the summands by skipping the summation over $S$ and the conditions $j_k= j_{k+1}$, resp. $j_k\ne j_{k+1}$.

Answer 2

Here's a strategy I believe works, though I didn't check the last step.

Let the left-hand side be $L(m)$ and the right-hand side be $R(m)$. It's trivial to check that $L(1)=n=R(1)$. Proceeding by induction:

• Fix $a_1,\dots,a_{m-2},b_1,\dots,b_{m-2}$ and consider $a_{m-1},b_{m-1}$ as variables.
• Note that when $a_{m-1}=1$ and $b_{m-1}=0$, the expressions $L(m)$ and $R(m)$ simplify to $L(m-1)$ and $R(m-1)$, respectively, which are equal by the inductive hypothesis.
• Note that the derivatives of $L(m)$ and $R(m)$ with respect to $a_{m-1}$ both equal $L(m-1)=R(m-1)$.
• Note that the derivatives of $L(m)$ and $R(m)$ with respect to $b_{m-1}$ are also equal. (This I didn't check.)

These observations together show that $L(m)=R(m)$ for all values of $a_{m-1}$ and $b_{m-1}$.