# Derivative formula

While trying to understand a paper of Cayley, he left something unexplained, I managed to show that it is equivalent to the following formula, which I got stuck at:

$k \cdot (f^k)^{(k-1)} = \sum_{j=0}^{k-1} {{k} \choose {j}} (f^{j})^{(j)}(f^{k-j})^{(k-j-1)}$

Can somebody help?

• I'm not sure why this was closed. Experiment with Maple shows that the formula holds when $k=9$ and $f$ is a polynomial of degree $10$, and this is big enough to convince me that it must be true in general. However, I do not see any obvious proof. – Neil Strickland Feb 14 '17 at 15:40
• @NeilStrickland I agree. I expect there would be a nice combinatorial interpretation as well. Do those who voted to close consider it obvious? It looks similar to a Leibniz product formula for higher derivatives, but I don't see how it follows trivially. – Todd Trimble Feb 14 '17 at 16:21
• I also don't see why this was closed. – Richard Stanley Feb 14 '17 at 17:12
• See Warren P. Johnson, The Pfaff/Cauchy derivative identities and Hurwitz type extensions, The Ramanujan Journal 13 (2007) pp. 167–201, link.springer.com/article/10.1007/s11139-006-0246-0, or my survey paper on Lagrange inversion, Journal of Combinatorial Theory, Series A 144 (2016) pp. 212–249, arxiv.org/abs/1609.05988, section 2.6. – Ira Gessel Feb 14 '17 at 17:38
• Which paper of Cayley? – Tom Copeland Feb 14 '17 at 19:06

A detailed historical discussion of identities like this one can be found in Warren P. Johnson's paper The Pfaff/Cauchy derivative identities and Hurwitz type extensions, The Ramanujan Journal 13 (2007) pp. 167–201. In particular, his formula (1.3) is $$\frac{d^n\ }{dx^n} \phi^n(x) u(x) v(x) = \sum_{k=0}^n \binom nk \left(\frac{d^k\ }{dx^k} \phi^k(x) u(x)\right) \left(\frac{d^{n-k-1}}{dx^{n-k-1}}\phi^{n-k}(x) v'(x)\right)\tag{1}$$ where for $n=k$, $\frac{d^{n-k-1}}{dx^{n-k-1}}\phi^{n-k}(x) v'(x)$ is to be interpreted as $v(x)$. This identity was given by Cauchy in 1826, but is equivalent to an identity given by Pfaff in 1795.

The OP's identity is equivalent to the case $\phi(x)=f$, $u(x)=1$, $v(x) = x$.

There is a related formula in Cayley's paper On the partitions of a polygon, Coll. Math. Papers 13 (1897), 93–113; Proc. London Math. Soc. (1) 22 (1891), 237–262, but I didn't see this formula there.

Formulas like $(1)$ are discussed in my survey paper Lagrange Inversion, Journal of Combinatorial Theory, Series A 144 (2016), pp. 212–249, section 2.6.

There is also a discussion of a somewhat related formula on Terry Tao's blog at https://terrytao.wordpress.com/2016/10/23/another-problem-about-power-series.

In addition to Ira Gessel's answer, let me explain how such Pfaff-Cauchy-Hurwitz type identities are connected to polynomial interpolation techniques and to Raney lemma.

Denote ${\bf k}=\{1,\dots,k\}$.

We prove a more general (not polynomial in $f$, but multilinear in $f_1,\dots,f_k$) identity $$k(f_1\dots f_k)^{(k-1)}=\sum_{\emptyset\ne A\subset{\bf k}}\left(\prod_{i\in A} f_i\right)^{(|A|-1)}\left(\prod_{i\notin A} f_i\right)^{(n-|A|)}.$$ It suffices to prove this identity when all $f_i$'s are power functions $f_i(t)=t^{x_i}$ (by some standard abstract nonsense). In this case we get a polynomial identity in $x_i's$ (where we denote $(x)_n=x(x-1)\dots(x-n+1)$, and also denote $s(A)=\sum_{i\in A}x_i$): $$k(s({\bf k}))_{k-1}=\sum_{A\sqcup B={\bf k},A\ne \emptyset}(s(A))_{|A|-1}\,(s(B))_{|B|}.$$ Both parts are polynomials of degree at most $k-1$, and it suffices to check that they coincide on the following combinatorial simplex $\Delta$: $x_i$ take non-negative integral values such that $\sum x_i\leqslant k-1$.

