Results 1 to 4 of 4

Math Help - Sums

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    Sums

    Prove that \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 \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
    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

    <br />
\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} }  <br /> <br />

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

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

    On the other hand:

    <br />
\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} } <br /> <br />

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

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

    SO we get that: <br />
\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} }
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    First note that, given <br />
n \in \mathbb{Z}<br />
, we have <br />
\int_{ - \pi }^\pi  {e^{i \cdot x \cdot n} dx}  = \left\{ \begin{gathered}<br />
  0{\text{ if }}n \ne 0 \hfill \\<br />
  2\pi {\text{ if }}n = 0 \hfill \\ <br />
\end{gathered}  \right.<br />

    From there it follows that, given <br />
n,j \in \mathbb{N}<br />
we have: <br />
\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}<br />

    Now, let's go to the sums.

    The LHS is equal to: <br />
\tfrac{1}<br />
{{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} } <br />
. by the linearity of the integral: <br />
\tfrac{1}<br />
{{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} <br />
    And by the Binomial Theorem this equals: <br />
\tfrac{1}<br />
{{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}<br />
{{2\pi }} \cdot \int_{ - \pi }^\pi  {\left( {1 + e^{i \cdot x} } \right)^t  \cdot \left( {2e^{ - i \cdot x}  + 1} \right)^m dx} <br />

    But by the Binomial Theorem again: <br />
\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} <br />
and now using the linearity of the integral we get <br />
\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 } <br />
and we are done

    Comment: In general <br />
\oint_\Gamma  {\tfrac{{\left( {1 + z} \right)^n }}<br />
{{z^{j + 1} }}dz}  = 2\pi  \cdot i \cdot \binom{n}{j}<br />
where <br />
\Gamma <br />
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: November 15th 2010, 10:27 AM
  2. sums
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 12th 2009, 11:23 AM
  3. sums .
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 23rd 2009, 01:57 AM
  4. Riemann sums
    Posted in the Calculus Forum
    Replies: 4
    Last Post: February 4th 2009, 11:26 AM
  5. sums with lnx
    Posted in the Calculus Forum
    Replies: 15
    Last Post: April 21st 2008, 06:11 PM

Search Tags


/mathhelpforum @mathhelpforum