Wild About Math! Making Math fun and accessible

29Jun/0915

Can you sum this?

Hi,

I've been playing with this series:

Sn = 1x22 + 2x32 + 3x42 + ... + nx(n+1)2

I've come up with a formula for determining Sn but I derived the formula in a fairly roundabout way.

I'm interested to know if someone has an elegant way to derive the formula.

Comments (15) Trackbacks (0)
  1. Well, if you know the formula of sigma i, sigma i^2 and sigma i^3 then you are done.

  2. Yup, you’re right. I used sigma i^2 and sigma i^3 in particular and I got a 4th degree polynomial that does factor nicely but it’s still a big beast of a formula so I’m interested to know if there’s an elegant way to solve this type of problem, maybe even without knowing the sums of powers formulas.

    I also wonder if this type of series is discussed in the literature somewhere.

  3. I’d just use the facts that

    nx(n+1)^2 = (n+1)^3 – (n+1)^2
    sigma (n+1)^3 = ((n+1)(n+2)/2)^2
    sigma (n+1)^2 = (n+1)(n+2)(2n+3)/6

    So, S_n = ((n+1)(n+2)/2)^2 – (n+1)(n+2)(2n+3)/6

  4. The only way I know how to do it is with the sigma formulas like watchmath suggested. Doing so I get (3n^4 + 14n^3 + 21n^2 + 10n)/12, or factored, n(n+1)(n+2)(3*n+5)/12 (I cheated on the factoring — I used a computer algebra system, PARI/GP).

  5. I recommend the book “Concrete Mathematics” by Ron Graham, Donald Knuth, and Oren Patashnik. They give about 10 different derivations for the sum of squares problem. When they introduce a new summation technique, they often use the sum of squares problem as one of the examples.

  6. It can be also solved by using antidifference operator.
    Here is the solution:

    Sn = Sum(1, n) [ n x (n+1)^2 ]
    Sn = Sum(1, n) n x (n+1) x (n+2) – Sum(1, n) n x (n+1)

    F_n(x) will mean falling factorial of x of degree n (http://en.wikipedia.org/wiki/Falling_factorial)

    So , Sn = Sum(1, n) F_3(n+2) – Sum(1, n) F_2(n+1)

    and we know that Sum(1,n) F_k(n) – F_k(1)= [F_k+1(n+1) / k+1] – F_k+1(1) / k+1, for k != -1 (That can be proved using antidifference operator)

    So we have that
    Sn = [F_4(n+3) / 4] – F_4(1) / 4 + [F_3(n+2) / 3] – F_3(1) / 3 = F_4(n+3) / 4 – F_3(n+2) / 3 = n(n+1)(n+2)(3*n+5)/12

  7. I made a mistake so I’m correcting myself :)

    Instead of
    “and we know that Sum(1,n) F_k(n) – F_k(1)= [F_k+1(n+1) / k+1] – F_k+1(1) / k+1, ”

    it should be
    “and we know that Sum(1,n) F_k(n) = [F_k+1(n+1) / k+1] – F_k+1(1) / k+1, “

  8. Just for fun I proved my formula n(n+1)(n+2)(3n+5)/12 by induction:

    n(n+1)(n+2)(3n+5)/12 + (n+1)(n+2)^2

    = (3n^4 + 14n^3 + 21n^2 + 10n)/12 + n^3 + 5n^2 + 8n + 4

    = (3n^4 + 14n^3 + 21n^2 + 10n + 12n^3 + 60n^2 + 96n + 48)/12

    = (3n^4 + 26n^3 + 81n^2 + 106n + 48)/12

    = (n+1)(n+2)(n+3)(3(n+1)+5)/12

    (Again, I cheated on the last step and used PARI/GP to factor.)

  9. I cheated and used a TI-83, knowing there the series would have a quartic regression.

    seq(X,X,1,10) -> List1
    List1 * (List1 + 1)² -> List2
    cumsum(List2) -> List3
    QuartReg List1,List3

    And it gave me the formula: ¹/₄ x⁴ + ⁷/₆ x³ + ⁷/₄ x² + ⁵/₆ x

  10. I stopped after noticing that the result was a quartic, I am lazy :-)

  11. Look at the book A = B which gives a way to derive a closed form for any sort of series like this. There is only a condition on the quotient of 2 succesive terms, IIRC. It can be downloaded at http://www.math.upenn.edu/~wilf/AeqB.html

    and explains the complete theory.

  12. I check the sequence on the encyclopaedia of integer sequence and there is some interesting interpretation of this number.
    The sequence gives us the number of non-square rectangles in an (n+1)x(n+1) square.

  13. No need to cheat on the factoring … don’t expand the common factor (n+1)(n+2) and all you’ll have to do is factor the remaining quadratic.

  14. kiwi — yes, easy shortcut that I missed. But I’m still inclined to cheat to factor the remaining 3n^2 + 17n + 24 :) .

  15. Wow! Amazing comments. I learned some new things from what you all wrote which will be good seeds for future articles. And, I will give you credit for each idea I use.

    John and Henno. Thanks for the book recommendations. I know about the Concrete Mathematics book as I took that course from Knuth himself, I believe before the book was published. It was a tough course!

    I’m still wondering if there’s a visual demonstration that makes the sum easy to see. I actually saw a “proof without words” once for the sum of squares of consecutive integers. It was a rectangular solid with sides n, n+1, and 2n+1 carved up in such a way that one could see that the sum of the squares was 1/6th of the volume of the solid. If I can dig it up I’ll scan and post the picture.


Leave a comment

No trackbacks yet.