Question

Give a Proof by Induction that the sum of squares of first n natural numbers is n. (n+1). (2n + 1) / 6.

Answer 1

Suppose S(n) represents the sum of squares of first n natural numbers.

Our hypothesis is that S(n) = n (n+1) (2n + 1) / 6.

To prove this hypothesis (and thereby convert into a theorem), let us use principle of mathematical induction.

Base Case

S(1) = 1^2 = 1,   Also, 1 * (1+1) * 3 / 6.  Therefore, Base Case is satisfied.

Induction Hypothesis

Let us suppose the hypothesis is true for all values of n < m.

Inductive Step  [Here, we should P(n | n < m) => P(m).]

Let us evaluate S(m).  By definition, S(m) = S(m -1) + m^2.

By induction hypothesis, S(m-1) = (m-1) * (m - 1 + 1) * (2(m-1) +1) / 6.   This can be used by us, since induction hypothesis allows us to assume hypothesis is true for all values of n < m, and therefore, specifically that it is true for n = m-1.

Therefore, we have 

S(m) = (m - 1) * (m) * (2m - 1) / 6 + m^2.   By rearranging terms, we get:

S(m) = m/6 {(m - 1) (2m - 1)  + 6m}.

That is, 

S(m) = m/6 {2m^2 - 2m - m + 1 + 6m}

S(m) = m/6 {2m^2 + 3m + 1}

S(m) = m/6 (m+1) (2m + 1)

Therefore, the hypothesis is true for m.

Since Induction base is satisfied, and induction step is satisfied, therefore, by PMI, hypothesis is true for all values of n >= 1.

Therefore, we have: 

S(n) = n (n+1) (2n + 1) / 6.

Answer 2

Let, S(n) represents the sum of squares of first n natural numbers.

Hypothesis : S(n) = n (n+1) (2n + 1) / 6.

Using mathematical induction:

Base Case

S(1) = 1^2 = 1,   Also, 1 * (1+1) * 3 / 6.  Therefore, Base Case is satisfied.

Induction Hypothesis

Let us suppose the hypothesis is true for all values of n < m.

Inductive Step  [Here, we should P(n | n < m) => P(m).]

Let us evaluate S(m).  By definition, S(m) = S(m -1) + m^2.

By induction hypothesis, S(m-1) = (m-1) * (m - 1 + 1) * (2(m-1) +1) / 6.   This can be used by us, since induction hypothesis allows us to assume hypothesis is true for all values of n < m, and therefore, specifically that it is true for n = m-1.

Therefore, we have

S(m) = (m - 1) * (m) * (2m - 1) / 6 + m^2.   By rearranging terms, we get:

S(m) = m/6 {(m - 1) (2m - 1)  + 6m}.

That is,

S(m) = m/6 {2m^2 - 2m - m + 1 + 6m}

S(m) = m/6 {2m^2 + 3m + 1}

S(m) = m/6 (m+1) (2m + 1)

Therefore, the hypothesis is true for m.

Since Induction base is satisfied, and induction step is satisfied, therefore, by PMI, hypothesis is true for all values of n >= 1.

Therefore, we have:

S(n) = n (n+1) (2n + 1) / 6.