Faà di Bruno's Formula

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} }$


Examples

Example: $n = 0$

$D_x^0 w = w$


Example: $n = 1$

$D_x^1 w = D_u^1 w D_x^1 u$


Example: $n = 2$

$D_x^2 w = D_u^2 w \left({D_x^1 u}\right)^2 + D_u^1 w D_x^2 u$


Proof 1

The proof proceeds by induction on $n$.

For all $n \in \Z_{\ge 0}$, let $P \left({n}\right)$ be the proposition:

$\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} }$


The case for $n = 0$ is:

$D_x^0 w = w$

which is consistent with the definition of the zeroth derivative.


The case for $n = 1$ is:

$D_x^1 w = D_u^1 w D_x^1 u$

which is consistent with Derivative of Composite Function.


Basis for the Induction

$P \left({2}\right)$ is the case:

$D_x^2 w = D_u^2 w \left({D_x^1 u}\right)^2 + D_u^1 w D_x^2 u$


This is consistent with Derivative of Composite Function: Second Derivative.

This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $P \left({r}\right)$ is true, where $r \ge 2$, then it logically follows that $P \left({r + 1}\right)$ is true.


So this is the induction hypothesis:

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


from which it is to be shown that:

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


Induction Step

This is the induction step:


Note that when $k_m = 0$:

$\dfrac {\left({D_x^m u}\right)^{k_m} } {k_m! \left({m!}\right)^{k_m} } = 1$

which shows that any contribution to the summation where $k_m = 0$ can be disregarded.


Let $j = 0$.

Consider the set of $k_p$ such that:

$k_1 + k_2 + \cdots = 0$
$1 \times k_1 + 2 k_2 + \cdots = r$
$k_1, k_2, \ldots \ge 0$

It is apparent by inspection that, for all $r > 0$, no set of $k_p$ can fulfil these conditions.

Therefore when $j = 0$ the summation is vacuous.


Also note that from:

$1 \times k_1 + 2 k_2 + \cdots = r$

it follows that:

$k_{r + 1} = k_{r + 2} = \cdots = 0$

Thus, while there are only finitely many $k$'s, their upper limit need not be explicitly considered.


Let $c \left({r, j, k_1, k_2, \ldots}\right)$ be the coefficient of $D_u^j w$ in $D_x^r w$.


We establish some lemmata:

Lemma 1:

$D_x \left({\left({D_x^m u}\right)^{k_m} }\right) = k_m \left({D_x^m u}\right)^{k_m - 1} D_x^{m + 1} u$


Lemma 2:

$\displaystyle D_x \left({\prod_{m \mathop = 1}^r \left({\dfrac {\left({D_x^m u}\right)^{k_m} } {k_m! \left({m!}\right)^{k_m} } }\right) }\right) = \prod_{m \mathop = 1}^r \left({\dfrac {\left({D_x^m u}\right)^{k_m} } {k_m! \left({m!}\right)^{k_m} } }\right) \sum_{m \mathop = 1}^r k_m \dfrac {D_x^{m + 1} u} {D_x^m u}$



By differentiating with respect to $x$:

\(\displaystyle c \left({r + 1, j, k_1, k_2, \ldots}\right)\) \(=\) \(\displaystyle c \left({r, j - 1, k_1 - 1, k_2, \ldots}\right)\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({k_1 + 1}\right) c \left({r, j, k_1 + 1, k_2 - 1, k_3, \ldots}\right)\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({k_2 + 1}\right) c \left({r, j, k_1, k_2 + 1, k_3 - 1, k_4, \ldots}\right)\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \cdots\)

The equations:

$k_1 + k_2 + \cdots = j$

and:

$k_1 + 2 k_2 + \cdots = r$

are preserved by this induction step.

Thus it is possible to factor out:

$\dfrac {r!} {k_1! \left({1!}\right)^{k_1} \cdots k_r! \left({r!}\right)^{k_r} }$

from each term on the right hand side of the equation for $c \left({r + 1, j, k_1, k_2, \ldots}\right)$.

