Intereting Posts

Expected value of infinite sum
Prove that $\prod\limits_{i=1}^n \frac{2i-1}{2i} \leq \frac{1}{\sqrt{3n+1}}$ for all $n \in \Bbb Z_+$
Euler's identity in matrix form
Hausdorff Dimension Calculation
If $\lambda_n \sim \mu_n$, is it true that $\sum \exp(-\lambda_n x) \sim \sum \exp(-\mu_n x)$ as $x \to 0$?
What is the difference between probability and statistics?
Solution to a recurrence relation
Functions that take rationals to rationals
When is $5n^2+14n+1$ a perfect square?
Sobolev spaces of sections of vector bundles
Is there an elementary method for evaluating $\displaystyle \int_0^\infty \frac{dx}{x^s (x+1)}$?
Show that $e^{-\beta} = \frac{1}{\sqrt{\pi}} \int_{0}^{\infty} \frac{e^{-u}}{\sqrt{u}} e^{-\beta^2 / 4u} du$.
A three variable binomial coefficient identity
Norm of Prime Ideal
How do I prove that a function with a finite number of discontinuities is Riemann integrable over some interval?

Combining the answers given by me and Ralth to the probability question at Probability of getting three zeros when sampling a set, we get the following identity:

$$

\sum\limits_{k = m}^n {{n \choose k}p^k (1 – p)^{n – k} {k \choose m} p_j^m (1 – p_j )^{k – m} } = {n \choose m} (p p_j)^m (1 – p p_j)^{n-m},

$$

where $m \geq 0$ and $n \geq m$ are arbitrary integers, and $p$ and $p_j$ are arbitrary probabilities (in Ralth’s notation $m$ is $k$, $p$ is $p_s$, and $p_j$ is $p_h$). Can you prove this identity directly (i.e., in a non-probabilistic setting)? Whether you’ll find this identity interesting or not, at least Ralth’s answer may now gain its due recognition.

- Can you reduce an inequality by taking a derivative?
- How to prove that $\sum_{r=0}^n\binom{n}{r}2^r=3^n$
- Computing irrational numbers
- Wanted: Insight into formula involving binomial coefficients
- Summation involving binomial coefficients: $\sum_{i=0}^{100} \binom{300}{3i}$
- How to find center of an arc given start point, end point, radius, and arc direction?
- Find the sum $\frac{1}{\sqrt{1}+\sqrt{2}} + \frac{1}{\sqrt{2}+\sqrt{3}} + …+ \frac{1}{\sqrt{99}+\sqrt{100}}$
- How long will it take Marie to saw another board into 3 pieces?
- Factorize $(x+1)(x+2)(x+3)(x+6)- 3x^2$
- Prove $\binom{2p+1}{p}\equiv2$ mod $p$ when $p$ is any prime.

We can prove this using the Multinomial Theorem.

We have, using the Multinomial Theorem, that

$$\displaystyle (a+b+c)^n = \sum_{m=0}^{n} \sum_{k=m}^{n} {n \choose k}{k \choose m} a^m b^{k-m} c^{n-k}$$

Set $\displaystyle a = pp_j x$, $b = p(1-p_j)$, $c = 1-p$.

We get

$$\displaystyle (pp_jx + p(1-p_j) + 1-p )^n = \sum_{m=0}^{n} \sum_{k=m}^{n} {n \choose k}{k \choose m} (pp_jx)^m (p(1-p_j))^{k-m} (1-p)^{n-k}$$

i.e.

$$\displaystyle (pp_jx + 1 – pp_j)^n = \sum_{m=0}^{n} \sum_{k=m}^{n} {n \choose k}{k \choose m} p_j^m(1-p_j)^{k-m} p^{k}(1-p)^{n-k} x^m$$

Expanding the left hand side using binomial theorem and comparing the coefficients of $\displaystyle x^m$ gives the result.

Consider the following two-step process: Start with $n$ elements. Pick each one with probability $p$. Among the $k$ elements chosen in the first phase, pick each one with probability $p_j$. The left-hand side describes the probability that the final set is of size $m$.

We can also calculate this probability directly: every element is chosen to the final set with probability $pp_j$, whence the right-hand side.

Writing the left-hand side as

$$

\sum\limits_{k = 0}^{n – m} {{n \choose k + m} p^{k + m} (1 – p)^{n – (k + m)} {k + m \choose m} p_j^m (1 – p_j )^{k + m – m} }

$$

we find, after some algebra, that the original equation is equivalent to

$$

\sum\limits_{k = 0}^l {{l \choose k}p^k (1 – p)^{l – k} (1 – p_j )^k } = (1 – pp_j )^l ,

$$

where $l (=n-m) \geq 0$. Since the case $p=0$ is satisfied ($0^0=1$), we assume that $p = x/y$, with $0 < x \leq y$. Substituting this leads straightforwardly to the equivalent equation

$$

\sum\limits_{k = 0}^l {{l \choose k}(x – x p_j)^k (y-x)^{l-k} = (y – xp_j)^l}.

$$

By the binomial theorem, the left-hand side is equal to $[(x – xp_j ) + (y – x)]^l$, completing the proof.

- Can the Bourbaki series be used profitably by undergraduates?
- Are there nontrivial continuous maps between complex projective spaces?
- Must the sequence $X_n$ converge to $0$ in probability?
- Any smart ideas on finding the area of this shaded region?
- Prove the _Chinese Remainder Theorem_
- Prove there is no contraction mapping from compact metric space onto itself
- Finding a specific improper integral on a solution path to a 2 dimensional system of ODEs
- Show that: $\mu\left(\bigcup_N \bigcap_{n=N}^{\infty} A_n \right) \leq \lim \inf \mu(A_n)$
- $u\in W^{1,p}(0,1)$ is equal a.e. to an absolutely continuous function?
- When is infinite sum bounded by an integral?
- Asymptotic behavior of $\sum\limits_{k=1}^n \frac{1}{k^{\alpha}}$ for $\alpha > \frac{1}{2}$
- Can finite non-isomorphic groups of the same order have isomorphic endomorphism monoids?
- Set of Ideals of a Polynomial Ring
- What is $\frac{x^{10} + x^8 + x^2 + 1}{x^{10} + x^6 + x^4 + 1}$ given $x^2 + x – 1 = 0$?
- How to Visualize points on a high dimensional (>3) Manifold?