News:

Facebook killed the radio star. And by radio star, I mean the premise of distributed forums around the internet. And that got got by Instagram/SnapChat. And that got got by TikTok. Where the fuck is the internet we once knew?

Main Menu

Sum of Squares & Hockey Stick Identity

Started by Ender, July 21, 2007, 02:28:20 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Ender

Problem:

Read http://ptri1.tripod.com/

And then prove the sum of squares formula, i.e.

1 + 2^2 + 3^2 + ... + n^2 = n(n+1)(2n+1)/6

by use of the Hockey Stick Identity (an important combinatorics identity which is explained in that link).

EDIT: Deriving the sum of squares formula by finite differences takes awhile and is thus annoying. For instance, to do it by finite differences you have to first make a large-enough table, then you have to establish the order of the polynomial, and then you have to solve a 3x4 augmented matrix. But deriving it with the Hockey Stick Identity only takes like a minute (once you know how to do it). So knowing how to derive it with the Hockey Stick identity allows you to derive it quickly :P

Ender

Hint: Look at a picture of Pascal's triangle for like 5-7 rows and consider the diagonal of triangular numbers. Note that the sum of two triangular numbers is a perfect square, e.g. 1 + 3 = 4.