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.

Advertisements
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

Posted in analysis, Uncategorized | Leave a comment

First post.

So here I am, starting my own maths blog. In English, in the world wide web, available for anyone interested in maths and sciene and has an internet connection.

I am a little bit excited. Continue reading

Posted in Uncategorized | Leave a comment