Multinomial identity

Question

Consider that $p_0,\dots,p_m$ are probabilities such that $\sum\limits_{i=0}^{m}p_i=1$. I would like to prove that \begin{align} \textstyle n\sum\limits_{i=0}^{m}ip_i=\sum\limits_{k_0+\dots +k_m=n;\text{ }k_i\geq 0}\binom{n}{k_0,\dots,k_m}\left(\sum\limits_{i=0}^{m}k_{i}i\right)p_m^{k_m} p_{m-1}^{k_{m-1}}\dots p_1^{k_1}p_0^{k_0}. \end{align}

I have been trying to prove it with induction. For $n=1$ and for each $m\in\mathbb{N}$ we have $\begin{aligned} &\textstyle\sum\limits_{k_0+\dots +k_m=1;\text{ }k_i\geq 0}\binom{1}{k_0,\dots,k_m}\left(\sum\limits_{i=0}^{m}k_{i}i\right)p_m^{k_m} p_{m-1}^{k_{m-1}}\dots p_1^{k_1}p_0^{k_0}=\\ &=\textstyle \left({\color{red}1}\cdot m+0\cdot(m-1)+0\cdot(m-2)+\dots+0\cdot 1+0\cdot 0\right)p_m^{{\color{red}1}} p_{m-1}^{0}p_{m-2}^{0}\dots p_1^{0}p_0^{0}+\\ &+\textstyle \left(0\cdot m+{\color{red}1}\cdot(m-1)+0\cdot(m-2)+\dots+0\cdot 1+0\cdot 0\right)p_m^{0} p_{m-1}^{{\color{red}1}}p_{m-2}^{0}\dots p_1^{0}p_0^{0}+\\ &+\textstyle \left(0\cdot m+0\cdot(m-1)+{\color{red}1}\cdot(m-2)+\dots+0\cdot 1+0\cdot 0\right)p_m^{0} p_{m-1}^{0}p_{m-2}^{{\color{red}1}}\dots p_1^{0}p_0^{0}+\\ &\phantom{+}\vdots\\ &+\textstyle \left(0\cdot m+0\cdot(m-1)+0\cdot(m-2)+\dots+{\color{red}1}\cdot 1+0\cdot 0\right)p_m^{0} p_{m-1}^{0}\dots p_1^{{\color{red}1}}p_0^{0}+\\ &+\textstyle\left(0\cdot m+0\cdot(m-1)+0\cdot(m-2)+\dots+0\cdot 1+{\color{red}1}\cdot 0\right)p_m^{1} p_{m-1}^{0}\dots p_1^{0}p_0^{{\color{red}1}}=\\ &=\textstyle mp_m+(m-1)p_{m-1}+\dots+1\cdot p_1+0\cdot p_0=\sum\limits_{i=0}^mip_i. \end{aligned}$

Now I would like to prove it for $n+1$. $\begin{aligned} &\textstyle\sum\limits_{k_0+\dots +k_m=n+1;\text{ }k_i\geq 0}\binom{n+1}{k_0,\dots,k_m}\left(\sum\limits_{i=0}^{m}k_{i}i\right)p_m^{k_m} p_{m-1}^{k_{m-1}}\dots p_1^{k_1}p_0^{k_0}=\\ &=\textstyle\sum\limits_{k_0+\dots +k_m=n+1;\text{ }k_i\geq 0}(n+1)\binom{n}{k_0,\dots,k_m}\left(\sum\limits_{i=0}^{m}k_{i}i\right)p_m^{k_m} p_{m-1}^{k_{m-1}}\dots p_1^{k_1}p_0^{k_0}=\\ &=\textstyle n\sum\limits_{k_0+\dots +k_m=n+1;\text{ }k_i\geq 0}\binom{n}{k_0,\dots,k_m}\left(\sum\limits_{i=0}^{m}k_{i}i\right)p_m^{k_m} p_{m-1}^{k_{m-1}}\dots p_1^{k_1}p_0^{k_0}+\\ &+\textstyle\sum\limits_{k_0+\dots +k_m=n+1;\text{ }k_i\geq 0}\binom{n}{k_0,\dots,k_m}\left(\sum\limits_{i=0}^{m}k_{i}i\right)p_m^{k_m} p_{m-1}^{k_{m-1}}\dots p_1^{k_1}p_0^{k_0}=\dots \end{aligned}$

But now I do not have idea how to continue.

Any help will be appreciated. Thank you.

Answer 1

I think it's easier to do the induction on $\ m\ $ rather than $\ n\ $. Here's an outline.

