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

/ Mathematical Induction / By

Table of Contents

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.

Let P(n) be the statement that 13 +23 +···+n3 = (n(n + 1)/2)2 for the positive integer n,

a) What is the statement P(1)?

13=(1(1 + 1)/2)2

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

13=1

(1(1 + 1)/2)2=(1×2/2)2=(2/2)2=12=1

This proves the basis step.

c) What is the inductive hypothesis?

P(k): 13 +23 +···+k3 = (k(k + 1)/2)2

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

Using the inductive hypothesis, we need to prove that P(k+1) is true.

Or, in other words:

P(k)->P(k+1)

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

P(k+1): 13 +23 +···+k3+(k+1)3 = ((k+1)(k + 2)/2)2

a

13 +23 +···+k3+(k+1)3, substituting the inductive hypothesis we get,

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

= k2(k+1)2/4 + (k+1)2(k+1), using (k+1)2 as a common factor we get,

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

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

= (k+1)2(k+2)2]/4

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

⧠

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

The steps above show that this formula is true whenever n is a positive integer because of the principle of mathematical induction.

Related exercises: