Can you sum this?
June 29th, 2009 | by Sol |Hi,
I’ve been playing with this series:
Sn = 1×22 + 2×32 + 3×42 + … + 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.
If you enjoyed this post, make sure you subscribe to my RSS feed!
15 Responses to “Can you sum this?”
By watchmath on Jun 29, 2009 | Reply
Well, if you know the formula of sigma i, sigma i^2 and sigma i^3 then you are done.
By Sol on Jun 29, 2009 | Reply
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.
By Jeff on Jun 29, 2009 | Reply
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
By Rick Regan on Jun 29, 2009 | Reply
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).
By John on Jun 29, 2009 | Reply
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.
By Nemanja Skoric on Jun 29, 2009 | Reply
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
By Nemanja Skoric on Jun 29, 2009 | Reply
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, “
By Rick Regan on Jun 29, 2009 | Reply
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.)
By Nikhil Chelliah on Jun 29, 2009 | Reply
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
By .mau. on Jun 30, 2009 | Reply
I stopped after noticing that the result was a quartic, I am lazy
By Henno on Jun 30, 2009 | Reply
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.
By watchmath on Jun 30, 2009 | Reply
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.
By kiwi on Jun 30, 2009 | Reply
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.
By Rick Regan on Jun 30, 2009 | Reply
kiwi — yes, easy shortcut that I missed. But I’m still inclined to cheat to factor the remaining 3n^2 + 17n + 24
.
By Sol on Jun 30, 2009 | Reply
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.