Note that for any $(x_1,\dots,x_k)\in \Delta$ and any partition ${\bf k}=A\sqcup B$, $A\ne \emptyset$, we have $s(A)+s(B)=s({\bf k})\leqslant k-1$, thus either $s(A)<|A|-1$ or $s(B)<|B|$ or $s(A)=|A|-1,s(B)=|B|$, $s({\bf k})=k-1$. Thus if $s({\bf k})<k-1$ both parts vanish, and if $s({\bf k})=k-1$, we have to prove that $$k!=\sum_{A:s(A)=|A|-1} (|A|-1)! (k-|A|)!$$ I know this identity from Andrei Zelevinsky (2008). Here is his manuscript containing a clever proof both of combinatorial and falling factorials identities. Andrei asked not to circulate this text, but I think that this request is out of date...

Consider a permutation $\pi=(c_1,\dots,c_k)$ of $1,2,\dots,k$. Choose minimal $m$ for which $s(\{c_1,\dots,c_m\})<m$. Then by minimality $s(\{c_1,\dots,c_m\})=m-1$. For how many permutations did we have $\{c_1,\dots,c_m\}=A$, where $A$ is a fixed subset of ${\bf k}$ with $s(A)=|A|-1$? The answer is $(|A|-1)!|B|!$, since for any fixed cyclic order $(c_1,\dots,c_m)$ of $A$ exactly one out of $m$ permutations $(c_{i+1},c_{i+2},\dots,c_i)$ satisfies $s(c_{i+1},\dots,c_{i+t})\geqslant t$ for all $t=1,2,\dots,m-1$. This is a variant of Raney's lemma. Thus the identity.

We may avoid combinatorial arguments with Raney's lemma and remain entirely in algebra. The following trick is suggested by Vlad Volkov: we instead check the points for which $(x_1,\dots,x_{k-1},x_k+1)\in \Delta$. In this case $\sum x_i\in \{-1,0,1,\dots,k-2\}$ and LHS equals 0 unless $x_1=\dots=x_{k-1}=0$, $x_k=-1$. In this last case LHS equals $(-1)^{k-1}k!$. Check the same for RHS. Always either $s(A)<|A|-1$ or $s(B)<|B|=k-|A|$, thus if the corresponding summand in RHS is non-zero, one of the sets $A$, $B$ has a sum of $x$'s equal to -1, i.e., consists of $k$ and several indices $i$ such that $x_i=0$. After some calculations everything reduces to Vandermonde--Chu identity.

Now a bit about multidimensional interpolation. Consider the space $\Pi(n,k)$ of polynomials $f(x_1,\dots,x_k)$ with degree at most $n$. Its dimension equals the number of monomials $x_1^{c_1}\dots x_k^{c_k}$, where $c_i$ are non-negative integers such that $\sum c_i\leqslant n$, we write this as $(c_1,\dots,c_k)\in \Delta_n^k$. Thus if we manage to find $|\Delta_n^k|$ linearly independent linear forms on $\Pi(n,k)$, then the polynomial $f\in \Pi(n,k)$ is uniquely determined by the values of these forms. I claim that the values at points of $\Delta_n^k$ serve as such linear forms. For proving that they are linearly independent we may simply construct a polynomial from $\Pi(n,k)$ which vanishes at all points of $\Delta_n^k$ but the given point $(t_1,\dots,t_k)$. Here it comes: $$\prod_{i=1}^k \prod_{j=0}^{t_i-1}(x_i-j)\cdot \prod_{\ell=t_1+\dots+t_k+1}^n (x_1+\dots+x_k-\ell).$$

• This looks really neat, but can you remind us why it suffices to check that identity on $\Delta$ ? – darij grinberg Feb 15 '17 at 20:18
• @darijgrinberg I explained, there are many other explanations. See also a more general form of this lemma (Observation 2.2) here: link.springer.com/article/10.1007/s40879-016-0099-z with several applications in spirit of the hook length formula – Fedor Petrov Feb 15 '17 at 21:40
• Ah! That's a beautiful identity; I expected some boring induction argument.. The identity you attribute to Zelevinsky, on the other hand, I remember seeing in a math contest (SPbMO?); maybe it was him who proposed it there? – darij grinberg Feb 16 '17 at 21:44
• @darijgrinberg yes, I asked him to use it on SPbMO and he kindly agreed – Fedor Petrov Feb 16 '17 at 21:48
• Ah :) By the way, has there been any progress on getting the problems and solutions (for SPbMO and 239MO) published in English? I remember that even finding the Russian version (from outside of Russia) was a challenge back when I was studying for contests... – darij grinberg Feb 16 '17 at 22:11