Let \begin{align} E_n&=\sum\limits_{k_0+\dots +k_m=n;\text{ }k_i\geq 0}\binom{n}{k_0,\dots,k_m}\left(\sum\limits_{i=0}^{m}k_{i}i\right)p_m^{k_m} p_{m-1}^{k_{m-1}}\dots p_1^{k_1}p_0^{k_0}\\ &=\sum_{k_m=0}^n\sum\limits_{k_0+\dots +k_{m-1}\\=n-k_m;\ k_i\geq 0}\binom{n}{k_0,\dots,k_m}\left(\sum\limits_{i=0}^{m}k_{i}i\right)p_m^{k_m} p_{m-1}^{k_{m-1}}\dots p_1^{k_1}p_0^{k_0}\\ &=\sum_{k_m=0}^np_m^{k_m}\big(1-p_m\big)^{n-k_m}{n\choose k_m}\\ &\sum\limits_{k_0+\dots +k_{m-1}\\=n-k_m;\ k_i\geq 0}\binom{n-k_m}{k_0,\dots,k_{m-1}}\left(mk_m+\sum\limits_{i=0}^{m-1}k_{i}i\right) q_{m-1}^{k_{m-1}}\dots q_1^{k_1}q_0^{k_0}\ , \end{align} where $\ q_i=\frac{p_i}{1-p_m}\ $. Now $\ \sum_\limits{i=0}^{m-1}q_i=1\ $, so $$ \sum\limits_{k_0+\dots +k_{m-1}\\=n-k_m;\text{ }k_i\geq 0}\binom{n-k_m}{k_0,\dots,k_{m-1}}q_{m-1}^{k_{m-1}}\dots q_1^{k_1}q_0^{k_0}=1\ , $$ because this is just the sum of the probabilities of the elementary outcomes of an $\ n-k_m,q_0,q_1,\dots,q_{m-1}\ $ multinomial distribution, and if the result is true for $\ m-1\ $, then we have $$ \sum\limits_{k_0+\dots +k_{m-1}\\=n-k_m;\text{ }k_i\geq 0}\binom{n-k_m}{k_0,\dots,k_{m-1}}\left(\sum\limits_{i=0}^{m-1}k_{i}i\right) q_{m-1}^{k_{m-1}}\dots q_1^{k_1}q_0^{k_0}\\ =\big(n-k_m\big)\sum_{i=0}^{m-1}iq_i\ . $$

Substituting these values back into the last expression above for $\ E_n\ $ gives \begin{align} E_n&=\sum_{k_m=0}^np_m^{k_m}\big(1-p_m\big)^{n-k_m}{n\choose k_m}\left(mk_m+\big(n-k_m\big)\sum_{i=0}^{m-1}iq_i\right)\\ &=mnp_k+n\big(1-p_k\big)\sum_{i=0}^{m-1}iq_i\\ &=n\sum_{i=0}^mip_i\ , \end{align} from the formula for the mean of the binomial distribution. Thus, the result holds for $\ m\ $ if it holds for $\ m-1\ $. The result also holds for $\ m=1\ $, because then it's just the formula for the mean of the binomial distribution. The result therefore holds for all $\ m\ge1\ $ by induction.

Answer 2

We consider a multivariate polynomial \begin{align*} \color{blue}{P(z_1,z_2,\ldots,z_m)=\left(p_0+p_1z_1+p_2z_2^2+\cdots+p_mz_m^m\right)^n}\tag{1.1} \end{align*} According to the multinomial theorem we have \begin{align*} \color{blue}{P(z_1,z_2,\ldots,z_n)=\sum_{{k_0+k_1+\cdots+k_m=n}\atop{k_i\geq 0,\ 0\leq i\leq m}} \binom{n}{k_0,\ldots,k_m}p_0^{k_0}p_1^{k_1}z_1^{k_1}p_2^{k_2}z_2^{2k_2}\cdots p_m^{k_m}z_m^{mk_m}}\tag{1.2} \end{align*}

We calculate in (1.1) the partial derivative of $P$ with respect to $z_i, 1\leq i\leq m$ and evaluate it at $z_1=z_2=\cdots=z_m=1$. We obtain \begin{align*} \frac{\partial}{\partial z_i}&F\left(z_1,\ldots,z_m\right)\Big|_{z_1=z_2=\cdots=z_m=1}\\ &=n\left(p_0+p_1z_1+p_2z_2^2+\cdots+p_mz_m^{m}\right)^{n-1} \cdot ip_iz^{i-1}\Big|_{z_1=z_2=\cdots=z_m=1}\\ &=n\left(p_0+p_1+p_2+\cdots+p_m\right)^{n-1}ip_i\\ &=nip_i\tag{2.1} \end{align*} Doing the same with (1.2) we obtain \begin{align*} \frac{\partial}{\partial z_i}&F\left(z_1,\ldots,z_m\right)\Big|_{z_1=z_2=\cdots=z_m=1}\\ &=\sum_{{k_0+k_1+\cdots+k_m=n}\atop{k_i\geq 0, 0\leq i\leq m}} \binom{n}{k_0,\ldots,k_m}p_0^{k_0}p_1^{k_1}z_1^{k_1}\cdots \color{blue}{ik_i p_i^{k_i}z_i^{ik_i-1}}\cdots p_m^{k_m}z_m^{mk_m}\Big|_{z_1=z_2=\cdots=z_m=1}\\ &=\sum_{{k_0+k_1+\cdots+k_m=n}\atop{k_i\geq 0, 0\leq i\leq m}} \binom{n}{k_0,\ldots,k_m}p_0^{k_0}p_1^{k_1}\cdots \color{blue}{ik_i p_i^{k_i}}\cdots p_m^{k_m}\tag{2.2} \end{align*}

We finally derive from (2.1) and (2.2) \begin{align*} \sum_{i=1}^{m}&\frac{\partial}{\partial z_i}F\left(z_1,\ldots,z_m\right)\Big|_{z_1=z_2=\cdots=z_m=1}\\ &\,\,=\color{blue}{n\sum_{i=0}^mip_i =\sum_{{k_0+k_1+\cdots+k_m=n}\atop{k_i\geq 0, 0\leq i\leq m}} \binom{n}{k_0,\ldots,k_m}\left(\sum_{i=0}^m ik_i\right)p_0^{k_0}p_1^{k_1}\cdots p_m^{k_m}} \end{align*} and the claim follows.