Proof By Induction: Sum of the Squares of Natural Numbers

I’ve delved deeply into divisiblity over the last few weeks, and am now examining properties of squares and sums of squares. I offer the following proof by induction (some algebraic manipulation is required as well).

It is known that the sum of the squares of the first n natural numbers is equal to

[( n )( n + 1 )( 2n + 1 )]/6

PROOF BY INDUCTION

Base cases: n = 1

[( 1 )( 1+1 )( 2(1)+1 )]/6 = [( 1 )( 2 )( 3 )]/6 = 6/6 = 1 = 12.

n = 2

[( 2 )( 2 + 1 )( 2(2) + 1 )]/6 = [( 2 )( 3 )( 5 )]/6 = 30/6 = 5 = 12 + 22.

Induction Hypothesis

[( k )( k + 1 )( 2k + 1 )]/6 = ( SUM from i = 0 to i = k of i2 )

Induction Step

(k + 1)2 + ( SUM from i = 0 to i = k of i2 ) = ( SUM from i = 0 to i = k + 1 of i2 )

RHS

( SUM from i = 0 to i = k + 1 of i2 ) = [( k + 1 )(( k + 1 ) + 1)( (2k + 1) + 1 )]/6

LHS

= ( k + 1 )2 + [( k )(k + 1 )( 2k + 1 )]/6

= [6( k + 1 )2 + ( k )(k + 1 )( 2k + 1 )]/6

= ( k + 1 )[6( k + 1 ) + k( 2k + 1 )]/6

= ( k + 1)[6k + 6 + 2k2 + k]/6

= (k + 1)[2k2 + 7k + 6]/6

= ( k + 1 )( k + 2 )( 2k + 3 )/6

= ( k + 1 ) (( k + 1) + 1)(( 2k + 1 ) + 1) /6 = RHS

Q.E.D.

I prefer proof by induction as it feels robust.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s