Fundamentals of Algorithms Homework 0 DUE August 24, 2010 4pm


1. Use proof by induction to show that 1^2 + 2^2 + 3^2 + ...+ n^2 = 1/6(n)(n+1)(2n+1) (100 points)

SOLUTION:

Base Case : n =1;
1^2 = (1/6) (1) (2) (3)

Inductive Hypothesis: n = k;

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

To Show : n = k + 1;

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

Starting from the IH:

1^2 +  2^2 +  3^2  .... k^2 = (1/6) (k) (k+1) (2k+1) (IH)

1^2 +  2^2 +  3^2  .... k^2 + ( k+1)^2 = (1/6) (k) (k+1) (2k+1) + (k + 1)^2 (adding (k+1)^2 to both sides)
					    = (k+1)[(1/6)k(2k+1) + k + 1] (factoring k+1)

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

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

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

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