Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My attempt at it: $\displaystyle 2n^3+3n^2+n= n(n+1)(2n+1) = 6\sum_nn^2$ This however reduces to proving the summation result by induction, which I am trying to avoid as it provides little insight.

share|cite|improve this question
if you want to use induction then use the fact that for your polynomial $p(n)=n(n+1)(2n+1)$ the following property holds: $$p(n+1)=6(n+1)^2+p(n)$$ – miracle173 Jun 26 '11 at 9:56

12 Answers 12

up vote 13 down vote accepted

If you write this as $2n^3+3n^2+n\equiv 0 \mod 6$ then you only need to check $n=0,1,2,3,4,5$.

Alternatively, write as $\dfrac{2n(2n+1)(2n+2)}{4}$ where the numerator obviously has a multiple of 3, a multiple of 4 and another multiple of 2, so is divisible by 24, meaning the expression is divisible by 6.

share|cite|improve this answer
Dear @henry, could you incorporate the comment into your answer? All other solutions are correct, but that seemed the most elegant and closest to what i was looking for. (re: 3 consecutive) – kuch nahi Jun 26 '11 at 7:59

You have $2n^3+3n^2+n=n(n+1)(2n+1)$, and $2\mid n(n+1)$. If $3\mid n(n+1)$, then you're done. Otherwise, $n\not\equiv 0\pmod{3}$ and $n\not\equiv -1\pmod{3}$, so $n\equiv 1\pmod{3}$. Then $2n+1\equiv 3\equiv 0\pmod{3}$, so $3\mid 2n+1$ and you get the result.

share|cite|improve this answer

HINT $\rm\ f(n) =\: 3\ (n^2+n) + 2\ (n^3-n)\ =\ 3\ n\ (n+1)\ +\ 2\ (n-1)\ n\ (n+1)\:.\:$ But $2$ divides one of $\rm\:n,\:n+1\:$ and $3$ divides one of $\rm\:n-1,\:n,\:n+1\:.\:$ Or, said in terms of binomial coefficients,

$$\rm f(n)\ =\ 6\ {n+1\choose 2}\ +\ 12\ {n+1\choose 3}\quad\text{is a multiple of}\ \ 6$$

In fact this generalizes widely: it is a classical result of Polya and Ostrowski (1920) that every integer valued polynomial, i.e. every $\rm\:f(x)\in \mathbb Q[x]\:$ with $\rm\:f(\mathbb Z)\subset \mathbb Z\:,\:$ is an integral linear combination of binomial coefficients. See this answer for references (and a similar problem).

share|cite|improve this answer

Yet another way to look at it is as follows:

First, as several others have already noted, $n(n+1)$ is divisible by $2$, so we just need to check for divisibility by $3$. Now, $n \equiv 0,1, \text{ or } 2 (\text{mod } 3)$. In the case of $n \equiv 0 (\text{mod } 3)$, the problem is trivial. In the case of $n \equiv 2 (\text{mod } 3)$, $n+1 \equiv 0 (\text{mod } 3)$. There is but one last case, but that too is covered: $2n+1 \equiv 0 (\text{mod } 3)$ if $n \equiv 1 (\text{mod } 3)$. To summarize...

$n \equiv 0 (\text{mod } 3) \implies n \equiv 0 (\text{mod } 3)$
$n \equiv 1 (\text{mod } 3) \implies 2n+1 \equiv 0 (\text{mod } 3)$
$n \equiv 2 (\text{mod } 3) \implies n+1 \equiv 0 (\text{mod } 3)$

How's that? :)

share|cite|improve this answer

Since $\displaystyle\frac{2n^3+3n^2+n}{6}=2\binom{n}{3}+3\binom{n}{2}+\binom{n}{1}$, it is easy to see that $6|(2n^3+3n^2+n)$.

Here is a general collection of results that can be applied in cases like this.

