Author |
Topic: Sum of Odd and Even Squares (Read 3696 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
Sum of Odd and Even Squares
« on: Jan 15th, 2005, 4:53pm » |
 Quote  Modify
|
Does anyone know how to prove, by deduction, that the sum of the first k odd squares is k(4k2-1)/3=k(2k+1)(2k-1)/3?
What about the first k even squares, 2k(2k+1)(k+1)/3?
Rather interestingly, I believe that the last formula corresponds to the number of moves a bishop can make on a (k+1) square board. For example, on a 4x4 board (k=3):
From any corner square there are 3 squares it can move to on the diagonal (4*3=12).
From each edge square there are 3 squares it can move to (8*3=24).
From each of the four centre squares there are 5 square to move to (4*5=20).
So there are 12+24+20=56 moves, and 2*3*7*4/3=56.
|
|
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Sum of Odd and Even Squares
« Reply #1 on: Jan 15th, 2005, 7:56pm » |
Quote Modify
|
Variation on the following can also be used sum of any Nth powers. I have often thought there must be a better way, since these sums always seem to result in a nicely factored polynomial but this method leaves the factoring up to you.
To find sum of first k squares, start with sum of cubes:
[sum]i=1k (i3) = [sum]i=2k+1 ((i-1)3) = [sum]i=2k+1 (i3-3i2+3i-1)
Subtract [sum]i=1k (i3) and you get
0 = (k+1)3 -1 + [sum]i=2k+1 (-3i2+3i-1)
Being careful about the limits on the summations, you can then arrange into formula for sum of the first k squares (you will need to use the formula for [sum] i ).
Multiply sum of the first k squares by 4 for sum of first k even numbers. Subtract sum of first k evens from sum of first 2k integers for sum of first k odds.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum of Odd and Even Squares
« Reply #2 on: Jan 16th, 2005, 5:05am » |
Quote Modify
|
on Jan 15th, 2005, 7:56pm, SWF wrote:| Multiply sum of the first k squares by 4 for sum of first k even numbers. |
|
Duh! 
Thanks, SWF.
I too wish there was a better way to find the sum of Nth powers in general. Similar to your method, I like to employ the telescoping principle. In fact I use it in one of the FAQs on my website: Sum of Square.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sum of Odd and Even Squares
« Reply #3 on: Jan 16th, 2005, 7:18am » |
Quote Modify
|
Something else you can use to find the sum of squares (or higher powers)
[sum]nz=1[sum]zy=1..(p times)..[sum]kj=1[sum]ji=1 [ i ] = (n+p-1)!/[p! (n-1)!]
[sum]nj=1[sum]ji=1[ i ] = [sum] [ j2/2 + j/2 ] = n(n+1)(n+2)/6
[sum] j2 = n(n+1)(n+2)/3 - [sum] j
[sum] j2 = n(n+1)(n+2)/3 - n(n+1)/2
[sum] j2 = n(n+1)(2n+1)/6
I'm not sure what will be easier to work out for higher powers though..
[edit]fixed sign-typo[/edit]
|
| « Last Edit: Jan 16th, 2005, 2:38pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum of Odd and Even Squares
« Reply #4 on: Jan 16th, 2005, 11:23am » |
Quote Modify
|
Let S(k) be the sum of the first k squares, and O(k) the sume of the first k odd squares, then O(k) = S(2k) - 4S(k).
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Sum of Odd and Even Squares
« Reply #6 on: Jan 16th, 2005, 2:31pm » |
Quote Modify
|
Thanks for your support, towr. For that I will not check on the accuracy of your formula for [sum] j2.
If you already know the formula for sum of squares, another even more straightforward way is to get sum of odd from [sum] (2*i-1)2. Just expand it and use formulas for sum of squares and [sum] i
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum of Odd and Even Squares
« Reply #8 on: Jan 17th, 2005, 9:11am » |
Quote Modify
|
Sorry, SWF, I didn’t read your post carefully. 
Here’s a nice way to derive a formula for a sum of the first k squares.
1
1 2 1
1 2 3 2 1
1 2 3 4 3 2 1
1 2 3 4 5 4 3 2 1
1 2 3 4 5 5 4 3 2 1
2 3 4 5 5 4 3 2
3 4 5 5 4 3
4 5 5 4
5 5
The illustration is for k=5. There are 11=2k+1 columns, each containing the number 15=k(k+1)/2. Five rows above the line add up to the sum of 5=k squares, as is each of the triangles below the line. Therefore, the sought sum is k(k+1)(2k+1)/6.
|
| « Last Edit: Jan 17th, 2005, 9:11am by Barukh » |
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum of Odd and Even Squares
« Reply #9 on: Jan 17th, 2005, 9:51am » |
Quote Modify
|
That is absolutely superb, Barukh! Is it your own discovery? If not, where did you see it?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum of Odd and Even Squares
« Reply #10 on: Jan 17th, 2005, 9:56am » |
Quote Modify
|
on Jan 17th, 2005, 9:51am, Sir Col wrote:| Is it your own discovery? |
|
Of course, not.
Quote:| If not, where did you see it? |
|
Conway & Guy. "The Book of Numbers", p. 49.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum of Odd and Even Squares
« Reply #11 on: Jan 17th, 2005, 12:21pm » |
Quote Modify
|
In general, if you want to compute the sum of the first n p-th powers without recursively working out 1,2,...,(p-1) first, you can do the following:
Let S(n) = Sp(n) = 1p + . . . + np.
S(n+1) - S(n) = (n+1)p, which tells you S(n) is a polynomial of degree p+1, say
S(n) = a1n + . . . + ap+1np+1,
as the constant term is clearly 0. Now the equation
[sum] ar(n+1)r = S(n+1) = S(n)+(n+1)p = [sum] arnr + (n+1)p
can be readily solved by equating coefficients, as the resulting system of linear equations is upper triangular.
Looking at the coefficient of nk,
[sum]r=kp+1 ar rCk = ak + pCk,
which gives the recursive formula
ak = 1/k (pCk-1 - [sum]r=k+1p+1 ar rCk-1)
Unfortunately Sp(n) doesn't seem to factor completely over [bbq] for p>3.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sum of Odd and Even Squares
« Reply #12 on: Jan 17th, 2005, 12:36pm » |
Quote Modify
|
on Jan 17th, 2005, 12:21pm, Eigenray wrote:S(n) is a polynomial of degree p+1, say
S(n) = a1n + . . . + ap+1np+1,
|
|
Interestingly, ap is independent of p (is 1/2).
|
| « Last Edit: Jan 17th, 2005, 12:38pm by Aryabhatta » |
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
Looking at the formula implies it might be possible to cut a n by (n+1) by (2n+1) brick into six identical shapes, each containing S(n) unit cubes. Trying it out shows that it can be done:
Start with a pyramid containing S(n) cubes as shown at lower left below in the green and yellow pyramid. Bottom layer is an n by n square, next layer up is (n-1) by (n-1) and so on (for the figure n=3).
Three of these pyramids can be arranged as shown in the red yellow and blue central figure. (Projections are show to demonstrate what the hidden faces look like.) This is an n by n by (n+1) block with a yellow staircase protruding. Another one of these three pyramid blocks will fit with the staircases interlocking to give a n by (n+1) by (2n+1) block made up of six pyramids. Thus S=n*(n+1)*(2n+1)/6.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
