Prove the generalized Leibniz Rule by induction

**chopet** · October 9th 2007, 06:53 AM

where

is the usual binomial coefficient.

Leibniz rule (generalized product rule - Wikipedia, the free encyclopedia)

anyone? its not given at wikipedia.

**topsquark** · October 9th 2007, 07:14 AM

Originally Posted by chopet

where

is the usual binomial coefficient.

Leibniz rule (generalized product rule - Wikipedia, the free encyclopedia)

anyone? its not given at wikipedia.

I am considering both functions f and g to be functions of the single variable x.

Consider the case for n = 1:
$(fg)^{\prime} = \sum_{k = 0}^1 \left ( \begin{matrix} 1 \\ k \end{matrix} \right ) f^{(k)}g^{(1 - k)} = f^{\prime}g + fg^{\prime}$

So the theorem holds for n = 1.

Now assume it holds for some n = N, that is:
$(fg)^{(N)} = \sum_{k = 0}^N \left ( \begin{matrix} N \\ k \end{matrix} \right ) f^{(k)}g^{(N - k)}$

We wish to show it holds for n = N + 1 also.

So:
$\frac{d}{dx}(fg)^{(N)} = (fg)^{(N + 1)} = \frac{d}{dx} \left [ \sum_{k = 0}^N \left ( \begin{matrix} N \\ k \end{matrix} \right ) f^{(k)}g^{(N - k)} \right ]$

$= \sum_{k = 0}^N \left ( \begin{matrix} N \\ k \end{matrix} \right ) \left ( f^{(k + 1)}g^{(N - k)} + f^{(k)}g^{(N - k + 1)} \right )$

We need to show that this is equal to
$\sum_{k = 0}^{N + 1} \left ( \begin{matrix} N + 1 \\ k \end{matrix} \right ) f^{(k)}g^{((N + 1) - k)}$

There is going to be a way to do this in general, but you should probably start small. Let N = 1, for example. Then we are saying:
$\sum_{k = 0}^1 \left ( \begin{matrix} 1 \\ k \end{matrix} \right ) \left ( f^{(k + 1)}g^{(1 - k)} + f^{(k)}g^{(2 - k)} \right ) = \sum_{k = 0}^{2} \left ( \begin{matrix} 2 \\ k \end{matrix} \right ) f^{(k)}g^{(2 - k)}$

The advantage is that we can write this out term by term and see what is happening:
$f^{(2)}g + f^{(1)}g^{(1)} + f^{(1)}g^{(1)} + fg^{(2)} = f^{(2)}g + 2f^{(1)}g^{(1)} + fg^{(2)}$

See if you can you use this example and maybe the next few higher values of N to find a way to set up a conditional equation between the two summations.

I'll give you a hint: It's the same pattern as you see when you are proving that
$(a + b)(a + b)^n = a(a + b)^n + b(a + b)^n = \sum_{k = 0}^{N + 1} \left ( \begin{matrix} N + 1 \\ k \end{matrix} \right ) a^kb^{N + 1 - k}$

-Dan

**chopet** · October 9th 2007, 09:57 AM

Thanks for the hint.

I'm guessing there is a need to utilise the Binomial Theorem:

$ (a+b)^n = \sum_{k = 0}^{N} \left( \begin{matrix} N \\ k \end{matrix} \right ) a^kb^{N-k} $

1) I'm wondering how should I get
$\sum_{k=0}^{N+1}$ reduced to $\sum_{k=0}^{N}$ .

My only solution so far is to extract the upperbound term $N+1$ from the summation.

2) How to deal with the binomial coefficient? Should I use the identity

$\left( \begin{matrix} N \\ k \end{matrix} \right ) = \left(\begin{matrix} N-1 \\ k \end{matrix} \right )\left( \begin{matrix} N-1 \\ k-1 \end{matrix} \right )$

They don't lead anywhere as of now... but I'll keep trying.

**topsquark** · October 9th 2007, 10:12 AM

Originally Posted by chopet

Thanks for the hint.

I'm guessing there is a need to utilise the Binomial Theorem:

$ (a+b)^n = \sum_{k = 0}^{N} \left( \begin{matrix} N \\ k \end{matrix} \right ) a^kb^{N-k} $

And I'm wondering how should I get $\sum_{k=0}^{N+1}$ reduced to $\sum_{k=0}^{N}$ .

There are 2 ways as I am aware of:
1) Using the identity $\left( \begin{matrix} N \\ k \end{matrix} \right ) = \left(\begin{matrix} N-1 \\ k \end{matrix} \right )\left( \begin{matrix} N-1 \\ k-1 \end{matrix} \right )$

2) Extracting the upperbound term $N+1$ from the summation.

They don't lead anywhere as of now... but I'll keep trying.

