In his most recent post, Prof. Tao shared the following elementary discovery:
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 as a product: . We need to differentiate this product times, and we do this by applying Leibniz’ rule repeatedly:
(The notation stands for “falling factorial”: .)
The crucial observation is that:
Given this observation (which we’ll explain shortly), the even case is immediate and the odd case follows directly from the binomial theorem:
To explain the observation, note that in the even case contains the term whenever . 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 (w.l.o.g) we find:
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.