nth derivative of a finite amount of composite functions

I was curious to see whether or not there is a formula for the $n$th derivative of $k$ composite functions. If $F(x)=(f_1\circ f_2\circ...\circ f_k(x))$ then is there a formula for

$$\frac{d^n} {dx^n}(F(x)).$$

For the $n$th derivative of two composite functions we use Faa di Bruno's rule, or

$$\frac{d^n} {dx^n}(f(g(x)) =\sum \frac {n!} {m_1! 1!^{m_1} ... m_n! n!^{m_n}} \cdot f^{(m_1 + ... + m_n)} (g(x)) \prod_{i=1}^{n}(g^{(i)}(x))^{m_i}, $$

where the sum is over all the values of $m_1,...,m_n$ such that $m_1+2m_2+...+nm_n=n$.

Also, for the first derivative of $k$ composite functions, user Yangzhe Lau gave me the formula

$$F'(x)=\prod_{i=1}^{k}f'_i(f_{i+1}\circ f_{i+2} \circ \cdot \cdot\cdot\circ f_k(x)).$$

Therefore, is there a formula for that essentially combines these two, I suppose.

Solution 1:

For the following it is easier to begin with functions which have no constant term, so say $$ \begin{eqnarray} f_1(x) &=&a_1 x + b_1 x^2 + c_1 x^3 + ... \\ f_2(x) &=&a_2 x + b_2 x^2 + c_2 x^3 + ... \\ ... \\ f_n(x) &= &a_n x + b_n x^2 + c_n x^3 + ... \\ \end{eqnarray} $$ This allows to use the concept of "Carleman"- or "Bell"-matrices for the composition of functions.
We define a Carlemanmatrix for the above functions, for instance $F_k$ for $f_k(x)$ such that the columns contain the coefficients of the consecutive powers of$f_k$ beginning with that of $f_k(x)^0, f_k(x),f_k(x)^2,...$ where it is obvious that we deal with infinite sized matrices! But the matrices come out to be triangular so we can later operate with them. For instance , $F_1$ looks like $$ F_1 = \small \begin{bmatrix} 1 & . & . & . & . & \cdots \\ 0 & a_1 & . & . & . & \cdots \\ 0 & b_1 & a_1^2 & . & . & \cdots \\ 0 & c_1 & 2 a_1 b_1 & a_1^3 & . & \cdots \\ 0 & d_1 & b_1^2+2 c_1 a_1 & 3 a_1^2 b_1 & a_1^4& \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix} $$ We see in the columns the coefficients of the powers of the formal power series of $f_1$.
Now with a "Vandermonde"-vector $V(x)=[1,x,x^2,x^3,...]$ the dotproduct $V(x) \cdot F_1 $ gives the evaluation of the function $f_1(x)$ and all of its (nonnegative) powers: $$ V(x) \cdot F_1 = [1,f(x),f(x)^2,f(x)^3,...] = V(f(x)) $$ The clue is here, that the result is again of the "Vandermonde"-type and that we can thus proceed with the next function and so on ...

Then the composition of the functions $g(x) = f_3 \circ f_2 \circ f_1 (x)$ has simply the Carlemanmatrix $G$ which is $$ G = F_1 \cdot F_2 \cdot F_3 $$

To exercise with this it is -in the software Pari/GP- easy to define appropriate vector- and even matrix-functions for some finite size $n$:

f1(x)= 'a1*x + 'b1*x^2+'c1*x^3+'d1*x^4+ O(x^5)      \\ actually you would  
f2(x)= 'a2*x + 'b2*x^2+'c2*x^3+'d2*x^4+ O(x^5)      \\ give some concrete values  
f3(x)= 'a3*x + 'b3*x^2+'c3*x^3+'d3*x^4+ O(x^5)      \\ for the symbols 'a,'b,...  
V(x,n)=vector(n,r,x^(r-1))     
Carleman(x,n)=matrix(n,n,r,c,...)          

where the latter function can accept a function written as truncated powerseries and then

F1 = Carleman(f1(x))
F2 = Carleman(f2(x))
F3 = Carleman(f3(x))
G = F1 * F2 * F3 
print(Ser(G[,2]))  \\ shows the notation of the power series of g(x)

and approximate results can be computed if the series converge well and the size of the matrices and vectors are sufficient just by

   x = 0.5   \\ give some initial value which gives reasonable approximation
   y1 = V(x )*F1[,2])     \\ shows evaluation of f1 at some value x       
   y2 = V(y1)*F2[,2])    \\ shows evaluation of f2 at the value y1=f1(x)       
   y3 = V(y2)*F3[,2])    \\ shows evaluation of f3 at the value y2=f2(f1(x))       
   g = V(x) * G[,2]    \\ g and y3 should be identical

(If you want to keep things symbolic then reduce the matrix-size to 4 or 5 - the composition creates huge stuff of terms!)

It is hopeless to try to write out the resulting coefficients for an indeterminate number of functions $f_k(x)$, but for the composition of, say 3 functions, the top left part of $G = F_1 \cdot F_2 \cdot F_3$ looks like $$ \Tiny \begin{array} {} 1 & . & . & . \\ 0 & a_3 a_2 a_1 & . & . \\ 0 & a_3 a_2 b_1+a_3 a_1^2 b_2+a_2^2 a_1^2 b_3 & a_3^2 a_2^2 a_1^2 & . \\ 0 & (2 a_3 a_1 b_2+2 a_2^2 a_1 b_3) b_1+2 a_2 a_1^3 b_3 b_2+(c_3 a_2^3+c_2 a_3) a_1^3+c_1 a_3 a_2 & 2 a_3^2 a_2^2 a_1 b_1+2 a_3^2 a_2 a_1^3 b_2+2 a_3 a_2^3 a_1^3 b_3 & a_3^3 a_2^3 a_1^3 \end{array} $$ The n'th derivatives of $g(x)$ are now in the second column, for instance $ \displaystyle \qquad g'(x) = a_3 a_2 a_1 \\ \qquad g''(x)/2! = a_3 a_2 b_1+a_3 a_1^2 b_2+a_2^2 a_1^2 b_3 \\ \qquad g'''(x)/3! = (2 a_3 a_1 b_2+2 a_2^2 a_1 b_3) b_1+2 a_2 a_1^3 b_3 b_2+(c_3 a_2^3+c_2 a_3) a_1^3+c_1 a_3 a_2 \\ $