Take the 2-minute tour ×
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.

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|improve this question

2 Answers 2

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|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 ? –  user26698 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! –  user26698 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|improve this answer

Your Answer

 
discard

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.