Prove sum-product identity 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.
 A: 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}$.
A: 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}$.
