Joy of Mathematics

A binomial sum

October 22, 2022 Tolaso

Evaluate the sum

$\sum_{k=0}^n \binom{n}{k}\frac{k!}{(n+1+k)!}$

Solution

We have successively

$\begin{align*} \sum_{k=0}^n \binom{n}{k}\frac{k!}{(n+1+k)!} &= \sum_{k=0}^{n} \frac{n!}{\left ( n-k \right )! \left ( n+k+1 \right )!} \\ &=\frac{n!}{\left ( 2n+1 \right )!} \sum_{k=0}^{n} \binom{2n+1}{n-k} \\ &= \frac{n!}{\left ( 2n+1 \right )!} \sum_{k=0}^{n} \binom{2n+1}{k} \\ &=\frac{n!}{2 \cdot \left ( 2n+1 \right )!} \sum_{k=0}^{2n+1} \binom{2n+1}{k} \\ &= \frac{n! \cdot 2^{2n}}{\left ( 2n+1 \right )!} \end{align*}$

Binomial sum

February 1, 2021February 2, 2021 Tolaso

Let $m, n$ be positive numbers with $n > m$ . Prove that

$\sum_{k=0}^{n} (-1)^k \binom{n}{k} \binom{m+n-2k}{n-1} = \binom{n}{m+1}$

Solution

Using the exercise here we have that

$\binom{n}{m} = \frac{1}{2\pi i } \oint \limits_{\left | z \right |=1} \frac{\left ( z+1 \right )^n}{z^{m+1}}\, \mathrm{d}z$

Hence,

$\begin{aligned} \sum_{k=0}^{n} (-1)^k \binom{n}{k} \binom{m+n-2k}{n-1} &= \frac{1}{2\pi i } \sum_{k=0}^{n} (-1)^k \binom{n}{k} \oint \limits_{\left | z \right |=1} \frac{\left ( 1+z \right )^{m+n-2k}}{z^n}\, \mathrm{d}z \\ &=\frac{1}{2\pi i } \oint \limits_{\left | z \right |=1} \frac{\left ( z+1 \right )^{m+n}}{z^n} \sum_{k=0}^{n} (-1)^k \binom{n}{k} \frac{\mathrm{d}z}{\left ( z+1 \right )^{2k}} \\ &= \frac{1}{2\pi i } \oint \limits_{\left | z \right |=1} \frac{\left ( z+1 \right )^{m+n}}{z^n} \left ( 1 - \frac{1}{\left ( z+1 \right )^2} \right )^n \, \mathrm{d}z \\ &= \frac{1}{2\pi i} \oint \limits_{\left | z \right |=1} \frac{\left ( z+2 \right )^n}{\left ( z+1 \right )^{n-m}}\, \mathrm{d}z \\ &=\mathfrak{Res}_{z =-1} \frac{\left ( z+2 \right )^n}{\left ( z+1 \right )^{n-m}} \\ &= \lim_{z \rightarrow -1} \frac{1}{\left ( n-m-1 \right )!} \frac{\mathrm{d}^{n-m-1} }{\mathrm{d} z^{n-m-1}} \left (\left ( z+2 \right )^n \right ) \\ &= \binom{n}{m+1} \end{aligned}$

Binomial coefficients as multiple sum

April 5, 2020 Tolaso

Prove that

$\sum_{n_1=1}^{n-1} \sum_{n_2=1}^{n_1-1} \sum_{n_3=1}^{n_2-1} \cdots \sum_{n_m=1}^{n_{m-1}-1} 1 = \binom{n-1}{m}$

Solution

The binomial coefficient in the RHS enumerates the subsets $A$ of size $m$ of $\{1,2,\ldots,n-1\}$ . The LHS does the same thing, but choosing first the largest element $n_1$ of $A$ , then its second-to-largest element $n_2 < n_1$ , until choosing its smallest element $n_m$ .

On the factorial

March 17, 2020 Tolaso

Let $\mu$ denote the Möbius function and $\left \lfloor \cdot \right \rfloor$ denote the floor function. Prove that:

$n! = \prod_{j=1}^{\infty} \prod_{i=1}^{\infty} \left ( \left \lfloor \frac{n}{ij} \right \rfloor! \right )^{\mu(i)}$

Solution

The RHS equals

$\begin{align*} \prod_{j=1}^{\infty} \prod_{i=1}^{\infty} \left ( \left \lfloor \frac{n}{ij} \right \rfloor! \right )^{\mu(i)} &= \prod_{k=1}^n \prod_{i|k} \left( \left \lfloor \frac{n}{k}\right\rfloor!\right)^{\mu(i)} \\ &= \prod_{k=1}^n \left( \left \lfloor \frac{n}{k}\right\rfloor!\right)^{\sum_{i|k}\mu(i)} \\ &= n! \end{align*}$

since $\sum \limits_{i | k} \mu(i) = 0$ for $k>1$ .

Sum over all positive rationals

February 22, 2020 Tolaso

For a rational number $x$ that equals $\frac{a}{b}$ in lowest terms , let $f(x)=ab$ . Prove that:

$\sum_{x \in \mathbb{Q}^+} \frac{1}{f^2(x)} = \frac{5}{2}$

Solution

First of all we note that

$F(s) = \sum_{x \in \mathbb{Q}^+} \frac{1}{f^s(x)} = \sum_{\substack{a,b=1 \\ \gcd(a, b)=1}}^{\infty} \frac{1}{\left ( ab \right )^s}$

Moreover for $s>1$ we have that

$\begin{align*} \zeta^2(s) &= \left ( \sum_{a=1}^{\infty} \frac{1}{a^s} \right )^2 \\ &=\sum_{a, b=1}^{\infty} \frac{1}{(ab)^s} \\ &=\sum_{d=1}^{\infty} \sum_{\substack{a, b=1 \\\gcd(a, b)=d}}^{\infty} \frac{1}{\left ( ab \right )^s} \\ &= \sum_{d=1}^{\infty} \frac{1}{d^{2s}} \sum_{\substack{a, b=1 \\\gcd(a, b)=1}}^{\infty} \frac{1}{\left ( ab \right )^s} \\ &= \zeta(2s) F(s) \end{align*}$

Hence for $s=2$ we have that

$F(2) = \frac{5}{2}$