1. ## Sums

Prove that $\displaystyle \sum_{k=0}^m \binom mk \binom{t+k}{m} =\sum_{k=0}^m\binom mk\binom tk\cdot2^k$.

2. Originally Posted by james_bond
Prove that $\displaystyle \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 $\displaystyle \sum_{k=0}^m \binom mk \binom{t+k}{m} = \binom {2t}{m}$

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

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

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

To get that elusive $\displaystyle 2^k$, I tried the following(in vain)
$\displaystyle (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

3. Let's find the generating functions

$\displaystyle \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: $\displaystyle \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: $\displaystyle \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:

$\displaystyle \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} }$

$\displaystyle \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: $\displaystyle \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: $\displaystyle \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:

$\displaystyle \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} }$

4. First note that, given $\displaystyle n \in \mathbb{Z}$, we have $\displaystyle \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 $\displaystyle n,j \in \mathbb{N}$ we have: $\displaystyle \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: $\displaystyle \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: $\displaystyle \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: $\displaystyle \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: $\displaystyle \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 $\displaystyle \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 $\displaystyle \oint_\Gamma {\tfrac{{\left( {1 + z} \right)^n }} {{z^{j + 1} }}dz} = 2\pi \cdot i \cdot \binom{n}{j}$ where $\displaystyle \Gamma$ is a contour enclosing 0

No animals were harmed during the production of this solution