Binomial coefficiens: an identity

**NonCommAlg** · April 4th 2009, 10:12 AM

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

Source: ejcnt

**PaulRS** · April 13th 2009, 04:46 PM

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)= \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 $

A bit of Snake-Oil ( Exchange the summation order): $ 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)} $

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

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

Now we read off the coefficients of the OGF bearing in mind that $ \tfrac{x} {{\left( {1 - x} \right)^2 }} = \sum\limits_{n \geqslant 0} {n \cdot x^n } $ to obtain: $ A_n = \left( { - 1} \right)^n \cdot \left( {2n + 1} \right) $

**NonCommAlg** · April 13th 2009, 05:04 PM

Originally Posted by PaulRS

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)= \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 $

A bit of Snake-Oil ( Exchange the summation order): $ 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)} $

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

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

Now we read off the coefficients of the OGF bearing in mind that $ \tfrac{x} {{\left( {1 - x} \right)^2 }} = \sum\limits_{n \geqslant 0} {n \cdot x^n } $ to obtain: $ A_n = \left( { - 1} \right)^n \cdot \left( {2n + 1} \right) $

Bravo!

Thread: Binomial coefficiens: an identity

LinkBack

Thread Tools

Display

Binomial coefficiens: an identity

Similar Math Help Forum Discussions

[SOLVED] An identity of equivalent products related to the binomial theorem

Proving a binomial identity

A binomial identity

Combinatorial proof of a binomial identity

Identity using binomial theorem

Search Tags