Results 1 to 6 of 6

Math Help - Prove the generalized Leibniz Rule by induction

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    145

    Prove the generalized Leibniz Rule by induction

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by chopet View Post
    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 ) = <br />
\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
    Last edited by topsquark; October 9th 2007 at 08:30 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2007
    Posts
    145
    Thanks for the hint.

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

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

    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.
    Last edited by chopet; October 9th 2007 at 11:10 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by chopet View Post
    Thanks for the hint.

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

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

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2007
    Posts
    145
    Ok, so far what I've figured out is to do it by brute force:

    a(a + b)^n + b(a + b)^n = <br />
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.
    Last edited by chopet; October 10th 2007 at 12:39 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by chopet View Post
    Ok, so far what I've figured out is to do it by brute force:

    a(a + b)^n + b(a + b)^n = <br />
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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Leibniz rule
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 8th 2011, 05:07 AM
  2. using Leibniz Rule
    Posted in the Calculus Forum
    Replies: 6
    Last Post: January 4th 2011, 10:39 PM
  3. Leibniz' rule
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 5th 2009, 07:47 AM
  4. Leibniz' rule
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 4th 2009, 04:58 AM
  5. Example of Leibniz rule for integration
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 6th 2008, 09:53 AM

Search Tags


/mathhelpforum @mathhelpforum