Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics - Sum of series

  1. Oct 12, 2010 #1
    1. The problem statement, all variables and given/known data

    Sum the series [tex]1^2+2^2+\cdots|n^2[/tex] by observing that [tex]m^2=2* \dbinom{m}{2} + \dbinom{m}{1}[/tex] and using the identity [tex] \dbinom{0}{k}+ \dbinom{1}{k} + \cdots+ \dbinom{m}{k}= \dbinom{m+1}{k+1}[/tex].

    2. Relevant equations



    3. The attempt at a solution

    I know that [tex]1^2+2^2+\cdots+m^2= 2* \dbinom{1}{2}+ \dbinom{1}{1} + 2* \dbinom{2}{2}+ \dbinom{2}{1} + 2* \dbinom{3}{2} + \dbinom{3}{1} + \cdots + 2* \dbinom{m}{2} + \dbinom{m}{1}[/tex] but I am not picking up on how to simply this into the sum of the whole series.
     
  2. jcsd
  3. Oct 12, 2010 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Try collecting terms so you have 2*(stuff) + (everything else).
     
  4. Oct 12, 2010 #3
    Re: Combinatorics - Sum of series ii

    OK, that gives me [tex] 2(\dbinom{1}{2}+\dbinom{2}{2}+...+\dbinom{n}{2})+(1+2+...+n) [/tex] , but I'm still not seeing it.
     
  5. Oct 12, 2010 #4
    OK, wait... The above equals [tex]2(\dbinom{1}{2}+ \dbinom{2}{2} +...+ \dbinom{n}{2})+(n(n+1))/2[/tex], so that lets me eliminate the 2's. Now I need to be able to combine the other two parts. Right?
     
  6. Oct 12, 2010 #5
    And [tex] \dbinom{n}{n}=\frac{1}{6}(n-2)(n-1)n = \frac{1}{6}(n^5-2n^4-n^3+2n^2)[/tex]. I don't know quite what I was expecting but that isn't it.
     
  7. Oct 12, 2010 #6
    And [tex] \dbinom{n}{n}=\frac{1}{6}(n-2)(n-1)n = \frac{1}{6}(n^5-2n^4-n^3+2n^2)[/tex] is what I meant to say.
     
  8. Oct 12, 2010 #7

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Did you use the identity you were given?
     
  9. Oct 12, 2010 #8

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    I don't see where you got this from. It can't be right because C(n,n)=1.
     
  10. Oct 12, 2010 #9
    No. Hmmm... So I would have [tex] \frac{(n-2)(n-1)n}{6}+ \dbinom{m+1}{k+1}[/tex]. And that equals [tex]\dbinom{m}{3}+ \dbinom{m+1}{k+1}[/tex].
     
  11. Oct 12, 2010 #10

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    What are m and k equal to? Where did the (n-2)(n-1)n/6 come from? Where did n(n+1)/2 go to?
     
  12. Oct 13, 2010 #11
    (n-2)(n-1)n/6 is the same as n falling power 3/3!, right? So that =[tex]\dbinom{m}{3}[/tex] So that would equal [tex]\dbinom{n}{3}+\dbinom{n+1}{k+1} [/tex]. Sorry, I mixed my m's and n's.
     
  13. Oct 13, 2010 #12

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    This is what I'm getting from what you wrote:

    [tex]\frac{(n-2)(n-1)n}{6} = \dbinom{n}{3} = \dbinom{m}{3} = \dbinom{n}{3}+\dbinom{n+1}{k+1}[/tex]

    You have an expression in terms of n and then you're saying it's equal to something in terms of m. Where did the m come from? Then you get another expression and yet another variable appears. Where did k come from? And how is this related to the original problem?
     
  14. Oct 13, 2010 #13
    Good grief... I am so sorry. This should read [tex]\frac{(n-2)(n-1)n}{6}= \dbinom{n}{3}+ \dbinom{n+1}{k+1}[/tex]. The k comes from the identity stated in the original problem.
     
  15. Oct 13, 2010 #14

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Let's go back to posts #3 and #4. You had

    [tex]\begin{align*}
    1^2+2^2+\cdots+n^2 &= 2\left[\dbinom{1}{2}+ \dbinom{2}{2} +...+ \dbinom{n}{2}\right]+(1+2+\cdots+n) \\
    &= 2\left[\dbinom{1}{2}+ \dbinom{2}{2} +...+ \dbinom{n}{2}\right]+\frac{n(n+1)}{2}
    \end{align*}[/tex]

    So far, so good. Now if you compare what's in the square brackets with the identity

    [tex]\dbinom{0}{k}+ \dbinom{1}{k} + \cdots + \dbinom{m}{k} = \dbinom{m+1}{k+1}[/tex]

    they look very similar. The first term of the lefthand side of the identity is always equal to 0, so it doesn't really matter if it's there or not. If you drop it, what's left and what's in the square brackets will match exactly if you choose the right values of m and k. What should m and k equal, possibly in terms of n?
     
  16. Oct 13, 2010 #15
    Yes, they do look very similar. I understand that I can eliminate the first term with no consequences. So... It seems that k has to be 2. I don't know how to say that in terms of n. m, on the other hand, would be n-1, wouldn't it?
     
  17. Oct 13, 2010 #16

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    k is indeed equal to 2. To see what m equals, look at the very last terms. In order for them to match exactly, you need m=n.
     
  18. Oct 13, 2010 #17
    So, in fact, I end up with [tex] \dbinom{n+1}{2} + \frac{n(n+1)}{2}[/tex]?
     
  19. Oct 13, 2010 #18

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Almost. Since k=2, you should have

    [tex]\dbinom{n+1}{3}+\frac{n(n+1)}{2}[/tex]
     
  20. Oct 14, 2010 #19
    Thank you so much for sticking this out with me! I have learned SO much from these posts; it's not just an answer to me. Thank you.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook