Let f and g have derivatives of every order. Prove that the n-th derivative of F = fg satisfies F^(n) = sum over j from 0 to n of C(n,j) f^(n-j) g^(j).

Step-by-step solution

1. 1

   Set up the induction. The claim is a statement about every natural number $n$, so prove it for $n=1$ and then show that the truth at $n$ forces the truth at $n+1$. The structural resemblance to the binomial theorem is the clue that Pascal's rule will do the work.

2. 2

   Base case n = 1. The right-hand side reads

   $\binom10 f'g+\binom11 fg'=f'g+fg'$

   which is exactly the ordinary product rule, so the formula holds for $n=1$.

3. 3

   Assume the formula at n and differentiate once more. Applying the product rule to each term of the inductive hypothesis:

   $F^{(n+1)}=\sum_{j=0}^{n}\binom{n}{j}\left[f^{(n-j+1)}g^{(j)}+f^{(n-j)}g^{(j+1)}\right]$

   This splits into two sums, one where $f$ picked up the extra derivative and one where $g$ did.

4. 4

   Re-index the second sum so the two align. Substituting $k=j+1$ in the second sum turns it into $\sum_{k=1}^{n+1}\binom{n}{k-1}f^{(n+1-k)}g^{(k)}$. Renaming $k$ back to $j$, the two sums now carry the same factor $f^{(n+1-j)}g^{(j)}$:

   $F^{(n+1)}=\sum_{j=0}^{n}\binom{n}{j}f^{(n+1-j)}g^{(j)}+\sum_{j=1}^{n+1}\binom{n}{j-1}f^{(n+1-j)}g^{(j)}$

5. 5

   Combine using Pascal's rule. For $1\le j\le n$ the coefficient of $f^{(n+1-j)}g^{(j)}$ is

   $\binom{n}{j}+\binom{n}{j-1}=\binom{n+1}{j}$

   The end terms match too: at $j=0$ the coefficient is $\binom{n}{0}=1=\binom{n+1}{0}$, and at $j=n+1$ it is $\binom{n}{n}=1=\binom{n+1}{n+1}$.

6. 6

   Conclude the induction.

   $F^{(n+1)}=\sum_{j=0}^{n+1}\binom{n+1}{j}f^{(n+1-j)}g^{(j)}$

   which is the formula with $n$ replaced by $n+1$. By induction it holds for every natural number $n$.

   $\boxed{F^{(n)}=\sum_{j=0}^{n}\binom{n}{j}f^{(n-j)}g^{(j)}}$

7. 7

   Check the case n = 2 explicitly. The formula predicts $F''=f''g+2f'g'+fg''$. Differentiating $F'=f'g+fg'$ by hand gives $f''g+f'g'+f'g'+fg''=f''g+2f'g'+fg''$ ✓ — the coefficients $1,2,1$ are the second row of Pascal's triangle, exactly as the binomial analogy suggests.