## Solution to an elementary problem posed by T. Tao

In his most recent post, Prof. Tao shared the following elementary discovery:

$\forall k \in \{0,1,2\cdots \}: \frac{d^{k+1}}{dx^{k+1}} (1+x^2)^{k/2} = \begin{cases} 0 & k \text{ is even} \\ \frac{(1 \times 3 \times \cdots \times k)^2}{(1+x^2)^{(k+2)/2}} & k \text{ is odd} \end{cases}$

He first discovered this empirically in the course of his research, and then found a short proof. He didn’t share the proof on his blog yet, and instead challenged the readers to find their own proofs and observations. In this short post I’ll share a nice solution of mine. (There are some partial solutions I might add later, if I’ll be able to complete them).

The key is Leibniz’ rule. We begin by writing $(1+x^2)^{k/2}$ as a product: $(x+i)^{k/2} \times (x-i)^{k/2}$. We need to differentiate this product $(k+1)$ times, and we do this by applying Leibniz’ rule repeatedly:

$\frac{d^{k+1}}{dx^{k+1}} (1+x^2)^{k/2} = \sum_{n+m=k+1} \binom{k+1}{n} (k/2)_{n} (x+i)^{k/2 - n} (k/2)_{m} (x-i)^{k/2-m}$

(The notation $(x)_n$ stands for “falling factorial”: $x(x-1)\cdots (x-(n-1))$.)
The crucial observation is that:

$\text{Observation: }\forall n+m=k+1: (k/2)_{n} (k/2)_{m} = (k/2)_{k+1} (-1)^m =\begin{cases} 0 & k \text{ is even} \\ (-1)^m (-\frac{1}{4})^{\frac{k+1}{2}} (1 \times 3 \times \cdots \times k)^2 & k \text{ is odd} \end{cases}$

Given this observation (which we’ll explain shortly), the even case is immediate and the odd case follows directly from the binomial theorem:

\begin{aligned} \sum_{n+m=k+1} \binom{k+1}{n} (k/2)_{n} (x+i)^{k/2 - n} (k/2)_{m} (x-i)^{k/2-m} &= (k/2)_{k+1} (x^2+1)^{k/2} \sum_{n+m=k+1}\binom{k+1}{n} (-1)^m (x+i)^{-n} (x-i)^{-m} \\ &= (k/2)_{k+1} (x^2+1)^{k/2} (\frac{-1}{x-i}+\frac{1}{x+i})^{k+1} \\ &= (k/2)_{k+1} (x^2+1)^{k/2} (\frac{-2i}{x^2+1})^{k+1} \\ &= \frac{(1 \times 3 \times \cdots \times k)^2}{(x^2+1)^{(k+2)/2}} \end{aligned}

To explain the observation, note that in the even case $(k/2)_n$ contains the term $0$ whenever $n > \frac{k}{2}$. In the odd case we need to write explicitly the terms in all 3 expressions (which are given as products), and seeing that they are the same (up to reordering and\or sign) – if we assume $n \ge m = k+1-n$ (w.l.o.g) we find:

\begin{aligned} (k/2)_n (k/2)_{m} &= \left( \frac{k}{2} (\frac{k}{2}-1) \cdots (\frac{k}{2} - (n-1)) \right) \left( \frac{k}{2} (\frac{k}{2}-1) \cdots (n-\frac{k}{2}) \right) \\ &=\left( \frac{k}{2} (\frac{k}{2}- 1) \cdots (n-\frac{k}{2}) \right)^2 \left( (n-\frac{k}{2}-1) \cdots (\frac{k}{2}+1-n) \right)\\ &=\left( \frac{k}{2} \cdots (n-\frac{k}{2}) \cdot (n-\frac{k}{2}-1) \cdots (\frac{k}{2}+1-n) \cdot (\frac{k}{2}-n) \cdots \frac{-k}{2} \right) (-1)^m \\ &= (k/2)_{k+1} (-1)^m \end{aligned}

And that:

$(1 \times 3 \cdots \times k)^2 = (k \cdot (k-2) \cdots 1 \cdot (-1) \cdots (-k)) (-1)^{\frac{k+1}{2}} = (\frac{k}{2} (\frac{k}{2}-1) \cdots \frac{-k}{2}) (-4)^{\frac{k+1}{2}} = (k/2)_{k+1} (-4)^{\frac{k+1}{2}}$

There’s no clever combinatorial explanation\algebraic manipulation needed. This is why I think of this as a tautological identity, although it is surprising at first sight.

Posted in Uncategorized | 1 Comment

## 5 Short Proofs of Simplified Stirling’s Approximation

(This post was converted from tex to html using the wonderful free tool “LaTeX  to WordPress”. You can find a PDF version in the “Documents” section.)

0. Introduction

Stirling’s approximation is the following (somewhat surprising) approximation of the factorial, ${ n!}$, using elementary functions:

$\displaystyle n!\sim(\frac{n}{e})^{n}\sqrt{2\pi n} \ \ \ \ \ (1)$

(${f(n)\sim g(n)}$ means: the ratio ${\frac{f(n)}{g(n)}}$ tends to 1 as ${n}$ goes to infinity.) It was proved in 1730 by the Scottish mathematician James Stirling.

This approximation has many applications, among them – estimation of binomial and multinomial coefficients. It has various different proofs, for example:

• Applying the Euler-Maclaurin formula on the integral ${\int_{1}^{n} \ln x \, dx}$.
• Using Cauchy’s formula from complex analysis to extract the coefficients of ${e^{x}}$: ${\frac{1}{n!}=\frac{1}{2\pi i}\int_{|z|=n}\frac{e^{z}}{z^{n+1}} \, dz}$.

Those proofs are not complicated at all, but they are not too elementary either. In this short note I will present, using guided exercises, 5 different proofs for weaker versions of Stirling’s approximation. In most of the real-life applications, the weaker versions are more than enough. The proofs are self-contained and completely elementary – nothing more than basic calculus (integration and differentiation, Taylor series, definitions of ${e}$ and ${e^{x}}$) is required. Continue reading