Look at
$(a + b)^{3} = (a + b)(a + b)^2 = a(a + b)^2 + b(a + b)^2 = (a^3 + 2a^2b + ab^2) + (a^2b + 2ab^2 + b^3)$
Do you see where the different terms come together to form the new binomial coefficients?

-Dan

**chopet** · October 10th 2007, 11:09 AM

Ok, so far what I've figured out is to do it by brute force:

$a(a + b)^n + b(a + b)^n = a[ \left(\begin{matrix} n \\ 0 \end{matrix}\right ) a^nb^0 +...+ \left(\begin{matrix} n \\ n \end{matrix}\right ) a^0b^n] +$ $b[ \left(\begin{matrix} n \\ 0 \end{matrix}\right ) a^nb^0 +...+\left(\begin{matrix} n \\ n \end{matrix}\right) a^0b^n]$

$= \left(\begin{matrix} n \\ 0 \end{matrix}\right ) a^{n+1}b^0 + [\left(\begin{matrix} n \\ 1 \end{matrix}\right) + \left(\begin{matrix} n \\ 0 \end{matrix}\right)]a^nb^1 + ...+$ $[\left(\begin{matrix} n \\ n \end{matrix}\right)+\left(\begin{matrix} n \\ {n-1} \end{matrix}\right)]a^1b^n + \left(\begin{matrix} n \\ n \end{matrix}\right )a^0b^{n+1}$

Then, using the identity (which is easily proven):
$\left( \begin{matrix} N \\ k \end{matrix} \right ) = \left(\begin{matrix} N-1 \\ k \end{matrix} \right )\left( \begin{matrix} N-1 \\ k-1 \end{matrix} \right )$

the equation can be re-arranged into:
$= \left(\begin{matrix} {n+1} \\ 0 \end{matrix}\right ) a^{n+1}b^0 + \left(\begin{matrix} n+1 \\ 1 \end{matrix}\right) a^nb^1 + ...+$ $\left(\begin{matrix} {n+1} \\ n \end{matrix}\right)a^1b^n + \left(\begin{matrix} {n+1} \\ {n+1} \end{matrix}\right )a^0b^{n+1}$

which is actually the expanded form of
$\sum_{k = 0}^{N + 1} \left ( \begin{matrix} N + 1 \\ k \end{matrix} \right ) a^kb^{N + 1 - k}$

I hope there is a better way to do it though. This one doesn't seem elegant enough.

**topsquark** · October 11th 2007, 05:22 AM

Originally Posted by chopet

Ok, so far what I've figured out is to do it by brute force:

$a(a + b)^n + b(a + b)^n = a[ \left(\begin{matrix} n \\ 0 \end{matrix}\right ) a^nb^0 +...+ \left(\begin{matrix} n \\ n \end{matrix}\right ) a^0b^n] +$ $b[ \left(\begin{matrix} n \\ 0 \end{matrix}\right ) a^nb^0 +...+\left(\begin{matrix} n \\ n \end{matrix}\right) a^0b^n]$

$= \left(\begin{matrix} n \\ 0 \end{matrix}\right ) a^{n+1}b^0 + [\left(\begin{matrix} n \\ 1 \end{matrix}\right) + \left(\begin{matrix} n \\ 0 \end{matrix}\right)]a^nb^1 + ...+$ $[\left(\begin{matrix} n \\ n \end{matrix}\right)+\left(\begin{matrix} n \\ {n-1} \end{matrix}\right)]a^1b^n + \left(\begin{matrix} n \\ n \end{matrix}\right )a^0b^{n+1}$

Then, using the identity (which is easily proven):
$\left( \begin{matrix} N \\ k \end{matrix} \right ) = \left(\begin{matrix} N-1 \\ k \end{matrix} \right )\left( \begin{matrix} N-1 \\ k-1 \end{matrix} \right )$

the equation can be re-arranged into:
$= \left(\begin{matrix} {n+1} \\ 0 \end{matrix}\right ) a^{n+1}b^0 + \left(\begin{matrix} n+1 \\ 1 \end{matrix}\right) a^nb^1 + ...+$ $\left(\begin{matrix} {n+1} \\ n \end{matrix}\right)a^1b^n + \left(\begin{matrix} {n+1} \\ {n+1} \end{matrix}\right )a^0b^{n+1}$

which is actually the expanded form of
$\sum_{k = 0}^{N + 1} \left ( \begin{matrix} N + 1 \\ k \end{matrix} \right ) a^kb^{N + 1 - k}$

I hope there is a better way to do it though. This one doesn't seem elegant enough.

Elegance, schmelegance. The point is that it works. You can work on finesse later.

-Dan

Thread: Prove the generalized Leibniz Rule by induction

LinkBack

Thread Tools

Display

Prove the generalized Leibniz Rule by induction

Similar Math Help Forum Discussions

Leibniz rule

using Leibniz Rule

Leibniz' rule

Leibniz' rule

Example of Leibniz rule for integration

Search Tags