Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

$$ \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$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.