# Prove that $6|2n^3+3n^2+n$

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.

-
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

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.

-
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.

-

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).

-

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? :)

-

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.

-

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 ...

-

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.

-

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$

-

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$.

-

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}$.

-
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.

-

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
-
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