# Binomial coefficiens: an identity

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

Source: ejcnt
• Apr 13th 2009, 05:46 PM
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)
$
• Apr 13th 2009, 06:04 PM
NonCommAlg
Quote:

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!