Define the combinatorial polynomial of degree $k$: $C_k(n)=\binom{n}{k}$. Let $L_k$ be the set of integral linear combinations of combinatorial polynomials of degree at most $k$. That is, $$ f\in L_k \Leftrightarrow f=\sum\limits_{j=0}^ka_kC_k\text{ for some }a_k\in\mathbb{Z} $$ Claim: Let $\{ a_j : j = 0\dots k \}$ be a set of $k+1$ integers, then there exists a $P\in L_k$ such that $P(j) = a_j$ for $j = 0\dots k$.

Proof: Since $a_0C_0(0)=a_0$, the claim is true for $k=0$.

Suppose the claim is true for some $k$. Let $\{ a_j : j = 0\dots k+1 \}$ be a set of $k+2$ integers and let $Q$ be an element of $L_k$ so that $Q(j) = a_j$ for $j = 0\dots k$. Since $b = a_{k+1} - Q(k+1)$ is an integer and $$ C_{k+1}(j) = \left\{\begin{array}{ll}0&\text{for }j=0\dots k\\1&\text{for }j=k+1 \end{array}\right. $$ $P(j) = Q(j) + b C_{k+1}(j)$ is an element of $L_{k+1}$, $P(j) = Q(j) = a_j$ for $j = 0\dots k$, and $$ \begin{align} P(k+1) &= Q(k+1) + b C_{k+1}(k+1)\\ &= Q(k+1) + (a_{k+1} - Q(k+1))\\ &= a_{k+1} \end{align} $$ Thus, the claim is true for $k+1$.$\hspace{.25in}\square$

Theorem: a polynomial, $P:\mathbb{Z}\mapsto\mathbb{Z}$ if and only if $P\in L_k$ for some $k$.

Proof: Because $C_k:\mathbb{Z}\mapsto\mathbb{Z}$, it is easy to see that any $f\in L_k$ sends $\mathbb{Z}\mapsto\mathbb{Z}$.

Let $Q$ be a polynomial of degree $k$ that maps $\mathbb{Z}\mapsto\mathbb{Z}$. Let $P$ be a polynomial in $L_k$ such that $P(j) = Q(j)$ for $j = 0\dots k$. Since a polynomial of degree $k$ is determined by its values at $k+1$ points, we must have that $P = Q$; that is, $Q\in L_k$.$\hspace{.25in}\square$

So we have a characterization of all polynomials that map $\mathbb{Z}\mapsto\mathbb{Z}$. We also have

Corollary: If a polynomial of degree $k$ maps $k+1$ consecutive integers to integers, it maps all integers to integers.

Proof: Suppose $P$ is a polynomial of degree $k$ and $P:\{m,m+1,m+2,\dots,m+k\}\mapsto\mathbb{Z}$. The Claim above assures that there is a $Q\in L_k$ so that $Q(j)=P(m+j)$ for $j=0,1,2,\dots,k$. Since a polynomial of degree $k$ is determined by its values at $k+1$ points, we must have that $P(j)=Q(j-m):\mathbb{Z}\mapsto\mathbb{Z}$.$\hspace{.25in}\square$

share|cite|improve this answer

Yet another way to see it: consider n(n+1)(2n+1). Write the third factor as (2(n+2)-3), so we have n (n+1) (2(n+2)-3). Since one of n, n+1 must be even, the product is divisible by 2.

One of n, n+1, n+2 must be divisible by 3. Note that n+2 is divisible by 3 if and only if 2(n+2)-3 is divisible by three, so this means that one of n, n+1, 2(n+2)-3 is divisible by three, and hence so is their product.

Since 2 and 3 are relatively prime, we have that n(n+1)(2n+1) is divisible by their product, 6.

share|cite|improve this answer

Note that either $n$ or $n+1$ is divisible by 2. Now if $n=3k+c$, then $n+1 = 3k+c+1$ and $(2n+1) = 6k + 2c+1$. If $c=0$ then $n$ is divisible by 3, if $c=1$ then $2n+1$ is divisible by 3, and if $c=2$ then ...

share|cite|improve this answer

HINT $\rm\quad 6\ |\ f(0) = 0\:$ and $\rm\ 6\ |\ f(k+1)-f(k)\:=\ 6\ (k+1)^2\:$ so $\rm\:6\ |\ f(n)\:$ by telescopic induction

$$\rm f(n)\ =\ (f(n)-f(n-1))\ +\ (f(n-1)-f(n-2))\ +\ \cdots\ +\ (f(1)-f(0))\ +\ f(0)$$

I.e. $\rm\ f\:$ is constant mod $6$, $\rm\:\ f(k+1)\equiv f(k)\ $ hence $\rm\ f(n)\equiv f(0) = 0\:.$

You can find many examples of telescopy in my prior posts here.

share|cite|improve this answer

Well you can divide $n$ by $3$ using the usual division with remainder to get $n = 3k + r$ where $r = 0, 1$ or $2$. Then just note that if $r = 0$ then $3$ divides $n$ so $3$ divides the product $n(n+1)(2n+1)$.

If $r = 1$ then $2n + 1 = 2(3k+1) + 1 = 6k+3 = 3(2k+1)$ so again $3$ divides $2n+1$ so it divides the product $n(n+1)(2n+1)$. And similarly you can check that if $r = 2$ then something like this happens so in all possible cases $3$ divides $n(n+1)(2n+1)$

And then you can do the same process but with 2 instead, that is, writing $n = 2k + r$ where now $r = 0$ or $1$.

share|cite|improve this answer

To prove that an expression in terms of $n$ is divisible by 6, it may be helpful to look at the cases where $n=6k$, $n=6k+1$, $n=6k+2$, $n=6k+3$, $n=6k+4$, and $n=6k+5$, where $k\in\mathbb{Z}$.

share|cite|improve this answer
This sounds cumbersome. We know that one of the three factors in $n(n+1)(2n+1)$ must be even. Is there a way to show that one of them must be divisible by three as well? (If they were consecutive, this would have been obvious) – kuch nahi Jun 26 '11 at 7:55
@kuch nahi: Ahh, if you already know that you've got a factor of 2 and just need to check for the factor of 3, then you can look at only 3 cases: $n=3k$, $n=3k+1$, and $n=3k+2$. – Isaac Jun 26 '11 at 7:57
@kuch nahi: $2n(2n+2)(2n+1)/4$ has three consecutive – Henry Jun 26 '11 at 7:58

$n(n+1)$ is divisible by $2$.
And $2(2n^3+3n^2+n) = n(n+1)(4n+2) \equiv n(n+1)(n+2) \mod 3$ is divisible by 3.

share|cite|improve this answer

to check for divisibility by 6 a number must be divisible by both 2 and 3 so we will prove that $2n^3 + 3n^2 + n = n (2n^2 + 3n +1) = n (n+1) (2n+1)$

If $n$ is even then 2 divides $n$ and $n+1$ will be odd so $n+1$ can be $3k+2$ or $3k$ where $k$ is some integer.

If $3k+1 = n+1$ as it would make $n$ itself a multiple of 6 as our assumption that $n$ is even

So if $n+1$ is $3k$ it can be divided by 3 so no problem. But if $n+1 = 3k+2$ then $2n+1$ will be $2(3k+1) +1 = 6k+3$ which is divisible by 3 and hence by 6.

Case 2: If $n$ is odd then $n+1$ is even and thus divisible by 2.

  • if $n$ is $3k$ then it is divisible by 3 so no issues
  • if $n$ is $3k+2$ as it makes $n+1=3k+3$ which is itself a multiple of 6 as our earlier assumption is that $n+1$ is even
  • if $n$ is $3k+1$ then $2n+1$ becomes $2(3k+1)+1=6k+3$ which is divisible by 3 and hence proved
share|cite|improve this answer
I've tried to made your post more readable by adding formatting, LaTeX markup, paragraphs.... I hope I did not unintentionally changed meaning somewhere - of course, you should edit your post again, if you think it's needed. – Martin Sleziak Jan 7 '12 at 17:57

Your Answer


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.