A closed form for sum of binomial coefficients












1












$begingroup$


What is a closed form of the sum:



$$binom{n}{0}+binom{n-1}{1}+binom{n-2}{2}+binom{n-3}{3}+cdots$$



A combinatorial proof would also be much appreciated.
Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?






combinatorics summation binomial-coefficients







share|cite|improve this question









$endgroup$












  • $begingroup$
    Try a few values of $n$; then make a guess. You can do it.
    $endgroup$
    – Marc van Leeuwen
    Nov 1 '14 at 10:27










  • $begingroup$
    Perhaps it would help Readers if you give the last term of the sum explicitly (is is finite, is it not?).
    $endgroup$
    – hardmath
    Nov 2 '14 at 17:15










  • $begingroup$
    @hardmath It is finite. By convention $binom{n}{k} = 0$ if $n<k$
    $endgroup$
    – Aditya
    Nov 4 '14 at 8:50






  • 1




    $begingroup$
    @Aditya However, $$ {n - k choose k}=left(,-1,right)^{k}{2k - n - 1 choose k} $$ when $n < k geq 0$.
    $endgroup$
    – Felix Marin
    Nov 5 '14 at 20:36












  • $begingroup$
    @FelixMarin I did not knew about that. I took $binom{n}{k}$ to mean simply as the number of ways to choose $k$ items out of $n$ distinct items.
    $endgroup$
    – Aditya
    Nov 8 '14 at 9:22
















1












$begingroup$


What is a closed form of the sum:



$$binom{n}{0}+binom{n-1}{1}+binom{n-2}{2}+binom{n-3}{3}+cdots$$



A combinatorial proof would also be much appreciated.
Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?






combinatorics summation binomial-coefficients







share|cite|improve this question









$endgroup$












  • $begingroup$
    Try a few values of $n$; then make a guess. You can do it.
    $endgroup$
    – Marc van Leeuwen
    Nov 1 '14 at 10:27










  • $begingroup$
    Perhaps it would help Readers if you give the last term of the sum explicitly (is is finite, is it not?).
    $endgroup$
    – hardmath
    Nov 2 '14 at 17:15










  • $begingroup$
    @hardmath It is finite. By convention $binom{n}{k} = 0$ if $n<k$
    $endgroup$
    – Aditya
    Nov 4 '14 at 8:50






  • 1




    $begingroup$
    @Aditya However, $$ {n - k choose k}=left(,-1,right)^{k}{2k - n - 1 choose k} $$ when $n < k geq 0$.
    $endgroup$
    – Felix Marin
    Nov 5 '14 at 20:36












  • $begingroup$
    @FelixMarin I did not knew about that. I took $binom{n}{k}$ to mean simply as the number of ways to choose $k$ items out of $n$ distinct items.
    $endgroup$
    – Aditya
    Nov 8 '14 at 9:22














1












1








1


2



$begingroup$


What is a closed form of the sum:



$$binom{n}{0}+binom{n-1}{1}+binom{n-2}{2}+binom{n-3}{3}+cdots$$



A combinatorial proof would also be much appreciated.
Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?






combinatorics summation binomial-coefficients







share|cite|improve this question









$endgroup$




What is a closed form of the sum:



$$binom{n}{0}+binom{n-1}{1}+binom{n-2}{2}+binom{n-3}{3}+cdots$$



A combinatorial proof would also be much appreciated.
Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?






combinatorics summation binomial-coefficients




combinatorics summation binomial-coefficients






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Nov 1 '14 at 10:22









AdityaAditya

18116




18116












  • $begingroup$
    Try a few values of $n$; then make a guess. You can do it.
    $endgroup$
    – Marc van Leeuwen
    Nov 1 '14 at 10:27










  • $begingroup$
    Perhaps it would help Readers if you give the last term of the sum explicitly (is is finite, is it not?).
    $endgroup$
    – hardmath
    Nov 2 '14 at 17:15










  • $begingroup$
    @hardmath It is finite. By convention $binom{n}{k} = 0$ if $n<k$
    $endgroup$
    – Aditya
    Nov 4 '14 at 8:50






  • 1




    $begingroup$
    @Aditya However, $$ {n - k choose k}=left(,-1,right)^{k}{2k - n - 1 choose k} $$ when $n < k geq 0$.
    $endgroup$
    – Felix Marin
    Nov 5 '14 at 20:36












  • $begingroup$
    @FelixMarin I did not knew about that. I took $binom{n}{k}$ to mean simply as the number of ways to choose $k$ items out of $n$ distinct items.
    $endgroup$
    – Aditya
    Nov 8 '14 at 9:22


















  • $begingroup$
    Try a few values of $n$; then make a guess. You can do it.
    $endgroup$
    – Marc van Leeuwen
    Nov 1 '14 at 10:27










  • $begingroup$
    Perhaps it would help Readers if you give the last term of the sum explicitly (is is finite, is it not?).
    $endgroup$
    – hardmath
    Nov 2 '14 at 17:15










  • $begingroup$
    @hardmath It is finite. By convention $binom{n}{k} = 0$ if $n<k$
    $endgroup$
    – Aditya
    Nov 4 '14 at 8:50






  • 1




    $begingroup$
    @Aditya However, $$ {n - k choose k}=left(,-1,right)^{k}{2k - n - 1 choose k} $$ when $n < k geq 0$.
    $endgroup$
    – Felix Marin
    Nov 5 '14 at 20:36












  • $begingroup$
    @FelixMarin I did not knew about that. I took $binom{n}{k}$ to mean simply as the number of ways to choose $k$ items out of $n$ distinct items.
    $endgroup$
    – Aditya
    Nov 8 '14 at 9:22
















$begingroup$
Try a few values of $n$; then make a guess. You can do it.
$endgroup$
– Marc van Leeuwen
Nov 1 '14 at 10:27




$begingroup$
Try a few values of $n$; then make a guess. You can do it.
$endgroup$
– Marc van Leeuwen
Nov 1 '14 at 10:27