Thus we are left with:

$k_1 + 2 k_2 + 3 k_3 + \cdots = r + 1$


So $P \left({r}\right) \implies P \left({r + 1}\right)$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\displaystyle \forall n \in \Z_{\ge 0}: 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 2

For convenience, let:

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


Then:

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


Thus:

\(\displaystyle D_x^1 w\) \(=\) \(\displaystyle w_1 u_1\) Derivative of Composite Function
\(\displaystyle D_x^2 w\) \(=\) \(\displaystyle \left({w_2 u_1 u_1 + w_1 u_2}\right)\) Derivative of Composite Function: Second Derivative
\(\displaystyle D_x^3 w\) \(=\) \(\displaystyle \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:

\(\displaystyle \mathcal D^1\) \(=\) \(\displaystyle \set 1\)
\(\displaystyle \mathcal D^2\) \(=\) \(\displaystyle \set {\set 2 \mid \set 1} + \set {2, 1}\)
\(\displaystyle \mathcal D^3\) \(=\) \(\displaystyle \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}$.

Let:

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


This rule is isomorphic to:

\(\displaystyle D_x \left({w_j u_{r_1} u_{r_2} \ldots u_{r_j} }\right)\) \(=\) \(\displaystyle w_{j + 1} u_1 u_{r_1} u_{r_2} \ldots u_{r_j}\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle w_j u_1 u_{r_1 + 1} u_{r_2} \ldots u_{r_j}\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle w_j u_1 u_{r_1} u_{r_2 + 1} \ldots u_{r_j}\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \cdots\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle 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$


Proof 3

We have that:

$\dfrac {D_x^k u} {k!}$ is the coefficient of $z^k$ in $u \left({x + z}\right)$
$\dfrac {D_u^j w} {j!}$ is the coefficient of $y^j$ in $w \left({u + y}\right)$.

Hence the coefficient of $z^n$ in $w \left({u \left({x + z}\right)}\right)$ is:

$\dfrac {D_x^n w} {n!} = \displaystyle \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} } \dfrac {j!} {k_1! \, k_2! \cdots k_n!} \left({\dfrac {D_x^1 u} {1!} }\right)^{k_1} \left({\dfrac {D_x^2 u} {2!} }\right)^{k_2} \cdots \left({\dfrac {D_x^n u} {n!} }\right)^{k_n}$



Proof 4

$D_x^n$ can be expressed as a determinant:

$D_x^n = \begin{vmatrix} \dbinom {n - 1} 0 u_1 & \dbinom {n - 1} 1 u_2 & \dbinom {n - 1} 2 u_3 & \cdots & \dbinom {n - 1} {n - 2} u_{n - 1} & \dbinom {n - 1} {n - 1} u_n \\ -1 & \dbinom {n - 2} 0 u_1 & \dbinom {n - 2} 1 u_2 & \cdots & \dbinom {n - 2} {n - 3} u_{n - 2} & \dbinom {n - 2} {n - 2} u_{n - 1} \\ 0 & -1 & \dbinom {n - 3} 0 u_1 & \cdots & \dbinom {n - 3} {n - 4} u_{n - 3} & \dbinom {n - 3} {n - 3} u_{n - 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & -1 & \dbinom 0 0 u_1 \end{vmatrix}$

where $u_j := \left({D_x^j u}\right) D_u$.

Both sides of this equation are differential operators which are to be applied to $w$.



Also known as

Some sources refer to this as Arbogast's formula for Louis François Antoine Arbogast who actually deduced this first.


Source of Name

This entry was named for Francesco Faà di Bruno.


Historical Note

While Faà di Bruno's Formula was named after Francesco Faà di Bruno, he was not the first to state it.

That honour belongs to Louis François Antoine Arbogast who published it in his textbook of $1800$ Du Calcul des Dérivations.

Faà di Bruno himself published this result in Barnaba Tortolini's magazine Annali di Scienze Matematiche e Fisiche in $1855$, and again in The Quarterly Journal of Pure and Applied Mathematics in $1857$.