2
$\begingroup$

I am trying to simplify the following expression I have encountered in a book

$\sum_{k=0}^{K-1}\left(\begin{array}{c} K\\ k+1 \end{array}\right)x^{k+1}(1-x)^{K-1-k}$

and according to the book, it can be simplified to this:

$1-(1-x)^{K}$

I wonder how is it done? I've tried to use Mathematica (to which I am new) to verify, by using

$\text{Simplify}\left[\sum _{k=0}^{K-1} \left(\left( \begin{array}{c} K \\ k+1 \end{array} \right)*x{}^{\wedge}(k+1)*(1-x){}^{\wedge}(K-1-k)\right)\right]$

and Mathematica returns

$\left\{\left\{-\frac{K q \left((1-q)^K-q^K\right)}{-1+2 q}\right\},\left\{-\frac{q \left(-(1-q)^K+(1-q)^K q+(1+K) q^K-(1+2 K) q^{1+K}\right)}{(1-2 q)^2}\right\}\right\}$

which I cannot quite make sense of it.

To sum up, my question is two-part:

  1. how is the first expression equivalent to the second?

  2. how should I interpret the result returned by Mathematica, presuming I'm doing the right thing to simplify the original formula?

Thanks a lot!

$\endgroup$
2
$\begingroup$

Note that $$ \begin{align} \sum_{k=0}^{K-1}\binom{K}{k+1}x^{k+1}(1-x)^{K-1-k} &=\sum_{k=1}^{K}\binom{K}{k}x^{k}(1-x)^{K-k}\\ &=\left(\sum_{k=0}^{K}\binom{K}{k}x^{k}(1-x)^{K-k}\right)-(1-x)^K\\ &=(x+(1-x))^K-(1-x)^K\\ &=1^K-(1-x)^K \end{align} $$

$\endgroup$
  • $\begingroup$ thanks robjohn! So what is that thing returned by Mathematica then? $\endgroup$ – balllib Oct 27 '11 at 16:02
  • $\begingroup$ $K$ seems to be reserved (note its color is black, not blue). When using $K1$, Mathematica gives $\left(\left(\frac{1}{1-x}\right)^{\text{K1}}-1\right) (1-x)^{\text{K1}}$. $\endgroup$ – robjohn Oct 27 '11 at 16:44
  • $\begingroup$ thanks! but i still get some output like before, this is what I input in Mathematica: $\text{Simplify}\left[\sum _{k=0}^{n-1} \left( \begin{array}{c} n \\ k+1 \end{array} \right)*x{}^{\wedge}(k+1)*(1-x){}^{\wedge}(n-1-k)\right]$, changing $K$ to $n$. $\endgroup$ – balllib Oct 27 '11 at 18:57
1
$\begingroup$

Simplify[PowerExpand[Simplify[Sum[Binomial[K, k + 1]*x^(k + 1)*(1 - x)^(K - k - 1), {k, 0, K - 1}], K > 0]]] works nicely. The key is in the use of the second argument of Simplify[] to add assumptions about a variable. and using PowerExpand[] to distribute powers.

$\endgroup$
  • $\begingroup$ thanks J.M. I've tried yours in Mathematica and indeed it gives nice result. However, as soon as I replace your style of the expression with symbolic one, the problem persists. I used the following: $\text{Simplify}\left[\text{PowerExpand}\left[\text{Simplify}\left[\sum _{k=0}^{K-1} \left(\left( \begin{array}{c} K \\ k+1 \end{array} \right)*(x{}^{\wedge}(k+1))*(1-x){}^{\wedge}(K-1-k)\right),K>0\right]\right]\right]$. Do you know why? $\endgroup$ – balllib Oct 27 '11 at 19:04
  • $\begingroup$ If I really want things to work in Mathematica, I often forgo the fancy formatting. Why do you need the fancy formatting here? $\endgroup$ – J. M. is a poor mathematician Oct 27 '11 at 23:39
0
$\begingroup$

It follows from the Binomial Formula, http://en.wikipedia.org/wiki/Binomial_theorem.

$\endgroup$
  • $\begingroup$ thanks for pointing out. i see that in robjohn's answer too. $\endgroup$ – balllib Oct 27 '11 at 18:01
  • $\begingroup$ wish I could up-vote this but apparently i need 15 points of reputation. still much appreciated. $\endgroup$ – balllib Oct 27 '11 at 18:02
0
$\begingroup$

The following answer makes sense only with some background in probability. Suppose first that $0 \le x\le 1$.

A possibly biased coin has probability $x$ of landing "heads." Toss the coin $K$ times. We compute the probability $P$ of one or more heads in two different ways.

The probability we get exactly $k+1$ heads is $$\binom{K}{k+1}x^{k+1}(1-x)^{K-1-k}.$$ Add up, from $k=0$ to $k=K-1$. We get the probability of $1$ head, plus the probability of $2$ heads, plus the probability of $3$ heads, and so on, up to the probability of $K$ heads. Thus $$P=\sum_{k=0}^{K-1}\binom{K}{k+1}x^{k+1}(1-x)^{K-1-k}.$$

The probability of $0$ heads (all tails) is $(1-x)^K$, so the probability of one or more heads is $1-(1-x)^K$, and therefore $$P=1-(1-x)^K.$$

The argument so far only proves the desired result for $0\le x\le 1$. But note that for any $K$, each of the expressions we are trying to prove equal is a polynomial of degree $K$. But if two polynomials $A(x)$ and $B(x)$ with real coefficients, each of degree $\le K$, are equal at $K+1$ values of $x$, then they are identically equal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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