0

Show that for all n ∈ N, it is true that $(n) (n + 1) (2n + 1)$ is a multiple of 6, that is: $$\exists m\in \mathbb{N}: n (n + 1) ( 2n + 1) = 6m$$

I think I can prove it by induction, but I don't know how proceed.

babemcnuggets
  • 401
  • 3
  • 14
C4995658
  • 33
  • Yes you can show it by induction and even if it is not much, have you tried at least showing for explicitly one $n\in \mathbb{N}$ that it is a multiple of 6? – babemcnuggets Jun 22 '20 at 14:13
  • Another way is to consider all possible remainders $\bmod 2$ and $\bmod 3$ for $n$ and show that at least one of the factors is a multiple of $2$ and at least one is a multiple of $3$. – Ross Millikan Jun 22 '20 at 14:14
  • Consider the 3 exhaustive cases: 1) n is divisible by 3, 2) n+1 is divisible by 3, and 3) n+2 is divisible by 3. – NeitherNor Jun 22 '20 at 14:17
  • 1
    Without induction: $ n (n + 1) ( 2n + 1) = 6 \binom{n}{1} + 18 \binom{n}{2} + 12 \binom{n}{3} $ – lhf Jun 22 '20 at 14:24

4 Answers4

2

One of $n$ and $n+1$ is a multiple of $2$.

Then, either:

$n$ is a multiple of $3$, or

$n$ is $1$ more than a multiple of $3$, in which case $2n+1$ is a multiple of $3$, or

$n$ is $2$ more than a multiple of $3$, in which case $n+1$ is a multiple of $3$.

In any case, you have a factor which is even, and a factor which is a multiple of $3$, thus the expression is a multiple of $6$.

DreiCleaner
  • 1,497
2

Try to prove by induction that $$1^2+2^2+\cdots+n^2=\frac16n(n+1)(2n+1)$$ then as both sides are integers we know that $6$ divides $n(n+1)(2n+1)$.

Peter Foreman
  • 19,947
1

Yes, do the base case, $0*1*1 = 0 = 6*0$.

Now for the inductive case, assuming it works for n:

\begin{equation*} \begin{split} (n+1)(n+2)(2(n+1)+1) & = 6 + 13 n + 9 n^2 + 2 n^3 \\ & = (n + 3 n^2 + 2 n^3) + (6+12n+6n^2) \\ & = n(n+1)(2n+1) + (6+12n+6n^2) \end{split} \end{equation*}

Because $n$, is an integer $(n+1)(n+2)(2(n+1)+1)$. This concludes the proof.

atul ganju
  • 964
1

Just look at it mod 6 and plug in 0 through 5.

You don't have to be fancy.

marty cohen
  • 107,799