I am writing a proof of Calculus which uses Faa di Bruno's formula to show that the composition of two analytic functions is analytic.
I tried to prove the result with induction. The base case was easy, but I got stuck in the inductive step. This is my work for the inductive step:
Define $h(x)=f(g(x))$.
Then
$$\begin{align} h^{(n+1)}(x)&=\left(h^{(n)}(x)\right)'\\\\ &=\left(\sum\limits_{1k_1+2k_2+\cdots+nk_n=n}\frac{n!}{k_1!\cdots k_n!}f^{(k_1+\cdots+k_n)}(g(x))\prod\limits_{j=1}^n\left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)'\\\\ &=\sum\limits_{1k_1+2k_2+\cdots+nk_n=n}\frac{n!}{k_1!\cdots k_n!}\left(f^{(k_1+\cdots+k_n)}(g(x))\prod\limits_{j=1}^n\left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)'\\\\ &=\sum\limits_{1k_1+2k_2+\cdots+nk_n=n}\frac{n!}{k_1!\cdots k_n!}\left[\left(f^{(k_1+\cdots+k_n)}(g(x))\right)'\left(\prod\limits_{j=1}^n\left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)\right.\\ &\left.\qquad\qquad+\left(\prod\limits_{j=1}^n\left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)'\left(f^{(k_1+\cdots+k_n)}(g(x))\right)\right]\\\\ &=\sum\limits_{1k_1+2k_2+\cdots+nk_n=n}\frac{n!}{k_1!\cdots k_n!}\left[\left(f^{(k_1+\cdots+k_n+1)}(g(x))g'(x)\right)\left(\prod\limits_{j=1}^n\left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)\right.\\\\ &\left.\qquad\qquad+\left(\sum\limits_{k=1}^{n} \left(\left(\frac{g^{(k)}(x)}{k!}\right)^{k_k}\right)'\prod\limits_{\substack{j=1\\j\ne k}}^{n} \left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)\left(f^{(k_1+\cdots+k_n)}(g(x))\right)\right]\\\\ &=\sum\limits_{1k_1+2k_2+\cdots+nk_n=n}\frac{n!}{k_1!\cdots k_n!}\left[\left(f^{(k_1+\cdots+k_n+1)}(g(x))g'(x)\right)\left(\prod\limits_{j=1}^n\left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)\right.\\\\ &\left.\qquad\qquad+\left(\sum\limits_{k=1}^{n} k_k\left(\left(\frac{g^{(k)}(x)}{k!}\right)^{k_k-1}\left(\frac{g^{(k+1)}(x)}{k!}\right)\right)\prod\limits_{\substack{j=1\\j\ne k}}^{n} \left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)\left(f^{(k_1+\cdots+k_n)}(g(x))\right)\right]\\ &=\sum\limits_{1k_1+2k_2+\cdots+nk_n=n}\frac{n!}{k_1!\cdots k_n!}\left[\left(f^{(k_1+\cdots+k_n+1)}(g(x))g'(x)\right)\left(\prod\limits_{j=1}^n\left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)\right.\\ &\left.\qquad\qquad+\left(\sum\limits_{k=1}^{n} k_k\left(\frac{g^{(k)}(x)}{k!}\right)^{k_k-1}\left(\frac{g^{(k+1)}(x)}{k!}\right)\prod\limits_{\substack{j=1\\j\ne k}}^{n} \left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}\right)\left(f^{(k_1+\cdots+k_n)}(g(x))\right)\right]\\ \end{align}$$
I eventually want to simplify this expression to $$\sum\limits_{1k_1+2k_2+\cdots+nk_n+(n+1)k_{n+1}=n+1}\frac{(n+1)!}{k_1!\cdots k_n!k_{n+1}!}f^{(k_1+\cdots+k_n+k_{n+1})}(g(x))\prod\limits_{j=1}^{n+1}\left(\frac{g^{(j)}(x)}{j!}\right)^{k_j}$$
I noticed that the first term of the right hand side of my last step is equivalent to that simplified sum under the restriction that $k_1\ge 1$ except it is missing a factor of $n+1$. The $nth$ term of the sum from $j=1$ to $n$ on the right hand side exactly matches the term on the simplified version where $k_{n+1}=1$ and the other $k_j's$ are $0$. The remaining terms of the sum (i.e. the terms for $j=1$ to $j=n-1$) correspond to a relative increase in $k_{j+1}$ by $1$ and relative decrease in $k_j$ by $1$, with the exception of a missing factor of $\frac{n+1}{(k+1)k_k}$. I am not sure how to address these missing factors and particuticularly how to rewrite the terms from $j=1$ to $n-1$ of the sum of the right hand side.
I tested my work for $n=2$ and the two expressions were equivalent. This makes me think my work is correct so far I just don't know how to proceed.
Thanks, Andrew Murdza