29Jun/0915

## Can you sum this?

Hi,

I've been playing with this series:

S

_{n}= 1x2^{2}+ 2x3^{2}+ 3x4^{2}+ ... + nx(n+1)^{2}

I've come up with a formula for determining S_{n} 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.

watchmathJune 29th, 2009 - 15:49

Well, if you know the formula of sigma i, sigma i^2 and sigma i^3 then you are done.

SolJune 29th, 2009 - 15:58

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.

JeffJune 29th, 2009 - 16:28

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

Rick ReganJune 29th, 2009 - 17:29

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).

JohnJune 29th, 2009 - 17:39

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.

Nemanja SkoricJune 29th, 2009 - 18:50

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

Nemanja SkoricJune 29th, 2009 - 18:58

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, “

Rick ReganJune 29th, 2009 - 20:41

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.)

Nikhil ChelliahJune 29th, 2009 - 22:13

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

.mau.June 30th, 2009 - 00:31

I stopped after noticing that the result was a quartic, I am lazy 🙂

HennoJune 30th, 2009 - 03:59

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.

watchmathJune 30th, 2009 - 07:34

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.

kiwiJune 30th, 2009 - 08:10

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.

Rick ReganJune 30th, 2009 - 10:44

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

SolJune 30th, 2009 - 17:21

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.