# Nifty identity with a really cool proof

• Jan 4th 2011, 01:45 PM
Chris11
Nifty identity with a really cool proof
Hey, I came across this in a textbook on algebra. It was in the appendix on induction, that I thought that I would just gloss over. Do not, however, use induction, as there is a much more elegant way!(This really just illistrates how great a certain proof of a certain famous theorem is)

Let f, g be n-differenciable functions on the reals. Let (n, r) denote the binomial coefficent. n is a positive integer. $f^i$ denote the ith derivitive of f.

Prove that $\displaystyle \sum_{i=0}^{i=n}(n,i)f^ig^{n-i}=(fg)^{n}$
• Jan 4th 2011, 01:53 PM
snowtea
Does the proof use Pascal's triangle (which I guess would be induction)?
Or a combinatorial interpretation of $f$ and $g$ as generating functions?
• Jan 4th 2011, 02:01 PM
Chris11
I don't know about generating functions, but it's a combinatorical proof.
• Jan 7th 2011, 05:38 PM
snowtea
I would love to know the more elegant solution, so I'll put something that I think is quite simple.

f0g0
f1g0 f0g1
f2g0 f1g1 f0g2
f3g0 f2g1 f1g2 f0g3
...

Let the entry f<i>g<j> represent the term $f^i g^j$.
In the diagram above, the derivative of each term is the sum of the one below it and the sum of the one below and to the right.
So create a graph, where each term has an edge to the term below, and an edge from a term to the one below and to the right.

In the final sum, the number of times a term $f^ig^j$ is added is the number of downward paths from f0g0 to that node.
This is of course $\binom{i+j}{i} = \binom{n}{i}$.
• Jan 7th 2011, 06:49 PM
Chris11
Notice that each 'coefficentless' term in the expansion will be of the form $f^ig^n-i$ Now, we have to diffrenciate the product n times. Each time, we can choose to differenciate an f or a g (of course there are the other terms, but they'll appear in a second) ie. say we diffrenciate fg. we can differenciate f or g to produce the terms f'g and g'f. Now, we have n choices that effect each term in the expansion, and we have slots 1234...n (representing the order of differenciation) upon which me must choose i of these slots to obtain an $f^i$, and the choices for g are forced. Hence, after collecting all of the f^i terms, we will have a coefficent that is equal to (n, i). This is essencially the same as the combinatorical proof of the binomial theorem, which you should definitly check out if you haven't seen it yet.

• Jan 7th 2011, 10:08 PM
TheCoffeeMachine
Quote:

Originally Posted by Chris11
Nifty identity with a really cool proof

This is called the General Leibniz Rule. It's just a generalization of the product rule. I'm surprised you didn't come across it before! :p
• Jan 7th 2011, 10:18 PM
Chris11
lol, I guess that I should be embarrased by my ignorance! (Speechless)
• Jan 7th 2011, 10:33 PM
TheCoffeeMachine
Quote:

Originally Posted by Chris11
lol, I guess that I should be embarrased by my ignorance! (Speechless)

Haha, don't be! Besides, I personally like it very much. I learnt it from an old book, and now in school, when
we are asked to find Taylor series for certain functions at some point, most students start finding derivative
after derivative to discern a pattern whereas I just differentiate it n-times using the this 'nifty identity' and
evaluate at the given point, then tada - there's it's... I've used it in here and here in this forum alone! :P