$begingroup$
Perhaps it would help Readers if you give the last term of the sum explicitly (is is finite, is it not?).
$endgroup$
– hardmath
Nov 2 '14 at 17:15




$begingroup$
Perhaps it would help Readers if you give the last term of the sum explicitly (is is finite, is it not?).
$endgroup$
– hardmath
Nov 2 '14 at 17:15












$begingroup$
@hardmath It is finite. By convention $binom{n}{k} = 0$ if $n<k$
$endgroup$
– Aditya
Nov 4 '14 at 8:50




$begingroup$
@hardmath It is finite. By convention $binom{n}{k} = 0$ if $n<k$
$endgroup$
– Aditya
Nov 4 '14 at 8:50




1




1




$begingroup$
@Aditya However, $$ {n - k choose k}=left(,-1,right)^{k}{2k - n - 1 choose k} $$ when $n < k geq 0$.
$endgroup$
– Felix Marin
Nov 5 '14 at 20:36






$begingroup$
@Aditya However, $$ {n - k choose k}=left(,-1,right)^{k}{2k - n - 1 choose k} $$ when $n < k geq 0$.
$endgroup$
– Felix Marin
Nov 5 '14 at 20:36














$begingroup$
@FelixMarin I did not knew about that. I took $binom{n}{k}$ to mean simply as the number of ways to choose $k$ items out of $n$ distinct items.
$endgroup$
– Aditya
Nov 8 '14 at 9:22




$begingroup$
@FelixMarin I did not knew about that. I took $binom{n}{k}$ to mean simply as the number of ways to choose $k$ items out of $n$ distinct items.
$endgroup$
– Aditya
Nov 8 '14 at 9:22










4 Answers
4






active

oldest

votes


















6












$begingroup$

Hint for a combinatorial proof. Count the number of sequences of $1$s and $2$s which add up to $n$.



Method 1. Explain why the number of such sequences which include exactly $k$ $2$s is $binom{n-k}{k}$.



Method 2. Show that if $a_n$ is the number of sequences then $a_n=a_{n-1}+a_{n-2}$.



Hint for a pictorial proof.
$$defr{color{red}{bullet}}defb{color{blue}{bullet}}defg{color{green}{bullet}}
defw{circ}defs{ }%
matrix{
wcr
wswcr
wswswcr
wswswsgcr
wswsgsbsrcr
wsgsbsrswswcr
gsbsrswswswswcr
bsrswswswswswswcr
rswswswswswswswswcr}$$
The terms in your expression are the red dots in Pascal's triangle. Each is the sum of the green and blue dots just above it. So the sum of all red dots is equal to the sum of all blue dots plus the sum of all green dots.



See if you can fill in the details. Good luck!






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Wow! Thanks :) Fibonacci numbers are beautiful!
    $endgroup$
    – Aditya
    Nov 4 '14 at 8:49



















3












$begingroup$


Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?




A general approach: consider $c_n=sumlimits_{k=0}^na_{k,n-k}$ for some given family of coefficients $(a_{k,n})$ and assume that, for every fixed $n$, the polynomial $A_n(x)=sumlimits_{k=0}^na_{k,n}x^k$ is known. Then, $$sum_{n=0}^infty A_n(x)x^n=sum_{kgeqslant0,ngeqslant0}a_{k,n}x^{k+n}=sum_{n=0}^infty c_nx^n.$$ In particular, if the generating function on the LHS can be computed, one can hope to recover the value of every $c_n$.



Your case is when $a_{n,k}={nchoose k}$, then the approach outlined above works like a charm...






share|cite|improve this answer









