# Sums

• May 3rd 2008, 08:44 AM
james_bond
Sums
Prove that $\sum_{k=0}^m \binom mk \binom{t+k}{m} =\sum_{k=0}^m\binom mk\binom tk\cdot2^k$.
• May 3rd 2008, 09:35 AM
Isomorphism
Quote:

Originally Posted by james_bond
Prove that $\sum_{k=0}^m \binom mk \binom{t+k}{m} =\sum_{k=0}^m\binom mk\binom tk\cdot2^k$.

I could not prove this, but I have some lead:

Strangely I get $\sum_{k=0}^m \binom mk \binom{t+k}{m} = \binom {2t}{m}$

I first observed that $\binom mk \binom{t+k}{m} = \binom tk \binom{t}{m-k}$

But $\sum_{k=0}^m \binom tk \binom{t}{m-k}$ is the coefficient of $x^m$ in $(1+x)^t \cdot (1+x)^t$

Viewed differently: The coefficient of $x^m$ in $(1+x)^{2t}$ i $s \binom {2t}m$!!

To get that elusive $2^k$, I tried the following(in vain)
$(1+x)^{2t} = (1+x^2 + 2x)^t = \sum_{k=0}^m \binom tk (x^2 + 2x)^k = \sum_{k=0}^m \binom tk x^k (x + 2)^k$

But what goes on from here is pretty ugly (Crying)
• May 3rd 2008, 01:13 PM
PaulRS
Let's find the generating functions

$
\sum_{t = 0}^{\infty} {\sum_{k = 0}^m {\binom{m}{k}\cdot{\binom{t+k}{m}} x^t} } = \sum_{k = 0}^{m} {\sum_{t = 0}^{\infty} {\binom{m}{k}\cdot{\binom{t+k}{m}} x^t} }

$

Note that: $
\sum_{t = 0}^{\infty} {\binom{t+k}{m}\cdot{x^t} } = \sum_{t = m - k}^{\infty} {\binom{t+k}{m}x^t }
= x^{m - k} \cdot \sum_{j = 0}^{\infty} {\binom{j+m}{m}x^j } = \frac{{x^{m - k} }}
{{\left( {1 - x} \right)^{m + 1} }}
$

Thus: $\sum_{k = 0}^{m} {\sum_{t = 0}^{\infty} {\binom{m}{k}\cdot{\binom{t+k}{m}} x^t} }=
\sum\limits_{k = 0}^m {\binom{m}{k} \cdot \tfrac{{x^{m - k} }}
{{\left( {1 - x} \right)^{m + 1} }}} = \tfrac{{x^m }}
{{\left( {1 - x} \right)^{m + 1} }}\left( {1 + \tfrac{1}
{x}} \right)^m = \tfrac{{\left( {1 + x} \right)^m }}
{{\left( {1 - x} \right)^{m + 1} }}
$

On the other hand:

$
\sum_{t = 0}^{\infty} {\sum_{k = 0}^m {\binom{m}{k}\cdot{\binom{t}{k}}\cdot{2^k} x^t} } = \sum_{k = 0}^{m} {\sum_{t = 0}^{\infty} {\binom{m}{k}\cdot{\binom{t}{k}}\cdot{2^k} x^t} }

$

$
\sum_{t = 0}^{\infty} {\binom{t}{k}\cdot{x^t} } = \sum_{t = k}^{\infty} {\binom{t}{k}x^t }
= x^{k} \cdot \sum_{j = 0}^{\infty} {\binom{j+k}{k}x^j } = \frac{{x^{k} }}
{{\left( {1 - x} \right)^{k + 1} }}
$

Thus: $\sum_{t = 0}^{\infty} {\sum_{k = 0}^m {\binom{m}{k}\cdot{\binom{t}{k}}\cdot{2^k} x^t} } =
\sum_{k = 0}^m {\binom{m}{k} \cdot 2^k \cdot \tfrac{{x^k }}
{{\left( {1 - x} \right)^{k + 1} }}} = \tfrac{1}
{{\left( {1 - x} \right)}}\left( {1 + \frac{{2x}}
{{1 - x}}} \right)^m

