Given $n \in \mathbb{N}$ prove that a polynomial result gives a natural number. A friend asked me this question:
Prove that for every $n\in \Bbb N$ the next equation result: $\dfrac{n^3}{6}+\dfrac{n^2} {2}+\dfrac{n}{3}$ would be a natural number.
My instincts were that i need to use induction, Though i'm not sure how. So i've started with this:
$$\frac{n^3+3n^2+2n}{6}\to\frac{n(n^2+3n+2)}{6}\to\frac{n(n+1)(n+2)}{6}$$
As i see it, I need to prove that $n(n+1)(n+2)$ divides $6$, with no reminder, Or even just prove that every $3$ consecutive numbers divides $6$ without reminder.
But, I can't seem to understand how to do it. I guess i'm missing something.
 A: Hints: (1) By uniqueness of prime decomposition, to be a multiple of 6 it is necessary and sufficient to be a multiple of 2 and 3.
(2) Can you show that for any natural $n$ either $n$ or $n+1$ is even, that is a multiple of 2?
(3) For 3, argue as in (2) for 2, but now using $n+2$ also.
A: For this concrete example there are many ways to proceed, but if you find more such problems you would want to avoid an ad hoc solution for each case. For the general case, the key observations are:
Proposition 1. For any field $K$ of characteristic$~0$, there is a basis$~B$ of the $K$-vector space $K[X]$ formed by the polynomials $\binom Xk=\frac{X(X-1)\ldots,(X-k+1)}{k!}$ for $k\in\Bbb N$.
Proof. Basically this is because the (infinite) matrix expressing these polynomials on the standard basis of monomials $X^k$ is upper triangular with nonzero coefficients $\frac1{k!}$ on the diagonal, hence invertible. But for who dislike arguments using infinite matrices, one shows easily by induction on the degree that any polynomial$~P$ can be uniquely expressed as a linear combination of elements of$~B$. Any non-trivial such linear combination gives a polynomial of the highest degree of an element of$~B$ that is used with nonzero coefficient; in particular it is nonzero, so $B$ is free. To attain $P$ as a linear combination one must refrain from using $\binom Xk$ for $k>\deg P$, and the coefficient for $k=\deg P$ must be the leading coefficient of$~P$ divided by$~k!$. After subtracting that multiple of $\binom Xk$, what remains of$~P$ is of lower degree and can be written as linear combination of elements of$~b$ by the induction hypothesis, so $B$ generates$~K[X]$. QED
Proposition 2. For $P\in K[X]$, the values of $P[n]$ are integer for all $n\in\Bbb Z$ if and only if the coefficients in the expression of $P$ in the basis$~B$ of proposition$~1$ are all integers.
Proof. It is clear that each $\binom Xk[n]=\binom nk$ is integer when $n\in\Bbb N$, by the combinatorial interpretation of binomial coefficients; for $n<0$ it suffices to apply the identity $\binom{-n}k=(-1)^k\binom{k+n-1}k$. Therefore if all coefficients are integer, $P[n]$ will be integer for all $n\in\Bbb Z$. Suppose conversely that $P[n]$ is integer for all $n\in\Bbb N$ (we won't need negative values of$~n$.) That the coefficient $c_n$ of $\binom Xn$ in $P$ is integer will be shown by strong induction on $n$. Since $\binom nk=0$ whenever $k>n$, one has $P[n]=\sum_{k=0}^nc_k\binom nk$, and because $\binom nn=1$ this can be written $c_n=P[n]-\sum_{k=0}^{n-1}c_k\binom nk$, which is integer by hypothesis. QED
So we have a criterion for deciding whether a polynomial expression of a single variable gives an integer value for all integer values of the variable: just express it on the basis$~B$ and check whether the coefficients are integers. Now it is known that the coefficient $c_k$ can be found by computing (an initial part of) the sequence $(P[n])_{n\in\Bbb N}$, applying $k$ times the difference operator$~\Delta$ to the sequence, and reading of the initial coefficient of the resulting sequence. Since this value only depends on the first $k+1$ values of the initial sequence, one has the trivial criterion to test the condition.
Theorem. A polynomial $P\in\Bbb Q[X]$ of degree$~d$ has the property that $P[n]$ is integer for all $n\in\Bbb Z$ if and only if $P[n]\in\Bbb Z$ for $n=0,1,\ldots,d$.
Proof. The "only if" part is obvious; assume $P[n]\in\Bbb Z$ for $n=0,1,\ldots,d$. As in the proof of proposition 1, the coefficient $c_k$ of $\binom Xk$ in$~P$ is zero for $k>d$. The proof of proposition 2 shows that $c_k\in\Bbb Z$ for $0\leq k\leq d$. Then proposition 2 applies, and gives the theorem. QED
Since $P$ takes integer values at all $n\in\Bbb Z$ if and only if the shifted polynomial $P[X+m]$ for some integer$~m$ does so, one can replace the values $0,1,\ldots,d$ at which $P$ is evaluated in the theorem by any $d+1$ consecutive values $m,m+1,\ldots,m+d$.
A: There are two ways:


*

*(As pointed out by @martini) Prove that one of any two consecutive numbers is divisible by two and one of any three consecutive numbers is divisible by three. Therefore the product of any three consecutive numbers has to be divisible by six.

*Prove that $\binom{n+2}{3} = \frac{n(n+1)(n+2)}{6}$ and we know that it is an integer, because it counts the ways you can pick $3$ elements from a set of size $n+2$. See also here, in fact $\binom{n+2}{3} = \frac{n(n+1)(n+2)}{6}= \sum_{k=1}^{n}\sum_{i=1}^{k}i$, and this is yet another proof that it is an integer.
I hope this helps $\ddot\smile$
A: Well, product $n(n+1)(n+2)$ is always even, in fact if $n$ is odd $n+1$ should be even, if $n$ is even, $n$ should be odd. So, if we suppose that $3$ divides $n$, obviously $6$ divides product. If $n= 1( mod 3)$, $3$ divides $n+2$. If $n=2 (\mod 3)$, $3$ divides $ n+1$. Hence the product is always divisible by $6$.
A: If you want to prove it by induction, you can. If the proposition is true of $n$, then it is easy to show that it is true of $n+6$.  You then have to check 6 base cases.
