# Thread: Prove the generalized Leibniz Rule by induction

1. ## Prove the generalized Leibniz Rule by induction

2. Originally Posted by chopet
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

3. 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.

4. 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

5. 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.

6. 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