Results 1 to 3 of 3

Math Help - Sumatory

  1. #1
    Member Nacho's Avatar
    Joined
    Mar 2008
    From
    Santiago, Chile
    Posts
    135

    Sumatory

    Calculate: <br />
\sum\limits_{k = 0}^n {2^k } \left( {\begin{array}{*{20}c}<br />
   {2n - k}  \\<br />
   n  \\<br /> <br />
 \end{array} } \right)<br />

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Nacho View Post
    Calculate: <br />
\sum\limits_{k = 0}^n {2^k } \left( {\begin{array}{*{20}c}<br />
   {2n - k}  \\<br />
   n  \\<br /> <br />
 \end{array} } \right)<br />
    This seems quite hard. Start by noticing that 2n-k\choose n is the coefficient of x^n in (1+x)^{2n-k}.

    Therefore \sum_{k=0}^n 2^k{2n-k\choose n} is the coefficient of x^n in \sum_{k=0}^n 2^k(1+x)^{2n-k} = f(x).

    But (writing the terms in reverse order) f(x) = 2^n(1+x)^n\sum_{k=0}^n\bigl(\tfrac12(1+x)\bigr)^k = 2^n(1+x)^n \frac{1-\bigl(\tfrac12(1+x)\bigr)^{n+1}}{1-\tfrac12(1+x)} (sum of geometric series), and this simplifies to \frac{2^{n+1}(1+x)^n - (1+x)^{2n+1}}{1-x} = \bigl(2^{n+1}(1+x)^n - (1+x)^{2n+1}\bigr)(1+x+x^2+\ldots). The coefficient of x^n in that expression is the sum of all the binomial coefficients of powers of x in 2^{n+1}(1+x)^n minus the sum of the coefficients in the first half of the expansion of (1+x)^{2n+1}.

    But the sum \sum_{k=0}^n {n\choose k} of all the binomial coefficients of powers of x in (1+x)^n is 2^n. Also, the symmetry of the binomial coefficients (the fact that \textstyle{n\choose k} = {n\choose n-k}) means that the sum \sum_{k=0}^n{2n+1\choose k} of the coefficients in the first half of the expansion of (1+x)^{2n+1} is \tfrac122^{2n+1} = 2^{2n}.

    Therefore \sum_{k=0}^n 2^k{2n-k\choose n} = 2^{n+1}\!\!\times2^n-2^{2n} = 4^n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Nacho's Avatar
    Joined
    Mar 2008
    From
    Santiago, Chile
    Posts
    135
    wonderfull
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sumatory
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 28th 2008, 06:22 PM
  2. Sumatory
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 10th 2008, 08:33 PM

Search Tags


/mathhelpforum @mathhelpforum