There's a formula for the $n$th derivative of a composite function $f(g(x))$ - it's called Faa di Bruno's formula - but I'm not really interested in the formula but in the proof given in the book of Flajolet and Sedgewick (2009). On their page 188, III.24, they say (if I understand correctly) that for proving this theorem it suffices to consider formal power series compositions (i.e. when $f$ and $g$ are formal power series $f(x)=\sum_{k\ge 0} f_kx^k$ and $g(x)=\sum_{k\ge 0}g_kx^k$). Since they say this is "clearly equivalent", the argumentation must be really simple but I don't see it right now. Does anyone have an idea? (Not all real functions admit power series representations, not even ones that are infinitely differentiable, right?)

  • 1
    $\begingroup$ Nice question. I cannot think of a formal way to justify that, but a reasonable formula obtained in this way would clearly be true :) I think an important observation is the fact that there obviously is a formula, so we only need to find it. (Afterwards, the truly formal proof should probably use induction.) Another formal way is to use Taylor polynomials instead of the power series and observe that the terms of order higher than guaranteed are not used. $\endgroup$ Mar 18, 2014 at 10:43
  • $\begingroup$ I'd like to know if/how the Borel-Ritt theorem can be applied in this context, also. $\endgroup$ Mar 18, 2014 at 10:57
  • $\begingroup$ A more formal way to express Alex Degtyarev comment: work in quotient ring of the formal power series modulo the ideal generated by the $n+1$ power of the indeterminate (the annihilated ideal corresponds to the Landau notation, small "o" of order $n$ or big "O" of order $n+1$). $\endgroup$
    – user46855
    Mar 18, 2014 at 13:30
  • $\begingroup$ The formal way to justify the argument mentioned by Alex is to consider $f$ and $g$ as members of suitable algebras of smooth functions with the topology of uniform convergence (together with all derivatives) on compacta. One then uses a density result (denseness of the polynomials) and the fact that the mapping $(f,g)\mapsto f \circ g$ is continuous. However, the latter is a bit messy to prove and I think that the argument of Alex is the most sensible: work with analytical functions (even polynomials) to discover the formula, then prove it by induction. $\endgroup$
    – barcelos
    Mar 18, 2014 at 14:30
  • 1
    $\begingroup$ This question is put on hold although Deane Yang, who did this, has answers to issues like "Why do we teach calculus students the derivative as a limit?" - how's the latter research, actually? $\endgroup$
    – mathse
    Mar 19, 2014 at 7:37


Browse other questions tagged or ask your own question.