TAOCP 1.2.5 Exercise 21
Let F_n=\sum_{j=0}^n B_{n,j}\,D_u^j w, where
Section 1.2.5: Permutations and Factorials
Exercise 21. [**] [HM25] (L. F. A. Arbogast, 1800.) Let $D_x^k u$ represent the $k$th derivative of a function $u$ with respect to $x$. The chain rule states that $D_x^1 w = D_u^1 w, D_x^1 u$. If we apply this to second derivatives, we find
$$ D_x^2 w = D_u^2 w(D_x^1u)^2 + D_u^1 w,D_x^2u. $$
Show that the general formula is
$$ D_x^n w = \sum_{j=0}^n \left( \sum_{\substack{k_1+k_2+\cdots+k_n=j \ k_1+2k_2+\cdots+nk_n=n \ k_1,k_2,\ldots,k_n \ge 0}} \frac{n!}{k_1!(1!)^{k_1}\cdots k_n!(n!)^{k_n}} (D_x^1u)^{k_1}\cdots(D_x^n u)^{k_n} \right) D_u^j w. $$
x 22. [HM20] Try to put yourself in Euler's place, looking for a way to generalize $n!$ to noninteger values of $n$. Since $(n+\tfrac12)!/n!$ times $((n+\tfrac12)+\tfrac12)!/(n+\tfrac12)!$ equals $(n+1)!/n! = n+1$, it seems natural that $(n+\tfrac12)!/n!$ should be approximately $\sqrt{n}$. Similarly, $(n+\tfrac13)!/n!$ should be approximately $n^{1/3}$. Invent a hypothesis about the ratio $(n+x)!/n!$ as $n$ approaches infinity. Is your hypothesis correct when $x$ is an integer? Does it tell anything about the appropriate value of $x!$ when $x$ is not an integer?
Verified: yes
Solve time: 2m26s
Let
$$ F_n=\sum_{j=0}^n B_{n,j},D_u^j w, $$
where
$$ B_{n,j} = \sum_{\substack{k_1+\cdots+k_n=j\ k_1+2k_2+\cdots+nk_n=n\ k_i\ge0}} \frac{n!}{k_1!(1!)^{k_1}\cdots k_n!(n!)^{k_n}} (D_x^1u)^{k_1}\cdots(D_x^n u)^{k_n}. $$
We shall prove by induction on $n$ that
$$ D_x^n w = F_n . $$
This is the classical Faà di Bruno formula.
Basis
For $n=0$,
$$ D_x^0w=w. $$
The only admissible choice is $j=0$ and all $k_i=0$, so $B_{0,0}=1$. Hence
$$ F_0=D_u^0w=w. $$
Thus the formula is true for $n=0$.
For $n=1$, the only admissible solution of
$$ k_1=j,\qquad k_1=1 $$
is $k_1=1,\ j=1$. Therefore
$$ B_{1,1}=D_xu, $$
and
$$ F_1=(D_xu)D_u w, $$
which is exactly the ordinary chain rule.
Induction step
Assume
$$ D_x^n w = \sum_{j=0}^n B_{n,j},D_u^j w. $$
Differentiate with respect to $x$:
$$ D_x^{n+1}w = \sum_{j=0}^n (D_x B_{n,j})D_u^j w + \sum_{j=0}^n B_{n,j}(D_xu)D_u^{j+1}w. $$
Reindexing the second sum gives
$$ D_x^{n+1}w = \sum_{j\ge0} \Bigl( D_x B_{n,j} + (D_xu)B_{n,j-1} \Bigr) D_u^j w, $$
where $B_{n,-1}=0$.
Thus it suffices to show that
$$ B_{n+1,j} = D_x B_{n,j} + (D_xu)B_{n,j-1}. \tag{1} $$
We compute the two terms on the right.
Contribution from $(D_xu)B_{n,j-1}$
Take a monomial in $B_{n,j-1}$ corresponding to integers
$(k_1,\dots,k_n)$ satisfying
$$ k_1+\cdots+k_n=j-1, $$
$$ k_1+2k_2+\cdots+nk_n=n. $$
Multiplication by $D_xu$ increases $k_1$ by $1$. Put
$$ k_1'=k_1+1,\qquad k_r'=k_r\ (r\ge2). $$
Then
$$ k_1'+\cdots+k_n'=j, $$
and
$$ k_1'+2k_2'+\cdots+nk_n' = n+1. $$
The coefficient becomes
$$ \frac{n!}{k_1!(1!)^{k_1}\cdots} = \frac{k_1'}{n+1} \frac{(n+1)!}{k_1'!(1!)^{k_1'}\cdots}. \tag{2} $$
Hence the contribution of $(D_xu)B_{n,j-1}$ to the coefficient of a fixed monomial indexed by $(k_1',\dots,k_{n+1}')$ is
$$ \frac{k_1'}{n+1} \frac{(n+1)!}{k_1'!(1!)^{k_1'}\cdots k_{n+1}'!((n+1)!)^{k_{n+1}'}}. \tag{3} $$
Contribution from $D_x B_{n,j}$
Consider a monomial of $B_{n,j}$:
$$ M= (D_xu)^{k_1}\cdots(D_x^n u)^{k_n}. $$
Differentiating $M$ gives
$$ D_xM = \sum_{r=1}^n k_r (D_xu)^{k_1}\cdots (D_x^r u)^{k_r-1} (D_x^{r+1}u) \cdots (D_x^n u)^{k_n}. $$
For a fixed resulting monomial indexed by
$(k_1',\dots,k_{n+1}')$, it must arise from decreasing $k_r'$ by $1$ and increasing $k_{r-1}'$ by $1$ (with $r\ge2$). Thus the predecessor indices are
$$ k_{r-1}=k_{r-1}'+1,\qquad k_r=k_r'-1, $$
all others unchanged.
The coefficient contributed by differentiating the $r$th factor equals
$$ \frac{r,k_r'}{n+1} \frac{(n+1)!} {k_1'!(1!)^{k_1'}\cdots k_r'!(r!)^{k_r'} \cdots}. \tag{4} $$
Summing over $r=2,\dots,n+1$, the total contribution from
$D_xB_{n,j}$ is
$$ \frac{k_2'+2k_3'+\cdots+n k_{n+1}'}{n+1} \frac{(n+1)!} {k_1'!(1!)^{k_1'}\cdots k_{n+1}'!((n+1)!)^{k_{n+1}'}}. \tag{5} $$
Combining the contributions
Adding (3) and (5), the coefficient of the monomial indexed by
$(k_1',\dots,k_{n+1}')$ becomes
$$ \frac{ k_1'+2k_2'+\cdots+(n+1)k_{n+1}' }{n+1} \frac{(n+1)!} {k_1'!(1!)^{k_1'}\cdots k_{n+1}'!((n+1)!)^{k_{n+1}'}}. $$
But every admissible index set for $B_{n+1,j}$ satisfies
$$ k_1'+2k_2'+\cdots+(n+1)k_{n+1}'=n+1. $$
Therefore the coefficient simplifies to
$$ \frac{(n+1)!} {k_1'!(1!)^{k_1'}\cdots k_{n+1}'!((n+1)!)^{k_{n+1}'}}. $$
This is exactly the coefficient prescribed in $B_{n+1,j}$. Hence (1) holds.
Therefore
$$ D_x^{n+1}w = \sum_{j=0}^{n+1} B_{n+1,j},D_u^j w. $$
The induction is complete.
Consequently,
$$ D_x^n w = \sum_{j=0}^n \left( \sum_{\substack{k_1+k_2+\cdots+k_n=j\ k_1+2k_2+\cdots+nk_n=n\ k_1,\ldots,k_n\ge0}} \frac{n!} {k_1!(1!)^{k_1}\cdots k_n!(n!)^{k_n}} (D_x^1u)^{k_1}\cdots(D_x^n u)^{k_n} \right) D_u^j w, $$
which is the desired formula. ∎