Another identity for posterity

Here’s another combinatorial identity that I think should be useful, and one that I will probably run into again:

$\frac{k}{m}\binom{2m}{m+k} = \binom{2m-1}{m+k-1} - \binom{2m-1}{m+k}$ , which allows you to compute very useful sums like: $\sum_{k=1}^m{\binom{2m}{m+k} k}$ . Combined with Stirling’s formula, this sum is asymptotically $2^{2m} \sqrt{m}/\sqrt{2\pi}$ .

For example, consider the standard simple, one dimensional random walk, where one can move left or right with equal probability. The expected location after $n$ steps is 0, but the expected distance after $n$ steps is $\Theta (\sqrt{n})$ , which can be arrived at via the identities described above. The standard deviation of the location is exactly $\sqrt{n}$ . Does any one know of a precise relationship between the variance and the expected distance?

Like this:

Be the first to like this post.

5 thoughts on “Another identity for posterity”

Another useful identity:

$\binom{r}{k} = \frac{r}{k} \binom{r-1}{k-1}$

Reply ↓

And another:

$\ln(x) \leq x + 1$
$\sum_{j=0}^n \binom{n}{j}\alpha^j\beta^{n-j}j = \alpha n (\alpha + \beta)^{n-1}$ .

Reply ↓

$\sum_{j=0}^{n}{\alpha^j} = \frac{1 - \alpha^{n+1}}{1 - \alpha}$ where $|\alpha| < 1$
$\binom{n}{x}\binom{x}{y} = \binom{n}{y}\binom{n-y}{x-y}$

Reply ↓

Pingback: A Solution to a Generalized Pepys’s Problem | Henry Yuen's Blog

Taylor series expansion for $H(p + \epsilon)$ , where $H(p)$ is the binary entropy function:

$H(p + \epsilon) \approx H(p) + (\log \frac{1-p}{p})\epsilon - \frac{1}{2}(\frac{1}{p} + \frac{1}{1-p})\epsilon^2 + \frac{1}{6}(\frac{1}{p^2} - \frac{1}{(1-p)^2})\epsilon^3 + \cdots$

Reply ↓

Henry Yuen's Blog

Slowly discovering the universe

Another identity for posterity

Like this:

5 thoughts on “Another identity for posterity”

Leave a Reply Cancel reply

Follow “Henry Yuen's Blog”