4

Let $p_1,\ldots,p_s$ be $s$ number in the unit interval such that $$p_1+\ldots+p_s=1.$$

Is it then true, that for every $n\geq 1$ we have $$ \sum_{(k_1,\ldots,k_n)\in \{1,\ldots,s \}^n} p_{k_1}\cdot \ldots \cdot p_{k_n}=1 ?$$

Checking it for $n=2$ indicates that it's true (but already for $n=3$ it isn't feasable to check it by hand)...

MyCatsHat
  • 1,069

2 Answers2

7

$$ \sum_{(k_1,\ldots,k_n)\in \{1,\ldots,s \}^n} p_{k_1}\cdot \ldots \cdot p_{k_n}=(p_1+p_2+\cdots+p_s)^n=1^n=1$$

Michael Hardy
  • 1
Amr
  • 20,030
2

Let $[s]=\{1,\dots,s\}$. For $n>1$ we have

$$\begin{align*} \sum_{\langle k_1,\dots,k_n\rangle\in[s]^n}p_{k_1}\dots p_{k_n}&=\sum_{\langle k_1,\dots,k_{n-1}\rangle\in[s]^{n-1}}\left(p_{k_1}\dots p_{k_{n-1}}\sum_{k\in[s]}p_k\right)\\\\ &=\sum_{\langle k_1,\dots,k_{n-1}\rangle\in[s]^{n-1}}p_{k_1}\dots p_{k_{n-1}}\;, \end{align*}$$

so the result follows by induction.

Brian M. Scott
  • 616,228
  • Accepted your answer in the end since it seems I can generalize it for other things I need to do. Could you please explain in more detail why the first equation holds ? – MyCatsHat Dec 30 '12 at 17:51
  • @user26698: I’m just gathering together all terms with the same first $n-1$ factors. Take the case $s=3,n=2$ as an example. The lefthand side of the first equation is $$p_1\cdot p_1+p_1\cdot p_2+p_1\cdot p_3+p_2\cdot p_1+p_2\cdot p_2+p_2\cdot p_3+p_3\cdot p_1+p_3\cdot p_2+p_3\cdot p_3;.$$ The righthand organizes it like this: $$p_1(p_1+p_2+p_3)+p_2(p_1+p_2+p_3)+p_3(p_1+p_2+p_3);.$$ – Brian M. Scott Dec 30 '12 at 22:03
  • got it, thanks a lot! – MyCatsHat Dec 31 '12 at 13:16
  • @user26698: Excellent. You’re welcome! – Brian M. Scott Dec 31 '12 at 14:44