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

                                An IMO inspired problem

                                Image
                                14 4 This problem from IMO 1988 is said to be one of the most elegant ones in functional equations. Problem : The function $f$ is defined on the set of all positive integers as follows: begin{align} f(1) = 1, f(3) &= 3, f(2n) = f(n), \ f(4n+1) &= 2f(2n+1) - f(n), \ f(4n+3) &= 3 f(2n+1) - 2f(n) end{align} Find the number of $n$ with $f(n) = n, 1 leq n leq 1988$. The main idea towards the solution is realizing that these conditions stand for the fact that $f(n)$ just reverses the digits in the binary representation of the number $n$. So, essentially the solution is finding the number of binary pallindromes $leq 1988_{10}$. My question is the following : How to reformulate the problem so that $f(n)$ reverses the digits of $n$ in its ternary representation. Or even better, can we reformulate it for a
                                Read more

                                Management

                                Image
                                Management From Wikipedia, the free encyclopedia Jump to navigation Jump to search "Manager" redirects here. For other uses, see Management (disambiguation) and Manager (disambiguation). An organization chart for the United States Coast Guard shows the hierarchy of managerial roles in that organization. Business administration Management of a business Accounting Management accounting Financial accounting Financial audit Business entities Cooperative Corporation Limited liability company Partnership Sole proprietorship State-owned enterprise Corporate governance Annual general meeting Board of directors Supervisory board Advisory board Audit committee Corporate law Commercial law Constitutional documents Contract Corporate crime Corporate liability Insolvency law International trade law Mergers and acquisitions Economics Commodity Pu
                                Read more

                                Investment

                                Image
                                Investment From Wikipedia, the free encyclopedia Jump to navigation Jump to search This article is about investment in finance. For investment in macroeconomics, see Investment (macroeconomics). For other uses, see Investment (disambiguation). "Invest" redirects here. For the term in meteorology, see Invest (meteorology). This article needs additional citations for verification . Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. ( February 2017 ) (Learn how and when to remove this template message) In general, to invest is to distribute money in the expectation of some benefit in the future – for example, investment in durable goods, in real estate by the service industry, in factories for manufacturing, in product development, and in research and development. However, this article focuses specifically on investment in financial
                                Read more