Disc Maths question

Question

Suppose you want to prove for all n⩾0 that the property P(n) given by

n

∑ j(j+1)/2 = n^3/6+n^2/2+n/3.

j=0

holds using induction on n. What should the induction step show (assuming that P(n) holds)?

Answer 1

Use standard induction notation:

1(1 + 1)/2 + 2 (2 + 1)/2 + 3(3 + 1)/2 + ... + n(n + 2)/2 = n³/6 + n²/2 + n/3

1) Demonstrate for n = 1

1(1 + 1)/2 = 1³/6 + 1²/2 + 1/3

2/2 = 1/6 + 1/2 + 1/3

1 = 1

2) Assume true for n

1(1 + 1)/2 + 2 (2 + 1)/2 + 3(3 + 1)/2 + ... + n(n + 2)/2 = n³/6 + n²/2 + n/3

3) Demonstrate true for n + 1

1(1+1)/2 + 2 (2+1)/2 + 3(3+1)/2 + ... + n(n + 1)/2 + (n+1)(n + 1 + 1)/2 =

n³/6 + n²/2 + n/3 + (n+1)(n + 1 + 1)/2