Faà di Bruno's Formula/Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $D_x^k u$ denote the $k$th derivative of a function $u$ with respect to $x$.

Then:

$\displaystyle D_x^n w = \sum_{j \mathop = 0}^n D_u^j w \sum_{\substack {\sum_{p \mathop \ge 1} k_p \mathop = j \\ \sum_{p \mathop \ge 1} p k_p \mathop = n \\ \forall p \mathop \ge 1: k_p \mathop \ge 0} } n! \prod_{m \mathop = 1}^n \dfrac {\left({D_x^m u}\right)^{k_m} } {k_m! \left({m!}\right)^{k_m} }$


Proof

For convenience, let:

$w_j := D_u^j w$
$u_k := D_x^k u$


Then:

\(\ds D_x \left({w_j}\right)\) \(=\) \(\ds w_{j + 1} u_1\) Derivative of Composite Function
\(\ds D_x \left({u_k}\right)\) \(=\) \(\ds u_{k + 1}\) Definition of Higher Derivative


Thus:

\(\ds D_x^1 w\) \(=\) \(\ds w_1 u_1\) Derivative of Composite Function
\(\ds D_x^2 w\) \(=\) \(\ds \left({w_2 u_1 u_1 + w_1 u_2}\right)\) Derivative of Composite Function: Second Derivative
\(\ds D_x^3 w\) \(=\) \(\ds \left({\left({w_3 u_1 u_1 u_1 + w_2 u_2 u_1 + w_2 u_1 u_2}\right) + \left({w_2 u_1 u_2 + w_1 u_3}\right)}\right)\) Derivative of Composite Function: Third Derivative or directly


Analogously, let a corresponding tableau be set up of set partitions as follows:

\(\ds \mathcal D^1\) \(=\) \(\ds \set 1\)
\(\ds \mathcal D^2\) \(=\) \(\ds \set {\set 2 \mid \set 1} + \set {2, 1}\)
\(\ds \mathcal D^3\) \(=\) \(\ds \set {\set 3 \mid \set 2 \mid \set 1} + \set {\set {3, 2} \mid \set 1} + \set {\set 2 \mid \set {3, 1} } + \set {\set 3 \mid \set {2, 1} } + \set {3, 2, 1}\)


Thus inspired, let $a_1 a_2 \cdots a_j$ denote a partition of the set $\set {1, 2, \ldots, n-1}$.

Let:

\(\ds \mathcal D a_1 a_2 \cdots a_j\) \(:=\) \(\ds \set n a_1 a_2 \cdots a_j\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds \left({a_1 \cup \set n}\right) a_2 \cdots a_j\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds a_1 \left({a_2 \cup \set n}\right) \cdots a_j\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds \cdots\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds a_1 a_2 \cdots \left({a_j \cup \set n}\right)\)


This rule is isomorphic to:

\(\ds D_x \left({w_j u_{r_1} u_{r_2} \ldots u_{r_j} }\right)\) \(=\) \(\ds w_{j + 1} u_1 u_{r_1} u_{r_2} \ldots u_{r_j}\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds w_j u_1 u_{r_1 + 1} u_{r_2} \ldots u_{r_j}\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds w_j u_1 u_{r_1} u_{r_2 + 1} \ldots u_{r_j}\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds \cdots\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds w_j u_1 u_{r_1} u_{r_2} \ldots u_{r_j + 1}\)

where the term $w_j u_{r_1} u_{r_2} \ldots u_{r_j}$ corresponds to a partition $a_1 a_2 \cdots a_j$.

Thus there exists a bijection from $\mathcal D^n$ to $D_x^n w$.



Thus, collecting like terms in $D_x^n w$, we obtain a sum of terms:

$c \left({k_1, k_2, \ldots}\right) w_j u_i^{k_1} u_2^{k_2} \ldots$

where:

$j = k_1 + k_2 + \cdots$

and:

$n = k_1 + 2 k_2 + \cdots$

and where:

$c \left({k_1, k_2, \ldots}\right)$ is the number of partitions of $\set {1, 2, \ldots, n}$ into $j$ subsets where there are $k_t$ subsets with $t$ elements.


Consider an array of $k_t$ boxes of capacity $t$.

The number of ways to put $n$ different elements into these boxes is the multinomial coefficient:

$\dbinom n {1, 1, \ldots, 1, 2, 2, \ldots, 2, 3, 3, \ldots, 3, 4, \ldots} = \dfrac {n!} {\left({1!}\right)^{k_1} \left({2!}\right)^{k_2} \left({3!}\right)^{k_3} \cdots}$

It remains to divide by $k_1! \, k_2! \, k_3! \ldots$ corresponding to the number of ways each group of $k_t$ can be permuted

Hence:

$c \left({k_1, k_2, \ldots}\right) = \dfrac {n!} {k_1! \left({1!}\right)^{k_1} \, k_2! \left({2!}\right)^{k_2} k_3! \left({3!}\right)^{k_3} \cdots}$

and the result follows.

$\blacksquare$


Source of Name

This entry was named for Francesco Faà di Bruno.


Sources