# Binomial coefficiens: an identity

• Apr 4th 2009, 10:12 AM
NonCommAlg
Binomial coefficiens: an identity
Evaluate $\displaystyle A_n=\sum_{j=0}^n \binom{n+j}{n-j}(-4)^j, \ \ n \in \mathbb{N}.$

Source: ejcnt
• Apr 13th 2009, 04:46 PM
PaulRS
First, we may write: $\displaystyle \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 $\displaystyle \binom{m}{s}=0$ when $\displaystyle m\in {\mathbb{N}}$ and $\displaystyle s\in\mathbb{Z}^-$ and the second because: $\displaystyle \binom{n+j}{n-j}=\binom{n+j}{2j}$ (they count complementary combinations)

Now consider the Ordinary Generating Function :$\displaystyle 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): $\displaystyle 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: $\displaystyle {\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 $\displaystyle \tfrac{1} {{1 - x}} = \sum\limits_{n \geqslant 0} {x^n }$ )

So: $\displaystyle 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 $\displaystyle \tfrac{x} {{\left( {1 - x} \right)^2 }} = \sum\limits_{n \geqslant 0} {n \cdot x^n }$ to obtain: $\displaystyle A_n = \left( { - 1} \right)^n \cdot \left( {2n + 1} \right)$
• Apr 13th 2009, 05:04 PM
NonCommAlg
Quote:

Originally Posted by PaulRS
First, we may write: $\displaystyle \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 $\displaystyle \binom{m}{s}=0$ when $\displaystyle m\in {\mathbb{N}}$ and $\displaystyle s\in\mathbb{Z}^-$ and the second because: $\displaystyle \binom{n+j}{n-j}=\binom{n+j}{2j}$ (they count complementary combinations)

Now consider the Ordinary Generating Function :$\displaystyle 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): $\displaystyle 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: $\displaystyle {\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 $\displaystyle \tfrac{1} {{1 - x}} = \sum\limits_{n \geqslant 0} {x^n }$ )

So: $\displaystyle 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 $\displaystyle \tfrac{x} {{\left( {1 - x} \right)^2 }} = \sum\limits_{n \geqslant 0} {n \cdot x^n }$ to obtain: $\displaystyle A_n = \left( { - 1} \right)^n \cdot \left( {2n + 1} \right)$

Bravo!