Results 1 to 3 of 3

Math Help - Binomial coefficiens: an identity

  1. #1
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7

    Binomial coefficiens: an identity

    Evaluate A_n=\sum_{j=0}^n \binom{n+j}{n-j}(-4)^j, \ \ n \in \mathbb{N}.

    Source: ejcnt
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    First, we may write: \sum\limits_{j = 0}^n {\binom{n+j}{n-j}\left( { - 4} \right)^j }=\sum\limits_{j \geq 0} {\binom{n+j}{n-j}\left( { - 4} \right)^j }=\sum\limits_{j \geq 0} {\binom{n+j}{2j}\left( { - 4} \right)^j}

    The first equality comes from the fact that \binom{m}{s}=0 when m\in {\mathbb{N}} and s\in\mathbb{Z}^- and the second because: \binom{n+j}{n-j}=\binom{n+j}{2j} (they count complementary combinations)

    Now consider the Ordinary Generating Function : A(x)=<br />
\sum\limits_{n \geqslant 0} {A_n  \cdot x^n }  = \sum\limits_{n \geq 0}\left( \sum\limits_{j \geq{0}}\binom{n+j}{2j} {\left( { - 4} \right)^j }\right)  \cdot x^n <br />

    A bit of Snake-Oil ( Exchange the summation order): <br />
A\left( x \right) = \sum\limits_{j \geqslant 0} {\left( { - 4} \right)^j  \cdot \left( {\sum\limits_{n \geqslant 0} {\binom{n+j}{2j}\cdot x^n } } \right)} = \sum\limits_{j \geqslant 0} {\left( { - \tfrac{4}{x}} \right)^j \cdot \left( {\sum\limits_{n \geqslant 0} {\binom{n+j}{2j}\cdot x^{n+j} } } \right)}<br />

    The inner series is: {\sum\limits_{n \geqslant 0} {\binom{n}{2j}\cdot x^{n} } } =\tfrac{{x^{2j} }}<br />
{{\left( {1 - x} \right)^{2j + 1} }}<br />
( This can be obtained differentiating repeatedly <br />
\tfrac{1}<br />
{{1 - x}} = \sum\limits_{n \geqslant 0} {x^n } <br />
)

    So: <br />
A\left( x \right) = \tfrac{1}<br />
{{1 - x}} \cdot \sum\limits_{j \geqslant 0} {\left( { - \tfrac{{4x}}<br />
{{\left( {1 - x} \right)^2 }}} \right)^j }  = \tfrac{1}<br />
{{1 - x}} \cdot \tfrac{1}<br />
{{1 + \tfrac{{4x}}<br />
{{\left( {1 - x} \right)^2 }}}} = \tfrac{{1 - x}}<br />
{{\left( {1 + x} \right)^2 }}<br />

    Now we read off the coefficients of the OGF bearing in mind that <br />
\tfrac{x}<br />
{{\left( {1 - x} \right)^2 }} = \sum\limits_{n \geqslant 0} {n \cdot x^n } <br />
to obtain: <br />
A_n  = \left( { - 1} \right)^n  \cdot \left( {2n + 1} \right)<br />
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by PaulRS View Post
    First, we may write: \sum\limits_{j = 0}^n {\binom{n+j}{n-j}\left( { - 4} \right)^j }=\sum\limits_{j \geq 0} {\binom{n+j}{n-j}\left( { - 4} \right)^j }=\sum\limits_{j \geq 0} {\binom{n+j}{2j}\left( { - 4} \right)^j}

    The first equality comes from the fact that \binom{m}{s}=0 when m\in {\mathbb{N}} and s\in\mathbb{Z}^- and the second because: \binom{n+j}{n-j}=\binom{n+j}{2j} (they count complementary combinations)

    Now consider the Ordinary Generating Function : A(x)=<br />
\sum\limits_{n \geqslant 0} {A_n \cdot x^n } = \sum\limits_{n \geq 0}\left( \sum\limits_{j \geq{0}}\binom{n+j}{2j} {\left( { - 4} \right)^j }\right) \cdot x^n <br />

    A bit of Snake-Oil ( Exchange the summation order): <br />
A\left( x \right) = \sum\limits_{j \geqslant 0} {\left( { - 4} \right)^j \cdot \left( {\sum\limits_{n \geqslant 0} {\binom{n+j}{2j}\cdot x^n } } \right)} = \sum\limits_{j \geqslant 0} {\left( { - \tfrac{4}{x}} \right)^j \cdot \left( {\sum\limits_{n \geqslant 0} {\binom{n+j}{2j}\cdot x^{n+j} } } \right)}<br />

    The inner series is: {\sum\limits_{n \geqslant 0} {\binom{n}{2j}\cdot x^{n} } } =\tfrac{{x^{2j} }}<br />
{{\left( {1 - x} \right)^{2j + 1} }}<br />
( This can be obtained differentiating repeatedly <br />
\tfrac{1}<br />
{{1 - x}} = \sum\limits_{n \geqslant 0} {x^n } <br />
)

    So: <br />
A\left( x \right) = \tfrac{1}<br />
{{1 - x}} \cdot \sum\limits_{j \geqslant 0} {\left( { - \tfrac{{4x}}<br />
{{\left( {1 - x} \right)^2 }}} \right)^j } = \tfrac{1}<br />
{{1 - x}} \cdot \tfrac{1}<br />
{{1 + \tfrac{{4x}}<br />
{{\left( {1 - x} \right)^2 }}}} = \tfrac{{1 - x}}<br />
{{\left( {1 + x} \right)^2 }}<br />

    Now we read off the coefficients of the OGF bearing in mind that <br />
\tfrac{x}<br />
{{\left( {1 - x} \right)^2 }} = \sum\limits_{n \geqslant 0} {n \cdot x^n } <br />
to obtain: <br />
A_n = \left( { - 1} \right)^n \cdot \left( {2n + 1} \right)<br />
    Bravo!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] An identity of equivalent products related to the binomial theorem
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: September 20th 2010, 12:53 AM
  2. Proving a binomial identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2009, 04:56 PM
  3. A binomial identity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2008, 03:19 AM
  4. Combinatorial proof of a binomial identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 12th 2008, 03:42 PM
  5. Identity using binomial theorem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 2nd 2008, 10:41 AM

Search Tags


/mathhelpforum @mathhelpforum