Let P(n) be the statement that 1^2 +2^2 +···+n^2 = n(n + 1)(2n + 1)/6 for the positive integer n.

Table of Contents

• a) What is the statement P(1)?
• b) Show that P (1) is true, completing the basis step of the proof
• c) What is the inductive hypothesis?
• d) What do you need to prove in the inductive step?
• e) Complete the inductive step, identifying where you use the inductive hypothesis
• f) Explain why these steps show that this formula is true whenever n is a positive integer

PRINCIPLE OF MATHEMATICAL INDUCTION: “To prove that P(n) is true for all positive integers n, where P (n) is a propositional function, we complete two steps: BASIS STEP: We verify that P (1) is true. INDUCTIVE STEP: We show that the conditional statement P (k) → P (k + 1) is true for all positive integers k.” Source: Discrete Mathematics and its Applications by Rosen.

a) What is the statement P(1)?

1² = 1(1+1)(2×1+1)/6=1x2x3/6

b) Show that P (1) is true, completing the basis step of the proof

1² = 1(1+1)(2×1+1)/6=1x2x3/6=6/6=1

Both sides of the equation are equal.

c) What is the inductive hypothesis?

P(k): 1² +2² +···+k² = k(k+1)(2k+1)/6

d) What do you need to prove in the inductive step?

In the inductive step, we need to prove that P(k)->P(k+1) for k≥1.

P(k+1)= 1² +2² +···+k² +(k+1)² =(k+1)(k+2)(2k+3)/6

e) Complete the inductive step, identifying where you use the inductive hypothesis

P(k+1): (1² +2² +···+k²)+(k+1)² , substituting P(k), we get,

= [k(k + 1)(2k+ 1)/6] + (k + 1)², by using (k+1)/6 as common factors between the two terms, we get,

=[(k + 1)/6] [k(2k + 1) + 6(k+ 1)] , multiplying in [k(2k + 1) + 6(k+ 1)], we get

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

= [(k+1)/6](2k² +7k+6), factorizing the second term we get,

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

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

f) Explain why these steps show that this formula is true whenever n is a positive integer

These steps show that the formula is true for all n≥0 because we applied the principle of mathematical induction, by completing the basis step and inductive step.

Related exercises:

• a) Find a formula for 1/2 + 1/4 + 1/8 + … + 1/2^n by examining the values of this expression for small values of n. b) Prove the formula you conjectured in part (a).
• Prove that 3+3 · 5+3 · 52+···+3 · 5^n=3(5^(n+1)−1)/4 whenever n is a nonnegative integer
• There are infinitely many stations on a train route. Suppose that the train stops at the first station and suppose that if the train stops at a station, then it stops at the next station. Show that the train stops at all stations