4
$\begingroup$

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)...

2 Answers 2

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.

  • 0
    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 ?2012-12-30
  • 0
    @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)\;.$$2012-12-30
  • 0
    got it, thanks a lot!2012-12-31
  • 0
    @user26698: Excellent. You’re welcome!2012-12-31
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$$