To start this proof you will need to find an expression for the sum of all integers. Using a similar method to one worked out by Guass we can then adapt this (and then use this proven result) to go further and find the sum of squares. Thus the proof comes in two parts...

Proof 1: The Sum Of Integers

Let S = 1 + 2 + 3 + 4 + ... + (k-1) + k

Start with the following:

(n+1)^2 = n^2 + 2n + 1

This implies that:

(n+1)^2 – n^2 = 2n + 1

Now write the following list, one for each value of n from n=1 to n=k.

2^2 – 1^2 = 2*1 + 1
3^2 – 2^2 = 2*2 + 1
4^2 - 3^2 = 2*3 + 1
...
(k-1)^2 - (k-2)^2 = 2*(k-2) + 1
(k)^2 - (k-1)^2 = 2*(k-1) + 1
(k+1)^2 - (k)^2 = 2*k + 1

Add both sides of the above list, noticing that many of the terms on the left hand side cancel out. The only terms that do not cancel from the left hand side are (k+1)^2 and -1^2.

On the other side, there are k lots of 1 and 2 multiplied by the sum (1 + 2 + 3 + ...) or rather S. When we add all these equations together, we obtain:

(k+1)^2 - 1^2 = 2S + k

Rearranging:

(k+1)^2 - 1^2 = 2S + k

(k+1)^2 - 1 - k = 2S

(k+1)^2 - (k+1) = 2S

(k+1)(k+1)-(k+1) = 2S

(k+1)((k+1)-1) = 2S

(k+1)(k) = 2S

Thus S = (k(k+1))/2

We have thus arrived at the required result.

Proof 2: The Sum Of The Integers Squared

Let T = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + ... + (n-2)^2 + (n-1)^2 + (n)^2

Let's start out by looking at the formula for the cubic equation:

(n+1)^3 = n^3 + 3n^2 + 3n + 1

Rearrange:

(n+1)^3 - (n^3) = 3n^2 + 3n + 1

Now substituting n=1 to n=k, we have:

2^3 - 1^3 = 3*1^2 + 3*1 + 1
3^3 - 2^3 = 3*2^2 + 3*2 + 1
4^3 - 3^3 = 3*3^2 + 3*3 + 1
5^3 - 4^3 = 3*4^2 + 3*4 + 1
...
k^3 - (k-1)^3 = 3*(k-1)^2 + 3*(k-1) + 1
(k+1)^3 - (k)^3 = 3*(k)^2 + 3*(k) + 1

Now let's sum the two sides vertically...

LHS:

Compare each row with the next and you will notice that the first term in one row is subtracted in the next row (eg most of the terms cancel each other out). There are only two terms which cannot be cancelled, namely:

(k+1)^3 - 1^3

RHS:

Starting from the right-hand side of this equation...

How many 1s? Answer: k
The next term in each line is 3 times the sum of integers.
The first term in each line is 3 times the sum of squares (eg what we are trying to work out).

Thus adding all these terms together gives:

(k+1)^3 - 1^3 = 3T + 3S + k*1

Now all we have to do is rearrange:

(k+1)^3 - 1 - k = 3T + 3S

Multiply by 2,

2(k+1)^3 - 2(k+1) = 6T + 3k(k+1)

Subtract 3k(k+1) from each side,

2(k+1)^3 - 2(k+1) - 3k(k+1) = 6T

Take (k+1) outside the bracket,

(k+1)(2*(k+1)^2 - 2 - 3k) = 6T

Rearrange,

(k+1)(2*(k^2 + 2k + 1) - 2 - 3k) = 6T

Simplify,

(k+1)(2k^2 + 4k + 2 - 2 - 3k) = 6T

(k+1)(2k^2 + k) = 6T

Take k outside the bracket,

k(k+1)(2k+1) = 6T

Thus, T = k(k+1)(2k+1)/6 which is the desired result.

No sir, I don't think anyone can prove it without induction in disguise.

The left hand side is the function f(n) satisfying
f(0)=0 and f(n)-f(n-1)=n^2. This is induction.

To prove the formula just show that the right hand side also satisfies these two conditions.

Why avoid induction? It is a marvelous tool.