Suppose you want to find the sum of the squares of all integers from 1 up to 200. Doing it manually would be boring a take a lot of time. Instead you can use the formula below:
S = 1/6 * n * (n + 1) * (2n + 1)
So in our case the answer would be 2,686,700
I am not sure how to derive this formula, cause I found it on a book that didn’t explain where it comes from, but once I find it I’ll update this post.
You can derive the formula like this:
Make the assumption, that
sum of squares from 1 to n = f(n) where f(n) = a*n^3+b*n^2+c*n+d
Then you plug in for n the values 1,2,3,4 and for f(n) the values 1,5,14,30 respectively.
What you get is a linear equation in the unknown a,b,c,d:
A * x = b
where x = (a,b,c,d) transposed
A = (1,1,1,1; 8,4,2,1; 27, 9,3,1;64,16,4,1)
and b = (1,5,14,30)
Then you solve the linear system for x and get:
x = A^(-1) * b = (1/3; 1/2; 1/6; 0)
Which is what we want.
Of course this does not proof the formula, but it is a derivation.
Now that you know what to proof, you can use induction on n to get a formal proof.
Notice, that this method of derivation works also with higher powers then two.
For instance you can try to derive
sum of cubes.
Notice also, that A is a so called Vandermode-Matrix.
The derivation is simple really…
The formula is actually the closed form solution of the following recurrence relation:
S(n)=n^2 + S(n-1) ; S(1)=1
which can be solved easily using Z-transform or any other common method…