Results 1 to 4 of 4

Thread: Sums

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    Sums

    Prove that $\displaystyle \sum_{k=0}^m \binom mk \binom{t+k}{m} =\sum_{k=0}^m\binom mk\binom tk\cdot2^k$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by james_bond View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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} }$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sums of cos(nx) and sin(nx)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2010, 09:27 AM
  2. sums
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Sep 12th 2009, 10:23 AM
  3. sums .
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Feb 23rd 2009, 12:57 AM
  4. Riemann sums
    Posted in the Calculus Forum
    Replies: 4
    Last Post: Feb 4th 2009, 10:26 AM
  5. sums with lnx
    Posted in the Calculus Forum
    Replies: 15
    Last Post: Apr 21st 2008, 05:11 PM

Search Tags


/mathhelpforum @mathhelpforum