Sums

Printable View

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} }$
November 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)