Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I wanted to prove that $n(n+1)(2n+1)$ is always divisible by three, for this I used the following approach:

$n = 0, 1\pmod2$

for $n = 0$; $$n(n+1)(2n+1) \equiv 0\pmod3$$

for $n = 1$; $$n(n+1)(2n+1) \equiv 0\pmod3$$

But now I am unsure if this the correct way of doing because of the following eg:

Let $k = \text{an odd number}\equiv 1\mod3$

for $k = 1$; $2k + 1 \equiv 0\pmod3$, therefore for every odd number $2k + 1$ is divisible by $3$, but this is not true.

So my question is the approach I am using to prove $n(n+1)(2n+1)$ divisible by $3$ is wrong or only the second example is wrong?, and why?

share|improve this question
2  
Why do you look at $n$ mod 2 at the beginning, when what you're interested in is $n(n+1)(2n+1)$ mod 3? Where does the 2 come from? –  Ben Millwood Jun 3 '12 at 9:00

4 Answers 4

up vote 9 down vote accepted

Your first mistake is at the very beginning, when you split into two cases according as $n$ is even or odd. You’re looking at divisibility by $3$, not by $2$, so it’s unlikely to matter whether $n$ is even or odd; you should be looking at the cases $n\equiv 0\pmod3$, $n\equiv 1\pmod3$, and $n\equiv 2\pmod3$. Here’s most of a table showing the congruence classes mod $3$ of the expressions involved.

$$\begin{array}{rcc} n\bmod3:&0&1&2\\ (n+1)\bmod3:&1&2&0\\ (2n+1)\bmod3:&1\\ \hline \big(n(n+1)(2n+1)\big)\bmod3:&0&&0 \end{array}$$

With what I’ve already filled in, you can see that $n(n+1)(2n+1)$ is divisible by $3$ when $n\equiv 0,2\pmod3$; if you finish filling in the table, you can finish the proof.

share|improve this answer
    
Thank you, Actually I was quite unsure about using mod, and you really helped me in understanding it. –  Kartik Anand Jun 3 '12 at 9:05

Every number $n$ is congruent to $0$, $1$, or $2$ mod $3$.

If $n \equiv 0 \pmod 3$, then $3 \mid n$.

If $n \equiv 1 \pmod 3$, then $2n \equiv 2 \pmod 3$ which implies $2n + 1 \equiv 3 \pmod 3$ which implies $2n + 1 \equiv 0 \pmod 3$.

If $n \equiv 2 \pmod 3$, then $n + 1 \equiv 3 \pmod 3$ which implies $n + 1 \equiv 0 \pmod 3$.

Hence for all for all $n$, $n(n + 1)(2n + 1)$ is divisible by $3$.

share|improve this answer

Note that $2\equiv -1\bmod 3$, so we have $$ n(n+1)(2n+1)\equiv n(n+1)(-n+1)\equiv-n(n+1)(n-1)\bmod 3. $$ Of course, $3$ divides one of the numbers $n-1$, $n$ and $n+1$.

share|improve this answer

Writing $$ n(n+1)(2n+1)=6\binom{n}{1}+18\binom{n}{2}+12\binom{n}{3}\tag{1} $$ we see that $n(n+1)(2n+1)\equiv0\pmod{6}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.