Question

Write out proof in paragraph form. Include contradictions if necessary

5. Prove that n(n+1) (2n+1) is always divisible by 6

Answer 1

If
`n=1`, then

`n(n+1)(2n+1)=1\cdot2\cdot3=6`

which is of course divisible by 6.

Assume the claim holds for
`n=k`. Then if
`n=k+1`, we have

`(k+1)(k+2)(2k+3)=\underbrace{k(k+1)(2k+1)}+k(2k+3)+(k+2)(2k+3)+2k(k+1)`

(I use the distributive property of multiplication to extract the first term, which we've assumed is divisible by 6)

The claim holds for
`n=k+1` if

`k(2k+3)+(k+2)(2k+3)+2k(k+1)`

is also divisible by 6. With some manipulation we can express this as

`(2k+2)(2k+3)+2k(k+1)`

`(k+1)(2(2k+3)+2k)`

`(k+1)(6k+6)`

`6(k+1)^2`

which is clearly divisible by 6, so the claim is true for
`n=k+1`, and this completes the proof (by induction).