5

$${k\choose m}{m \choose n} = {k!\over m!(k-m)!}{m!\over n!(m-n)!}={k\choose k-m,n,m-n}$$ so we have $$\sum_{m=0}^k\sum_{n=0}^m{k\choose k-m,n,m-n}=3^k,$$ the number of ways to distribute $k$ objects in $3$ piles.


5

Under the convention that $\binom{n}{k}=0$ if $k\notin\left\{ 0,1,\dots,n\right\} $ we find by means of the triangle of Pascal: $$\begin{aligned}\sum_{n=k+1}^{\infty}\binom{n}{k+1}\frac{1}{2^{n}} & =\sum_{n=k+1}^{\infty}\binom{n-1}{k}\frac{1}{2^{n}}+\sum_{n=k+1}^{\infty}\binom{n-1}{k+1}\frac{1}{2^{n}}\\ & =\frac{1}{2}\sum_{n=k}^{\infty}\binom{n}{k}\...


3

Recall the classic Cayley's Result that there are $n^{n-2}$ labelled tree on $n$ vertices. https://en.wikipedia.org/wiki/Cayley%27s_formula Choose one of the vertices of a labelled tree and call it the (first) root ($r_1$); it is clear that there are $n^{n-1}$ rooted trees. Next choose a second vertex ($r_2$) (possibly the same as the first) and call it ...


2

Starting from (the contribution from $k=0$ is zero owing to the third binomial coefficient) $$\sum_{k=1}^n \left(-\frac{1}{4}\right)^k {2k\choose k}^2 \frac{1}{1-2k} {n+k-2\choose 2k-2}$$ we seek to show that this is zero when $n$ is odd and $$\left[\left(\frac{1}{4}\right)^m {2m\choose m} \frac{1}{1-2m}\right]^2$$ when $n=2m$ is even. We observe that ...


2

\begin{align} \sum_{n=r}^\infty \binom{n}{r}^{-1} &= \sum_{n=r}^\infty \, (n+1)\int_0^1 x^{n-r} (1-x)^{r}\,dx \\ &= \int_0^1 \left( \sum_{n=r}^\infty (n+1)x^{n-r} \right) (1-x)^r \,dx \\ &= \int_0^1 \frac{1+r-rx}{(1-x)^2} (1-x)^r \,dx \\ &= \frac{r}{r-1} \end{align}


2

The coefficient of $x^k$ in $(x+1)\ldots(x+n)$ is $|S_1(n+1,k+1)|$ where $S_1(\cdot,\cdot)$ are the Stirling numbers of the first kind.


2

Write out what those factorials mean: $$1\cdot 2\cdot 3\cdots (n-2)(n-1)(n)(n+1) = 110 \cdot 1\cdot 2\cdot 3\cdots (n-2)(n-1).$$ What can you cancel from both sides?


2

The sum $$S=\sum_{m=0}^{k} \sum_{n=0}^{m} {k \choose m}{m \choose n}=\sum_{m=0}^{k} {k \choose m}\sum_{n=0}^{m} {m \choose n}= \sum_{m=0}^{k} 2^m {k \choose m}=3^k.$$


1

Maybe it's easier to understand backwards: Taking the $(d-1)$th derivative gives $$ \frac{\mathrm{d}^{(d-1)}}{\mathrm{d}x^{(d-1)}} \left[ \sum_{i=0}^{\infty} x^{i+n+d-1} \right] = \sum_{i=0}^{\infty} \left[ \frac{\mathrm{d}^{(d-1)}}{\mathrm{d}x^{(d-1)}} x^{i+n+d-1} \right] = \sum_{i=0}^{\infty} \frac{(i+n+d-1)!}{(i+n)!} x^{i+n}, $$ since each of the $(d-1)...


1

The answer given by @saulspatz is correct. I would like to give an alternative way to get to the result that helps understanding what is actually going on. The binomial coefficient $\binom{k}{m}$ is the number of ways in which we can choose $m$ elements out of a set of $k$ elements. In other words, it is the number of elements of the set $$\{f:\{x_1,\ldots,...


1

$\newcommand{\usn}[2]{\begin{bmatrix}#1 \\ #2 \end{bmatrix}}$ It is well known that the unsigned Stirling numbers of the first kind can be written as $$\begin{align} \usn{x}{x-1}&=\binom{x}{2} \\ \usn{x}{x-2}&=2\binom{x}{3}+3\binom{x}{4} \\ \usn{x}{x-3}&=6\binom{x}{4}+20\binom{x}{5} + 15\binom{x}{6} \\ \usn{x}{x-4}&=24\binom{x}{5}+130\binom{...


1

Another proof: Let us use $${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$$ Let $$f_k=\sum_{n=k}^{\infty} {n \choose k} \frac{1}{2^n}= \sum_{n=k}^{\infty} {n-1 \choose k}\frac{1}{2^n}+\sum_{n=k}^{\infty} {n-1 \choose k-1} \frac{1}{2^n}.$$ Let $n-1=p$, then $$\Rightarrow f_k=\sum_{p=k-1}^{\infty} {p\choose k} \frac{1}{2^{p+1}}+\sum_{p=k-1} {p\choose k-1}\...


Only top voted, non community-wiki answers of a minimum length are eligible