7

I went through induction proofs and they are nice. I'm just looking for an alternative.

To give some context, kindly consider the following example. To expand $(x+a)^n$ we think of it as a combinatorics problem : $$(x+a)(x+a)\cdots (x+a)$$ To get $x$ term we need to choose $x$ from any one product and $a$ from the rest. Thus the $x$ term would be $\binom{n}{1}xa^{n-1}$
To get the $x^2$ term we need to choose $x$ from any two products and $a$ from the rest: $\binom{n}{2}x^2a^{n-2}$

I'm wondering if the product rule can be seen using combinatorics $$\begin{align} (fg)^{'} &=f'g+fg'\\ (fg)^{''}&=(f'g+fg')^{'} = f''g+2f'g'+fg'' \end{align}$$ This looks almost same as the earlier problem of expanding $(x+a)^n$. I'm pretty sure these two problems are identical, but I'm not able to make the connection. Any help ?

RayDansh
  • 1,073
AgentS
  • 12,195
  • Did you see egreg's approach here? – Cameron Buie Jul 17 '18 at 23:24
  • Yes @CameronBuie I'm familiar with that proof and I like induction a lot. I'm trying to interpret the product rule using arguments like choose two first derivatives, choose three second derivatives, etc.. – AgentS Jul 17 '18 at 23:30
  • I mean only after I wrote $(x+a)^n$ flat $$(x+a)(x+a)\cdots (x+a)$$

    it became clear what I had to choose and leave to get the coefficient of $x^k$. I'm wondering if we can flatten something similar in product rule.. @CameronBuie

     – AgentS Jul 17 '18 at 23:36
  • The required connection is done in the Species Theory. For every two species $F$ and $G$, $[F.G]' = F'G + G'F$. Here is the derivative of a product https://math.stackexchange.com/questions/2852683/how-many-subsets-of-size-k-from-1-2-n-such-that-if-subset-contains-2-it-doe/2853273#2853273 – Boyku Jul 20 '18 at 18:39

3 Answers3

5

A "counting argument" could be as follows. Let $\mu$ be the multiplication operator and let $D$ be the derivative operator. Then the usual product rule says that we have the following identity.

$$D\mu = \mu(D\times 1+1\times D)$$

This means, by induction, that $$D^n\mu = \mu(D\times 1+1\times D)^n$$

Now expand the right hand side using the binomial theorem! This is why both proofs are the same.

Induction, of course. Suppose that it is true that

$$D^n(f\cdot g) = \sum_{i=0}^n \binom ni D^if\cdot D^{n-i} g$$

Applying $D$ you get

$$D^{n+1}(f\cdot g) = \sum_{i=0}^n \binom ni D(D^if\cdot D^{n-i} g)$$

Apply the base case to this to get

$$D^{n+1}(f\cdot g) = \sum_{i=0}^n \binom ni D^{i+1}f\cdot D^{n-i} g+D^if\cdot D^{n-i+1} g.$$

Now use Pascal's rule to obtain the induction step. Note the proof is the same as for the binomial.

Pedro
  • 122,002
  • 3
    Though, OP did mention that he was looking to an alternative to induction. – Argon Jul 17 '18 at 23:17
  • Yeah I went through many induction proofs in another post yesterday, but this form using operators is really slick. Thank you :) I'm still wondering if we can approach the problem directly with out referring to induction explicitly. Like using arguments like choosing terms etc.. Hmm – AgentS Jul 17 '18 at 23:21
3

Define three operators: $D_\times$ represents differentiation of a product; $D_1$ represents differentiation of the first term of the product; and $D_2$ represents differentiation of the second term. Then the simple product rule $(fg)' = f'g + fg'$ can be written $D_\times = D_1 + D_2$. Observe that $D_1$ and $D_2$ are commutative, so you can apply the binomial theorem to $(D_1 + D_2)^n$.

Peter Taylor
  • 13,425
2

With (as usual) $f^{(n)}$ denoting the $n$th derivative of $f$ when $n>0,$ and $f^{(0)}=f.$

There are $n$ steps ($n$ differentiations ) to get from $(fg)^{(0)}$ to $(fg)^{(n)}.$

After the $m$th step ($m\geq 0$) we have the sum of a finite sequence of (not necessarily unequal) terms, each of the form $f^{(j)}g^{(m-j)}$ for some $0\leq j\leq m.$ The $(m+1)$th step replaces each such term with the 2 terms $f^{(j+1)}g^{(m-j)}$ and $f^{(j)}g^{(m+1-j)}.$

After $n$ steps a term $f^{(j)}g^{(n-j)}$ will appear $\binom {n}{j}$ times because there are $\binom {n}{j}$ different "paths" through the $n$ steps that will result in such a term.

DanielWainfleet
  • 57,985