$

SO we get that: $
\sum_{t = 0}^{\infty} {\sum_{k = 0}^m {\binom{m}{k}\cdot{\binom{t+k}{m}} x^t} } =\sum_{t = 0}^{\infty} {\sum_{k = 0}^m {\binom{m}{k}\cdot{\binom{t}{k}}\cdot{2^k} x^t} }$

That is, the generating functions are equal, therefore we must have:

$\sum_{k = 0}^m {\binom{m}{k}\cdot{\binom{t+k}{m}}}=\sum_{k = 0}^m {\binom{m}{k}\cdot{\binom{t}{k}}\cdot{2^k} }$
• Nov 1st 2008, 05:30 AM
PaulRS
First note that, given $
n \in \mathbb{Z}
$
, we have $
\int_{ - \pi }^\pi {e^{i \cdot x \cdot n} dx} = \left\{ \begin{gathered}
0{\text{ if }}n \ne 0 \hfill \\
2\pi {\text{ if }}n = 0 \hfill \\
\end{gathered} \right.
$

From there it follows that, given $
n,j \in \mathbb{N}
$
we have: $
\int_{ - \pi }^\pi {\left( {1 + e^{i \cdot x} } \right)^n \cdot e^{ - i \cdot x \cdot j} dx} = 2\pi \cdot \binom{n}{j}
$

Now, let's go to the sums.

The LHS is equal to: $
\tfrac{1}
{{2\pi }} \cdot \sum\limits_{k = 0}^m {\binom{m}{k} \cdot \int_{ - \pi }^\pi {\left( {1 + e^{i \cdot x} } \right)^{t + k} \cdot e^{ - i \cdot x \cdot m} dx} }
$
. by the linearity of the integral: $
\tfrac{1}
{{2\pi }} \cdot \int_{ - \pi }^\pi {\left( {1 + e^{i \cdot x} } \right)^t \cdot e^{ - i \cdot x \cdot m} \cdot \sum\limits_{k = 0}^m {\binom{m}{k}\left( {1 + e^{i \cdot x} } \right)^k } dx}
$

And by the Binomial Theorem this equals: $
\tfrac{1}
{{2\pi }} \cdot \int_{ - \pi }^\pi {\left( {1 + e^{i \cdot x} } \right)^t \cdot e^{ - i \cdot x \cdot m} \cdot \left( {2 + e^{i \cdot x} } \right)^m dx} = \tfrac{1}
{{2\pi }} \cdot \int_{ - \pi }^\pi {\left( {1 + e^{i \cdot x} } \right)^t \cdot \left( {2e^{ - i \cdot x} + 1} \right)^m dx}
$

But by the Binomial Theorem again: $
\int_{ - \pi }^\pi {\left( {1 + e^{i \cdot x} } \right)^t \cdot \left( {2e^{ - i \cdot x} + 1} \right)^m dx} = \int_{ - \pi }^\pi {\left( {1 + e^{i \cdot x} } \right)^t \cdot \sum\limits_{k = 0}^m {\binom{m}{k}\cdot 2^k \cdot e^{ - i \cdot x \cdot k} } dx}
$
and now using the linearity of the integral we get $
\int_{ - \pi }^\pi {\left( {1 + e^{i \cdot x} } \right)^t \cdot \left( {2e^{ - i \cdot x} + 1} \right)^m dx} = 2\pi \cdot \sum\limits_{k = 0}^m {\binom{m}{k}\cdot \binom{t}{k} \cdot 2^k }
$
and we are done

Comment: In general $
\oint_\Gamma {\tfrac{{\left( {1 + z} \right)^n }}
{{z^{j + 1} }}dz} = 2\pi \cdot i \cdot \binom{n}{j}
$
where $
\Gamma
$
is a contour enclosing 0

No animals were harmed during the production of this solution (Rofl)