My Math Forum  

Go Back   My Math Forum > High School Math Forum > Pre-Calculus

Pre-Calculus Pre-Calculus Math Forum


Thanks Tree2Thanks
Reply
 
LinkBack Thread Tools Display Modes
August 14th, 2014, 06:50 PM   #1
Senior Member
 
Mr Davis 97's Avatar
 
Joined: Feb 2014
From: Louisiana

Posts: 156
Thanks: 6

Math Focus: algebra and the calculus
Deriving the formula for summing a sequence of squares

If we have the sequence $\displaystyle 1^{2}, 2^{2}, 3^{2}, 4^{2},\cdots n^{2}$, how do we derive $\displaystyle \sum_{k = 1}^{n}k^{2}$ for any positive integer $\displaystyle n$?
Mr Davis 97 is offline  
 
August 14th, 2014, 07:01 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
The general solution for this problem is complex and involves Bernoulli numbers. But if you know that the sum of an n-th degree polynomial is an (n+1)-th degree polynomial, you can do a simple curve fit through the points (0, 0), (1, 1), and (2, 5).
CRGreathouse is offline  
August 14th, 2014, 07:09 PM   #3
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,094
Thanks: 2360

Math Focus: Mainly analysis and algebra
Hi Mr. Davis,

I think you posted a question on sequences for which the answer was $n(n+1)$. The method of differences that I used there will serve you well here too.
v8archie is offline  
August 14th, 2014, 08:38 PM   #4
Senior Member
 
Joined: Sep 2012
From: British Columbia, Canada

Posts: 764
Thanks: 53

Before you post a question, take some time to search for it, in case it was already answered. In this case, WikiProof gives a nice proof of it.
eddybob123 is offline  
August 14th, 2014, 09:39 PM   #5
Banned Camp
 
Joined: Jun 2014
From: Earth

Posts: 945
Thanks: 191

Quote:
Originally Posted by CRGreathouse View Post
But if you know that the sum of an n-th degree polynomial is an (n+1)-th degree polynomial,
you can do a simple curve fit through the points (0, 0), (1, 1),
and (2, 5). $\displaystyle \ \ \ \ $ <----- Did you mean (2, 4)?
But the third degree polynomial will require four different points for curve-fitting.
Math Message Board tutor is offline  
August 14th, 2014, 09:53 PM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
I did not mean (2, 4), I meant (2, 5). But you're right, you need another point. Take (3, 14).
CRGreathouse is offline  
August 14th, 2014, 11:01 PM   #7
Banned Camp
 
Joined: Jun 2014
From: Earth

Posts: 945
Thanks: 191

Quote:
Originally Posted by CRGreathouse View Post
I did not mean (2, 4), I meant (2, 5).

But you're right, you need another point. Take (3, 14).
I asked about (2, 4), because the OP's question deals with the sum of squares.

In keeping with that, I expected you to give (0, 0), (1, 1), (2, 4), ...
Math Message Board tutor is offline  
August 15th, 2014, 04:29 AM   #8
Math Team
 
Joined: Apr 2010

Posts: 2,778
Thanks: 361

The question is indeed about the sum of the (first lowest) n squares, which are
$\displaystyle 0, 1^2 = 1, 1^2 + 2^2 = 5, 1^2 + 2^2 + 3^2 = 14,...$.

To find them for some n I'd write $\displaystyle k^2 = 2 \cdot {k \choose 2} + {k \choose 1}$ and then $\displaystyle \sum_{k=1}^{n}k^2 = \sum_{k=1}^{n}\left(2 \cdot {k \choose 2} + {k \choose 1}\right) = 2 \cdot {n+1 \choose 3} + {n+1 \choose 2}$
Hoempa is offline  
August 15th, 2014, 04:22 PM   #9
Global Moderator
 
Joined: Dec 2006

Posts: 18,250
Thanks: 1439

$\displaystyle \text{As }6k^2 \equiv 2(k^3 - (k - 1)^3) + 3(k^2 - (k - 1)^2) + 1,$

$\displaystyle 6\sum_{k=1}^n k^2 = \sum_{k=1}^n (2(k^3 - (k - 1)^3) + 3(k^2 - (k - 1)^2) + 1) = 2n^3 + 3n^2 + n = n(n + 1)(2n + 1).$
skipjack is offline  
August 16th, 2014, 06:02 PM   #10
Math Team
 
Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 407

Hello, Mr Davis 97!

I'll show you a very primitive solution to this problem.


Quote:
If we have the sequence $\displaystyle 1^2, 2^2, 3^2, 4^2,\cdots n^2$,
how do we derive $\displaystyle \sum_{k = 1}^{n}k^{2}$ for any positive integer $\displaystyle n$?

We have: $\:S_n \;=\;1^2+2^2+3^2+4^2+\cdots + n^2$

Crank out the first few partial sums.

$\qquad\begin{array}{ccccccc}S_1 &=& 1^2 &=& 1 \\
S_2 &=& 1^2+2^2 &=& 5 \\\
S_3 &=& 1^2+2^2+3^2 &=& 14 \\
S_4 &=& 1^2+2^2+3^2+4^2 &=& 30 \\
S_5 &=& 1^2+2^3+3^2+4^2+5^2 &=& 55 \end{array}$

Take the differences of consecutive terms,
$\quad$then take the differences of the differences, and so on.

$\begin{array}{c|ccccccccccc} S_n & 1 && 5 && 14 && 30 && 55 && 91 \\ \hline
\text{1st diff} && 4 && 9 && 16 && 25 && 36 \\
\text{2nd diff} &&& 5 && 7 && 9 && 11 \\
\text{3rd diff} &&&& 2 && 2 && 2 \end{array}$

The 3rd differences are constant.
Hence, the generating function is of the 3rd degree (a cubic).

The general cubic is: $\:f(n) \:=\:an^3 + bn^2 + cn + d$


Use the first four values from our list:

$\quad \begin{array}{ccccc}f(1) \:=\:1\!: & a + b + c + d &=& 1 \\
f(2) \:=\:5\!: & 8a + 4b + 2c + d &=& 5 \\
f(3) \:=\:14\!: & 27a + 9b + 3c + d &=& 14 \\
f(4)\:=\:30\!: & 64a + 16b + 4c + d &=& 30 \end{array}$

Solve the system: $\:a = \frac{1}{3},\;b = \frac{1}{2},\;c = \frac{1}{6},\;d = 0$

Hence: $\:f(n) \;=\;\frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n \;=\;\frac{1}{6}n(2n^2 + 3n + 1) $

Therefore: $\displaystyle\:\sum^n_{k=1} k^2 \;=\;\frac{n(n+1)(2n+1)}{6}$

soroban is offline  
Reply

  My Math Forum > High School Math Forum > Pre-Calculus

Tags
deriving, formula, sequence, squares, summing



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
finitely many squares sequence James1973 Number Theory 1 November 3rd, 2013 08:30 AM
Help deriving this Bessel function formula alan0354 Applied Math 18 July 27th, 2013 02:02 PM
Show that the sequence does not contain any squares maximus101 Number Theory 1 October 23rd, 2012 09:35 PM
Deriving a closed newton-cotes formula for n = 3 Laurier FMATH BBA Applied Math 1 November 10th, 2011 02:24 PM
Deriving formula from tree diagram? Wevans2303 Advanced Statistics 0 October 30th, 2011 02:07 PM





Copyright © 2017 My Math Forum. All rights reserved.