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.
 A: 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. 
A: 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).
A: 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}\to\mathbb{Z}$ if and only if $P\in L_k$ for some $k$.
Proof: Because $C_k:\mathbb{Z}\to\mathbb{Z}$, it is easy to see that any $f\in L_k$ sends $\mathbb{Z}\to\mathbb{Z}$.
Let $Q$ be a polynomial of degree $k$ that maps $\mathbb{Z}\to\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}\to\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\}\to\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}\to\mathbb{Z}$.$\hspace{.25in}\square$
A: 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? :)
A: 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.
A: 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 ...
A: 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.
A: 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$.
A: 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.
A: 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}$.
A: $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.
A: 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 