$endgroup$





















    2












    $begingroup$

    HINT:



    The coefficient of $x^n$ in



    $$(1+x)^n+x^2(1+x)^{n-1}+x^4(1+x)^{n-2}+cdots$$ which is a Geometric Series with common ratio $dfrac{x^2}{1+x}$ which can be safely set in $(-1,1)$ to utilize Infinite Sum formula






    share|cite|improve this answer











    $endgroup$





















      2












      $begingroup$

      $newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
      newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
      newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
      newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
      newcommand{dd}{{rm d}}
      newcommand{ds}[1]{displaystyle{#1}}
      newcommand{expo}[1]{,{rm e}^{#1},}
      newcommand{fermi}{,{rm f}}
      newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
      newcommand{half}{{1 over 2}}
      newcommand{ic}{{rm i}}
      newcommand{iff}{Longleftrightarrow}
      newcommand{imp}{Longrightarrow}
      newcommand{pars}[1]{left(, #1 ,right)}
      newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
      newcommand{pp}{{cal P}}
      newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
      newcommand{sech}{,{rm sech}}
      newcommand{sgn}{,{rm sgn}}
      newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
      newcommand{ul}[1]{underline{#1}}
      newcommand{verts}[1]{leftvert, #1 ,rightvert}$
      begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
      =sum_{k = 0}^{n} overbrace{oint_{verts{z} = 1}%
      {pars{1 + z}^{k} over z^{n - k + 1}},{dd z over 2piic}}
      ^{ds{= color{#c00000}{k choose n - k}}}
      \[5mm] = &
      oint_{verts{z} = 1}{1 over z^{n + 1}}
      sum_{k = 0}^{n}bracks{pars{1 + z}z}^{k}
      ,{dd z over 2piic}
      \[5mm]&=oint_{verts{z} = 1}{1 over z^{n + 1}}
      {bracks{pars{1 + z}z}^{n + 1} - 1 over pars{1 + z}z - 1}
      ,{dd z over 2piic}
      \[5mm]&=oint_{verts{z} = 1}
      {pars{1 + z}^{n + 1} over pars{z - r_{-}}pars{z - r_{+}}}
      ,{dd z over 2piic}
      \[2mm] &
      -oint_{verts{z} = 1}
      {1 over z^{n + 1}pars{z - r_{-}}pars{z - r_{+}}}
      ,{dd z over 2piic}label{1}tag{1}
      end{align}




      where $ds{r_{mp} = {-1 mp root{5} over 2}}$ are the roots of
      $ds{z^{2} + z - 1 = 0}$. $ds{r_{-} = -phi}$ and
      $ds{r_{+} = phi - 1 = {1 over phi}}$.
      $ds{phi equiv {1 + root{5} over 2}}$ is the Golden Ratio.




      $$
      mbox{Note that}quad
      r_{-} < -1,,quad 0 < r_{+} < 1.,qquad r_{-}r_{+} = r_{-} + r_{+} = -1.quad
      r_{+} - r_{-} = root{5}
      $$




      From expression eqref{1}:
      begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
      \[5mm] = &
      {pars{1 + r_{+}}^{n + 1} over r_{+} - r_{-}}
      -{1 over r_{+} - r_{-}}oint_{verts{z} = 1}
      {1 over z^{n + 1}pars{z - r_{+}}},{dd z over 2piic}
      \&+
      {1 over r_{+} - r_{-}}oint_{verts{z} = 1}
      {1 over z^{n + 1}pars{z - r_{-}}},{dd z over 2piic}
      \[5mm]&={phi^{n + 1} over root{5}}
      -{1 over root{5}}color{#00f}{oint_{verts{z} = 1}
      {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
      \&-{1 over root{5}r_{-}}color{#c00000}{oint_{verts{z} = 1}
      {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}label{2}tag{2}
      end{align}




      begin{align}&color{#00f}{oint_{verts{z} = 1}
      {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
      =sum_{k = 0}^{infty}r_{+}^{k}oint_{verts{z} = 1}
      {1 over z^{n + 2 + k}},{dd z over 2piic}=color{#00f}{0}label{3}tag{3}
      end{align}




      begin{align}&color{#c00000}{oint_{verts{z} = 1}
      {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}
      =sum_{k = 0}^{infty}{1 over r_{-}^{k}}oint_{verts{z} = 1}
      {1 over z^{n + 1 - k}},{dd z over 2piic}={1 over r_{-}^{n}}
      =color{#c00000}{{1 over pars{-phi}^{n}}}
      label{4}tag{4}
      end{align}




      With eqref{2}, eqref{3} and eqref{4}:
      begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
      ={phi^{n + 1} over root{5}} - {1 over root{5}pars{-phi}},
      {1 over pars{-phi}^{n}}
      =color{#66f}{large{phi^{n + 1} + pars{-1}^{n}phi^{-n - 1} over root{5}}}
      end{align}
      which is the $ds{pars{n + 1}}$-Fibonacci Number.






      share|cite|improve this answer











      $endgroup$













        Your Answer





        StackExchange.ifUsing("editor", function () {
        return StackExchange.using("mathjaxEditing", function () {
        StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
        StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
        });
        });
        }, "mathjax-editing");

        StackExchange.ready(function() {
        var channelOptions = {
        tags: "".split(" "),
        id: "69"
        };
        initTagRenderer("".split(" "), "".split(" "), channelOptions);

        StackExchange.using("externalEditor", function() {
        // Have to fire editor after snippets, if snippets enabled
        if (StackExchange.settings.snippets.snippetsEnabled) {
        StackExchange.using("snippets", function() {
        createEditor();
        });
        }
        else {
        createEditor();
        }
        });

        function createEditor() {
        StackExchange.prepareEditor({
        heartbeatType: 'answer',
        autoActivateHeartbeat: false,
        convertImagesToLinks: true,
        noModals: true,
        showLowRepImageUploadWarning: true,
        reputationToPostImages: 10,
        bindNavPrevention: true,
        postfix: "",
        imageUploader: {
        brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
        contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
        allowUrls: true
        },
        noCode: true, onDemand: true,
        discardSelector: ".discard-answer"
        ,immediatelyShowMarkdownHelp:true
        });


        }
        });














        draft saved

        draft discarded


















        StackExchange.ready(
        function () {
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1001040%2fa-closed-form-for-sum-of-binomial-coefficients%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        4 Answers
        4






        active

        oldest

        votes








        4 Answers
        4






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        6












        $begingroup$

        Hint for a combinatorial proof. Count the number of sequences of $1$s and $2$s which add up to $n$.



        Method 1. Explain why the number of such sequences which include exactly $k$ $2$s is $binom{n-k}{k}$.



        Method 2. Show that if $a_n$ is the number of sequences then $a_n=a_{n-1}+a_{n-2}$.



        Hint for a pictorial proof.
        $$defr{color{red}{bullet}}defb{color{blue}{bullet}}defg{color{green}{bullet}}
        defw{circ}defs{ }%
        matrix{
        wcr
        wswcr
        wswswcr
        wswswsgcr
        wswsgsbsrcr
        wsgsbsrswswcr
        gsbsrswswswswcr
        bsrswswswswswswcr
        rswswswswswswswswcr}$$
        The terms in your expression are the red dots in Pascal's triangle. Each is the sum of the green and blue dots just above it. So the sum of all red dots is equal to the sum of all blue dots plus the sum of all green dots.



        See if you can fill in the details. Good luck!






        share|cite|improve this answer











        $endgroup$













        • $begingroup$
          Wow! Thanks :) Fibonacci numbers are beautiful!
          $endgroup$
          – Aditya
          Nov 4 '14 at 8:49
















        6












        $begingroup$

        Hint for a combinatorial proof. Count the number of sequences of $1$s and $2$s which add up to $n$.



        Method 1. Explain why the number of such sequences which include exactly $k$ $2$s is $binom{n-k}{k}$.



        Method 2. Show that if $a_n$ is the number of sequences then $a_n=a_{n-1}+a_{n-2}$.



        Hint for a pictorial proof.
        $$defr{color{red}{bullet}}defb{color{blue}{bullet}}defg{color{green}{bullet}}
        defw{circ}defs{ }%
        matrix{
        wcr
        wswcr
        wswswcr
        wswswsgcr
        wswsgsbsrcr
        wsgsbsrswswcr
        gsbsrswswswswcr
        bsrswswswswswswcr
        rswswswswswswswswcr}$$
        The terms in your expression are the red dots in Pascal's triangle. Each is the sum of the green and blue dots just above it. So the sum of all red dots is equal to the sum of all blue dots plus the sum of all green dots.



        See if you can fill in the details. Good luck!






        share|cite|improve this answer











        $endgroup$













        • $begingroup$
          Wow! Thanks :) Fibonacci numbers are beautiful!
          $endgroup$
          – Aditya
          Nov 4 '14 at 8:49














        6












        6








        6





        $begingroup$

        Hint for a combinatorial proof. Count the number of sequences of $1$s and $2$s which add up to $n$.



        Method 1. Explain why the number of such sequences which include exactly $k$ $2$s is $binom{n-k}{k}$.



        Method 2. Show that if $a_n$ is the number of sequences then $a_n=a_{n-1}+a_{n-2}$.



        Hint for a pictorial proof.
        $$defr{color{red}{bullet}}defb{color{blue}{bullet}}defg{color{green}{bullet}}
        defw{circ}defs{ }%
        matrix{
        wcr
        wswcr
        wswswcr
        wswswsgcr
        wswsgsbsrcr
        wsgsbsrswswcr
        gsbsrswswswswcr
        bsrswswswswswswcr
        rswswswswswswswswcr}$$
        The terms in your expression are the red dots in Pascal's triangle. Each is the sum of the green and blue dots just above it. So the sum of all red dots is equal to the sum of all blue dots plus the sum of all green dots.



        See if you can fill in the details. Good luck!






        share|cite|improve this answer











        $endgroup$



        Hint for a combinatorial proof. Count the number of sequences of $1$s and $2$s which add up to $n$.



        Method 1. Explain why the number of such sequences which include exactly $k$ $2$s is $binom{n-k}{k}$.



        Method 2. Show that if $a_n$ is the number of sequences then $a_n=a_{n-1}+a_{n-2}$.



        Hint for a pictorial proof.
        $$defr{color{red}{bullet}}defb{color{blue}{bullet}}defg{color{green}{bullet}}
        defw{circ}defs{ }%
        matrix{
        wcr
        wswcr
        wswswcr
        wswswsgcr
        wswsgsbsrcr
        wsgsbsrswswcr
        gsbsrswswswswcr
        bsrswswswswswswcr
        rswswswswswswswswcr}$$
        The terms in your expression are the red dots in Pascal's triangle. Each is the sum of the green and blue dots just above it. So the sum of all red dots is equal to the sum of all blue dots plus the sum of all green dots.



        See if you can fill in the details. Good luck!







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Nov 1 '14 at 12:00

























        answered Nov 1 '14 at 10:48









        DavidDavid

        68.1k664126




        68.1k664126












        • $begingroup$
          Wow! Thanks :) Fibonacci numbers are beautiful!
          $endgroup$
          – Aditya
          Nov 4 '14 at 8:49


















        • $begingroup$
          Wow! Thanks :) Fibonacci numbers are beautiful!
          $endgroup$
          – Aditya
          Nov 4 '14 at 8:49
















        $begingroup$
        Wow! Thanks :) Fibonacci numbers are beautiful!
        $endgroup$
        – Aditya
        Nov 4 '14 at 8:49




        $begingroup$
        Wow! Thanks :) Fibonacci numbers are beautiful!
        $endgroup$
        – Aditya
        Nov 4 '14 at 8:49











        3












        $begingroup$


        Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?




        A general approach: consider $c_n=sumlimits_{k=0}^na_{k,n-k}$ for some given family of coefficients $(a_{k,n})$ and assume that, for every fixed $n$, the polynomial $A_n(x)=sumlimits_{k=0}^na_{k,n}x^k$ is known. Then, $$sum_{n=0}^infty A_n(x)x^n=sum_{kgeqslant0,ngeqslant0}a_{k,n}x^{k+n}=sum_{n=0}^infty c_nx^n.$$ In particular, if the generating function on the LHS can be computed, one can hope to recover the value of every $c_n$.



        Your case is when $a_{n,k}={nchoose k}$, then the approach outlined above works like a charm...






        share|cite|improve this answer









        $endgroup$


















          3












          $begingroup$


          Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?




          A general approach: consider $c_n=sumlimits_{k=0}^na_{k,n-k}$ for some given family of coefficients $(a_{k,n})$ and assume that, for every fixed $n$, the polynomial $A_n(x)=sumlimits_{k=0}^na_{k,n}x^k$ is known. Then, $$sum_{n=0}^infty A_n(x)x^n=sum_{kgeqslant0,ngeqslant0}a_{k,n}x^{k+n}=sum_{n=0}^infty c_nx^n.$$ In particular, if the generating function on the LHS can be computed, one can hope to recover the value of every $c_n$.



          Your case is when $a_{n,k}={nchoose k}$, then the approach outlined above works like a charm...






          share|cite|improve this answer









          $endgroup$
















            3












            3








            3





            $begingroup$


            Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?




            A general approach: consider $c_n=sumlimits_{k=0}^na_{k,n-k}$ for some given family of coefficients $(a_{k,n})$ and assume that, for every fixed $n$, the polynomial $A_n(x)=sumlimits_{k=0}^na_{k,n}x^k$ is known. Then, $$sum_{n=0}^infty A_n(x)x^n=sum_{kgeqslant0,ngeqslant0}a_{k,n}x^{k+n}=sum_{n=0}^infty c_nx^n.$$ In particular, if the generating function on the LHS can be computed, one can hope to recover the value of every $c_n$.



            Your case is when $a_{n,k}={nchoose k}$, then the approach outlined above works like a charm...






            share|cite|improve this answer









            $endgroup$




            Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?




            A general approach: consider $c_n=sumlimits_{k=0}^na_{k,n-k}$ for some given family of coefficients $(a_{k,n})$ and assume that, for every fixed $n$, the polynomial $A_n(x)=sumlimits_{k=0}^na_{k,n}x^k$ is known. Then, $$sum_{n=0}^infty A_n(x)x^n=sum_{kgeqslant0,ngeqslant0}a_{k,n}x^{k+n}=sum_{n=0}^infty c_nx^n.$$ In particular, if the generating function on the LHS can be computed, one can hope to recover the value of every $c_n$.



            Your case is when $a_{n,k}={nchoose k}$, then the approach outlined above works like a charm...







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Nov 1 '14 at 10:37









            DidDid

            247k23222458




            247k23222458























                2












                $begingroup$

                HINT:



                The coefficient of $x^n$ in



                $$(1+x)^n+x^2(1+x)^{n-1}+x^4(1+x)^{n-2}+cdots$$ which is a Geometric Series with common ratio $dfrac{x^2}{1+x}$ which can be safely set in $(-1,1)$ to utilize Infinite Sum formula






                share|cite|improve this answer











                $endgroup$


















                  2












                  $begingroup$

                  HINT:



                  The coefficient of $x^n$ in



                  $$(1+x)^n+x^2(1+x)^{n-1}+x^4(1+x)^{n-2}+cdots$$ which is a Geometric Series with common ratio $dfrac{x^2}{1+x}$ which can be safely set in $(-1,1)$ to utilize Infinite Sum formula






                  share|cite|improve this answer











                  $endgroup$
















                    2












                    2








                    2





                    $begingroup$

                    HINT:



                    The coefficient of $x^n$ in



                    $$(1+x)^n+x^2(1+x)^{n-1}+x^4(1+x)^{n-2}+cdots$$ which is a Geometric Series with common ratio $dfrac{x^2}{1+x}$ which can be safely set in $(-1,1)$ to utilize Infinite Sum formula






                    share|cite|improve this answer











                    $endgroup$



                    HINT:



                    The coefficient of $x^n$ in



                    $$(1+x)^n+x^2(1+x)^{n-1}+x^4(1+x)^{n-2}+cdots$$ which is a Geometric Series with common ratio $dfrac{x^2}{1+x}$ which can be safely set in $(-1,1)$ to utilize Infinite Sum formula







                    share|cite|improve this answer














                    share|cite|improve this answer



                    share|cite|improve this answer








                    edited Nov 1 '14 at 10:56

























                    answered Nov 1 '14 at 10:49









                    lab bhattacharjeelab bhattacharjee

                    224k15156274




                    224k15156274























                        2












                        $begingroup$

                        $newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
                        newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
                        newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
                        newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
                        newcommand{dd}{{rm d}}
                        newcommand{ds}[1]{displaystyle{#1}}
                        newcommand{expo}[1]{,{rm e}^{#1},}
                        newcommand{fermi}{,{rm f}}
                        newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
                        newcommand{half}{{1 over 2}}
                        newcommand{ic}{{rm i}}
                        newcommand{iff}{Longleftrightarrow}
                        newcommand{imp}{Longrightarrow}
                        newcommand{pars}[1]{left(, #1 ,right)}
                        newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
                        newcommand{pp}{{cal P}}
                        newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
                        newcommand{sech}{,{rm sech}}
                        newcommand{sgn}{,{rm sgn}}
                        newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
                        newcommand{ul}[1]{underline{#1}}
                        newcommand{verts}[1]{leftvert, #1 ,rightvert}$
                        begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                        =sum_{k = 0}^{n} overbrace{oint_{verts{z} = 1}%
                        {pars{1 + z}^{k} over z^{n - k + 1}},{dd z over 2piic}}
                        ^{ds{= color{#c00000}{k choose n - k}}}
                        \[5mm] = &
                        oint_{verts{z} = 1}{1 over z^{n + 1}}
                        sum_{k = 0}^{n}bracks{pars{1 + z}z}^{k}
                        ,{dd z over 2piic}
                        \[5mm]&=oint_{verts{z} = 1}{1 over z^{n + 1}}
                        {bracks{pars{1 + z}z}^{n + 1} - 1 over pars{1 + z}z - 1}
                        ,{dd z over 2piic}
                        \[5mm]&=oint_{verts{z} = 1}
                        {pars{1 + z}^{n + 1} over pars{z - r_{-}}pars{z - r_{+}}}
                        ,{dd z over 2piic}
                        \[2mm] &
                        -oint_{verts{z} = 1}
                        {1 over z^{n + 1}pars{z - r_{-}}pars{z - r_{+}}}
                        ,{dd z over 2piic}label{1}tag{1}
                        end{align}




                        where $ds{r_{mp} = {-1 mp root{5} over 2}}$ are the roots of
                        $ds{z^{2} + z - 1 = 0}$. $ds{r_{-} = -phi}$ and
                        $ds{r_{+} = phi - 1 = {1 over phi}}$.
                        $ds{phi equiv {1 + root{5} over 2}}$ is the Golden Ratio.




                        $$
                        mbox{Note that}quad
                        r_{-} < -1,,quad 0 < r_{+} < 1.,qquad r_{-}r_{+} = r_{-} + r_{+} = -1.quad
                        r_{+} - r_{-} = root{5}
                        $$




                        From expression eqref{1}:
                        begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                        \[5mm] = &
                        {pars{1 + r_{+}}^{n + 1} over r_{+} - r_{-}}
                        -{1 over r_{+} - r_{-}}oint_{verts{z} = 1}
                        {1 over z^{n + 1}pars{z - r_{+}}},{dd z over 2piic}
                        \&+
                        {1 over r_{+} - r_{-}}oint_{verts{z} = 1}
                        {1 over z^{n + 1}pars{z - r_{-}}},{dd z over 2piic}
                        \[5mm]&={phi^{n + 1} over root{5}}
                        -{1 over root{5}}color{#00f}{oint_{verts{z} = 1}
                        {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
                        \&-{1 over root{5}r_{-}}color{#c00000}{oint_{verts{z} = 1}
                        {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}label{2}tag{2}
                        end{align}




                        begin{align}&color{#00f}{oint_{verts{z} = 1}
                        {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
                        =sum_{k = 0}^{infty}r_{+}^{k}oint_{verts{z} = 1}
                        {1 over z^{n + 2 + k}},{dd z over 2piic}=color{#00f}{0}label{3}tag{3}
                        end{align}




                        begin{align}&color{#c00000}{oint_{verts{z} = 1}
                        {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}
                        =sum_{k = 0}^{infty}{1 over r_{-}^{k}}oint_{verts{z} = 1}
                        {1 over z^{n + 1 - k}},{dd z over 2piic}={1 over r_{-}^{n}}
                        =color{#c00000}{{1 over pars{-phi}^{n}}}
                        label{4}tag{4}
                        end{align}




                        With eqref{2}, eqref{3} and eqref{4}:
                        begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                        ={phi^{n + 1} over root{5}} - {1 over root{5}pars{-phi}},
                        {1 over pars{-phi}^{n}}
                        =color{#66f}{large{phi^{n + 1} + pars{-1}^{n}phi^{-n - 1} over root{5}}}
                        end{align}
                        which is the $ds{pars{n + 1}}$-Fibonacci Number.






                        share|cite|improve this answer











                        $endgroup$


















                          2












                          $begingroup$

                          $newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
                          newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
                          newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
                          newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
                          newcommand{dd}{{rm d}}
                          newcommand{ds}[1]{displaystyle{#1}}
                          newcommand{expo}[1]{,{rm e}^{#1},}
                          newcommand{fermi}{,{rm f}}
                          newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
                          newcommand{half}{{1 over 2}}
                          newcommand{ic}{{rm i}}
                          newcommand{iff}{Longleftrightarrow}
                          newcommand{imp}{Longrightarrow}
                          newcommand{pars}[1]{left(, #1 ,right)}
                          newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
                          newcommand{pp}{{cal P}}
                          newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
                          newcommand{sech}{,{rm sech}}
                          newcommand{sgn}{,{rm sgn}}
                          newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
                          newcommand{ul}[1]{underline{#1}}
                          newcommand{verts}[1]{leftvert, #1 ,rightvert}$
                          begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                          =sum_{k = 0}^{n} overbrace{oint_{verts{z} = 1}%
                          {pars{1 + z}^{k} over z^{n - k + 1}},{dd z over 2piic}}
                          ^{ds{= color{#c00000}{k choose n - k}}}
                          \[5mm] = &
                          oint_{verts{z} = 1}{1 over z^{n + 1}}
                          sum_{k = 0}^{n}bracks{pars{1 + z}z}^{k}
                          ,{dd z over 2piic}
                          \[5mm]&=oint_{verts{z} = 1}{1 over z^{n + 1}}
                          {bracks{pars{1 + z}z}^{n + 1} - 1 over pars{1 + z}z - 1}
                          ,{dd z over 2piic}
                          \[5mm]&=oint_{verts{z} = 1}
                          {pars{1 + z}^{n + 1} over pars{z - r_{-}}pars{z - r_{+}}}
                          ,{dd z over 2piic}
                          \[2mm] &
                          -oint_{verts{z} = 1}
                          {1 over z^{n + 1}pars{z - r_{-}}pars{z - r_{+}}}
                          ,{dd z over 2piic}label{1}tag{1}
                          end{align}




                          where $ds{r_{mp} = {-1 mp root{5} over 2}}$ are the roots of
                          $ds{z^{2} + z - 1 = 0}$. $ds{r_{-} = -phi}$ and
                          $ds{r_{+} = phi - 1 = {1 over phi}}$.
                          $ds{phi equiv {1 + root{5} over 2}}$ is the Golden Ratio.




                          $$
                          mbox{Note that}quad
                          r_{-} < -1,,quad 0 < r_{+} < 1.,qquad r_{-}r_{+} = r_{-} + r_{+} = -1.quad
                          r_{+} - r_{-} = root{5}
                          $$




                          From expression eqref{1}:
                          begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                          \[5mm] = &
                          {pars{1 + r_{+}}^{n + 1} over r_{+} - r_{-}}
                          -{1 over r_{+} - r_{-}}oint_{verts{z} = 1}
                          {1 over z^{n + 1}pars{z - r_{+}}},{dd z over 2piic}
                          \&+
                          {1 over r_{+} - r_{-}}oint_{verts{z} = 1}
                          {1 over z^{n + 1}pars{z - r_{-}}},{dd z over 2piic}
                          \[5mm]&={phi^{n + 1} over root{5}}
                          -{1 over root{5}}color{#00f}{oint_{verts{z} = 1}
                          {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
                          \&-{1 over root{5}r_{-}}color{#c00000}{oint_{verts{z} = 1}
                          {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}label{2}tag{2}
                          end{align}




                          begin{align}&color{#00f}{oint_{verts{z} = 1}
                          {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
                          =sum_{k = 0}^{infty}r_{+}^{k}oint_{verts{z} = 1}
                          {1 over z^{n + 2 + k}},{dd z over 2piic}=color{#00f}{0}label{3}tag{3}
                          end{align}




                          begin{align}&color{#c00000}{oint_{verts{z} = 1}
                          {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}
                          =sum_{k = 0}^{infty}{1 over r_{-}^{k}}oint_{verts{z} = 1}
                          {1 over z^{n + 1 - k}},{dd z over 2piic}={1 over r_{-}^{n}}
                          =color{#c00000}{{1 over pars{-phi}^{n}}}
                          label{4}tag{4}
                          end{align}




                          With eqref{2}, eqref{3} and eqref{4}:
                          begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                          ={phi^{n + 1} over root{5}} - {1 over root{5}pars{-phi}},
                          {1 over pars{-phi}^{n}}
                          =color{#66f}{large{phi^{n + 1} + pars{-1}^{n}phi^{-n - 1} over root{5}}}
                          end{align}
                          which is the $ds{pars{n + 1}}$-Fibonacci Number.






                          share|cite|improve this answer











                          $endgroup$
















                            2












                            2








                            2





                            $begingroup$

                            $newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
                            newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
                            newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
                            newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
                            newcommand{dd}{{rm d}}
                            newcommand{ds}[1]{displaystyle{#1}}
                            newcommand{expo}[1]{,{rm e}^{#1},}
                            newcommand{fermi}{,{rm f}}
                            newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
                            newcommand{half}{{1 over 2}}
                            newcommand{ic}{{rm i}}
                            newcommand{iff}{Longleftrightarrow}
                            newcommand{imp}{Longrightarrow}
                            newcommand{pars}[1]{left(, #1 ,right)}
                            newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
                            newcommand{pp}{{cal P}}
                            newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
                            newcommand{sech}{,{rm sech}}
                            newcommand{sgn}{,{rm sgn}}
                            newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
                            newcommand{ul}[1]{underline{#1}}
                            newcommand{verts}[1]{leftvert, #1 ,rightvert}$
                            begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                            =sum_{k = 0}^{n} overbrace{oint_{verts{z} = 1}%
                            {pars{1 + z}^{k} over z^{n - k + 1}},{dd z over 2piic}}
                            ^{ds{= color{#c00000}{k choose n - k}}}
                            \[5mm] = &
                            oint_{verts{z} = 1}{1 over z^{n + 1}}
                            sum_{k = 0}^{n}bracks{pars{1 + z}z}^{k}
                            ,{dd z over 2piic}
                            \[5mm]&=oint_{verts{z} = 1}{1 over z^{n + 1}}
                            {bracks{pars{1 + z}z}^{n + 1} - 1 over pars{1 + z}z - 1}
                            ,{dd z over 2piic}
                            \[5mm]&=oint_{verts{z} = 1}
                            {pars{1 + z}^{n + 1} over pars{z - r_{-}}pars{z - r_{+}}}
                            ,{dd z over 2piic}
                            \[2mm] &
                            -oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{z - r_{-}}pars{z - r_{+}}}
                            ,{dd z over 2piic}label{1}tag{1}
                            end{align}




                            where $ds{r_{mp} = {-1 mp root{5} over 2}}$ are the roots of
                            $ds{z^{2} + z - 1 = 0}$. $ds{r_{-} = -phi}$ and
                            $ds{r_{+} = phi - 1 = {1 over phi}}$.
                            $ds{phi equiv {1 + root{5} over 2}}$ is the Golden Ratio.




                            $$
                            mbox{Note that}quad
                            r_{-} < -1,,quad 0 < r_{+} < 1.,qquad r_{-}r_{+} = r_{-} + r_{+} = -1.quad
                            r_{+} - r_{-} = root{5}
                            $$




                            From expression eqref{1}:
                            begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                            \[5mm] = &
                            {pars{1 + r_{+}}^{n + 1} over r_{+} - r_{-}}
                            -{1 over r_{+} - r_{-}}oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{z - r_{+}}},{dd z over 2piic}
                            \&+
                            {1 over r_{+} - r_{-}}oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{z - r_{-}}},{dd z over 2piic}
                            \[5mm]&={phi^{n + 1} over root{5}}
                            -{1 over root{5}}color{#00f}{oint_{verts{z} = 1}
                            {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
                            \&-{1 over root{5}r_{-}}color{#c00000}{oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}label{2}tag{2}
                            end{align}




                            begin{align}&color{#00f}{oint_{verts{z} = 1}
                            {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
                            =sum_{k = 0}^{infty}r_{+}^{k}oint_{verts{z} = 1}
                            {1 over z^{n + 2 + k}},{dd z over 2piic}=color{#00f}{0}label{3}tag{3}
                            end{align}




                            begin{align}&color{#c00000}{oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}
                            =sum_{k = 0}^{infty}{1 over r_{-}^{k}}oint_{verts{z} = 1}
                            {1 over z^{n + 1 - k}},{dd z over 2piic}={1 over r_{-}^{n}}
                            =color{#c00000}{{1 over pars{-phi}^{n}}}
                            label{4}tag{4}
                            end{align}




                            With eqref{2}, eqref{3} and eqref{4}:
                            begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                            ={phi^{n + 1} over root{5}} - {1 over root{5}pars{-phi}},
                            {1 over pars{-phi}^{n}}
                            =color{#66f}{large{phi^{n + 1} + pars{-1}^{n}phi^{-n - 1} over root{5}}}
                            end{align}
                            which is the $ds{pars{n + 1}}$-Fibonacci Number.






                            share|cite|improve this answer











                            $endgroup$



                            $newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
                            newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
                            newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
                            newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
                            newcommand{dd}{{rm d}}
                            newcommand{ds}[1]{displaystyle{#1}}
                            newcommand{expo}[1]{,{rm e}^{#1},}
                            newcommand{fermi}{,{rm f}}
                            newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
                            newcommand{half}{{1 over 2}}
                            newcommand{ic}{{rm i}}
                            newcommand{iff}{Longleftrightarrow}
                            newcommand{imp}{Longrightarrow}
                            newcommand{pars}[1]{left(, #1 ,right)}
                            newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
                            newcommand{pp}{{cal P}}
                            newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
                            newcommand{sech}{,{rm sech}}
                            newcommand{sgn}{,{rm sgn}}
                            newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
                            newcommand{ul}[1]{underline{#1}}
                            newcommand{verts}[1]{leftvert, #1 ,rightvert}$
                            begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                            =sum_{k = 0}^{n} overbrace{oint_{verts{z} = 1}%
                            {pars{1 + z}^{k} over z^{n - k + 1}},{dd z over 2piic}}
                            ^{ds{= color{#c00000}{k choose n - k}}}
                            \[5mm] = &
                            oint_{verts{z} = 1}{1 over z^{n + 1}}
                            sum_{k = 0}^{n}bracks{pars{1 + z}z}^{k}
                            ,{dd z over 2piic}
                            \[5mm]&=oint_{verts{z} = 1}{1 over z^{n + 1}}
                            {bracks{pars{1 + z}z}^{n + 1} - 1 over pars{1 + z}z - 1}
                            ,{dd z over 2piic}
                            \[5mm]&=oint_{verts{z} = 1}
                            {pars{1 + z}^{n + 1} over pars{z - r_{-}}pars{z - r_{+}}}
                            ,{dd z over 2piic}
                            \[2mm] &
                            -oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{z - r_{-}}pars{z - r_{+}}}
                            ,{dd z over 2piic}label{1}tag{1}
                            end{align}




                            where $ds{r_{mp} = {-1 mp root{5} over 2}}$ are the roots of
                            $ds{z^{2} + z - 1 = 0}$. $ds{r_{-} = -phi}$ and
                            $ds{r_{+} = phi - 1 = {1 over phi}}$.
                            $ds{phi equiv {1 + root{5} over 2}}$ is the Golden Ratio.




                            $$
                            mbox{Note that}quad
                            r_{-} < -1,,quad 0 < r_{+} < 1.,qquad r_{-}r_{+} = r_{-} + r_{+} = -1.quad
                            r_{+} - r_{-} = root{5}
                            $$




                            From expression eqref{1}:
                            begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                            \[5mm] = &
                            {pars{1 + r_{+}}^{n + 1} over r_{+} - r_{-}}
                            -{1 over r_{+} - r_{-}}oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{z - r_{+}}},{dd z over 2piic}
                            \&+
                            {1 over r_{+} - r_{-}}oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{z - r_{-}}},{dd z over 2piic}
                            \[5mm]&={phi^{n + 1} over root{5}}
                            -{1 over root{5}}color{#00f}{oint_{verts{z} = 1}
                            {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
                            \&-{1 over root{5}r_{-}}color{#c00000}{oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}label{2}tag{2}
                            end{align}




                            begin{align}&color{#00f}{oint_{verts{z} = 1}
                            {1 over z^{n + 2}pars{1 - r_{+}/z}},{dd z over 2piic}}
                            =sum_{k = 0}^{infty}r_{+}^{k}oint_{verts{z} = 1}
                            {1 over z^{n + 2 + k}},{dd z over 2piic}=color{#00f}{0}label{3}tag{3}
                            end{align}




                            begin{align}&color{#c00000}{oint_{verts{z} = 1}
                            {1 over z^{n + 1}pars{1 - z/r_{-}}},{dd z over 2piic}}
                            =sum_{k = 0}^{infty}{1 over r_{-}^{k}}oint_{verts{z} = 1}
                            {1 over z^{n + 1 - k}},{dd z over 2piic}={1 over r_{-}^{n}}
                            =color{#c00000}{{1 over pars{-phi}^{n}}}
                            label{4}tag{4}
                            end{align}




                            With eqref{2}, eqref{3} and eqref{4}:
                            begin{align}&color{#66f}{largesum_{k = 0}^{n}{k choose n - k}}
                            ={phi^{n + 1} over root{5}} - {1 over root{5}pars{-phi}},
                            {1 over pars{-phi}^{n}}
                            =color{#66f}{large{phi^{n + 1} + pars{-1}^{n}phi^{-n - 1} over root{5}}}
                            end{align}
                            which is the $ds{pars{n + 1}}$-Fibonacci Number.







                            share|cite|improve this answer














                            share|cite|improve this answer



                            share|cite|improve this answer








                            edited Jan 8 at 19:42

























                            answered Nov 6 '14 at 22:30









                            Felix MarinFelix Marin

                            67.4k7107141




                            67.4k7107141






























                                draft saved

                                draft discarded




















































                                Thanks for contributing an answer to Mathematics Stack Exchange!


                                • Please be sure to answer the question. Provide details and share your research!

                                But avoid …



                                • Asking for help, clarification, or responding to other answers.

                                • Making statements based on opinion; back them up with references or personal experience.


                                Use MathJax to format equations. MathJax reference.


                                To learn more, see our tips on writing great answers.




                                draft saved


                                draft discarded














                                StackExchange.ready(
                                function () {
                                StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1001040%2fa-closed-form-for-sum-of-binomial-coefficients%23new-answer', 'question_page');
                                }
                                );

                                Post as a guest















                                Required, but never shown





















































                                Required, but never shown














                                Required, but never shown












                                Required, but never shown







                                Required, but never shown

































                                Required, but never shown














                                Required, but never shown












                                Required, but never shown







                                Required, but never shown







                                -

                                Popular posts from this blog

                                1300-talet

                                Image
                                Den här artikeln handlar om hundraårsperioden 1300–1399. För decenniet 1300–1309, se 1300-talet (decennium). .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output ...
                                Read more

                                1300-talet

                                Image
                                Den här artikeln handlar om hundraårsperioden 1300–1399. För decenniet 1300–1309, se 1300-talet (decennium). .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output ...
                                Read more

                                Display a custom attribute below product name in the front-end Magento 1.9.3.8

                                Image
                                0 I need to display a custom attribute bellow the product name and I don't know how can I call this attribute. I am editing the file /app/design/frontend/templatemela/MAG100219_1/template/catalog/product/view.phtml But how can I call this attribute in php? I tried calling a string echo with the name I put in the attribute, but it didn't work. Code is as below: <div class="page-title product-title"> <h1><?php echo $_helper->productAttribute($_product, $_product->getName(), 'name') ?></h1> </div> <div class="codigoinmetro"> <h2><?php echo $_helper->productAttribute($_product, $_product->getName(), 'registroinmetro') ?></h2> </div> php attrib...
                                Read more