Prove that the quantity is an integer

Question

I want to prove that $\frac{n^3}{3}-\frac{n^2}{2}+\frac{n}{6} \in \mathbb{Z}, \forall n \geq 1$.

I have thought to use induction.

Base Case: For $n=1$, $\frac{n^3}{3}-\frac{n^2}{2}+\frac{n}{6}=\frac{1}{3}-\frac{1}{2}+\frac{1}{6}=0 \in \mathbb{Z}$.

Induction hypothesis: We suppose that it holds for $n=k$, i.e. that $\frac{k^3}{3}-\frac{k^2}{2}+\frac{k}{6} \in \mathbb{Z}$.

Induction step: We want to show that it holds for $n=k+1$.

$$\frac{(k+1)^3}{3}-\frac{(k+1)^2}{2}+\frac{k+1}{6}=\frac{k^3}{3}+\frac{k^2}{2}+\frac{k}{6}$$

Is everything right? If so, then we cannot use at the induction step the induction hypothesis, can we?

Or can we not get the desired result using induction?

Answer 1

If you want to use induction you want to show that $$\frac{(k+1)^3}{3}-\frac{(k+1)^2}{2}+\frac{k+1}{6}$$ is an integer. You can expand all the terms and use the known fact about the expression for $k$ to get there.

Another approach is to note that $6$ is a common denominator and say you want to prove that the numerator $2k^3-3k^2+k$ is divisible by $6$. But $2k^3-3k^2+k=(2k-1)(k-1)k$ and one of $k$ or $k-1$ is even and one of the terms is a multiple of $3$.

Answer 2

Yes, we can. If $f(n)=\frac{n^3}{3}-\frac{n^2}{2}+\frac{n}{6}$, then $f(n+1)-f(n)=n^2$.

Answer 3

$$F=\frac{n^3}{3}-\frac{n^2}{2}+\frac{n}{6}=\frac{n(n-1)(2n-1)}{6}$$

You can see that for any n(odd or even) the numerator is always a multiple of 6, so the sum of fractions is an integer; in fact we may have:

• $n=6k ⇒ F=6m/6=m $

• $n=6k+1 ⇒ F=(6k+1)(6k+1-1)(12k+2-1)=6m/6=m$

• $n=6k+2 ⇒ F=(6k+2)(6k+2-1)(12k+4-1)=6t/6=t$

• $n=6k+3 ⇒ F=(6k+3)(6k+3-1)(12k+6-1)=6s/6=s$

• $n=6k+4 ⇒ F=(6k+4)(6k+4-1)(12k+8-1)=6v/6=v$

• $n=6k+5 ⇒ F=(6k+5)(6k+5-1)(12k+10-1)=6u/6=u$

Where m,t,s,u and v are integers.

Answer 4

To prove $$\frac{n^3}{3}-\frac{n^2}{2}+\frac{n}{6} \in \mathbb{Z}, \forall n \geq 1$$

We take common denominator and prove the numerator is a multiple of $6.$

The numerator factors as $$n(2n-1)(n-1)$$

One of $n$ or $n-1$ is even so the product is multiple of $2$

The remainder of n in dividing by $3$ is either $0$ or $1$ or $2$

In either of these cases the product $$n(2n-1)(n-1)$$ is divisible by $3$
Thus the numerator is always a multiple of $6$ which makes the fraction an integer.

Answer 5

If you put everything over a common denominator you get $$f(n)=\frac {2n^3-3n^2+n}6=\frac {n(n-1)(2n-1)}6$$

Now it is easier, I think, to see what is going on for a straightforward induction, or you can write $2n-1=2n-4+3$ and split up into different fractions viz $$f(n)=\frac {n(n-1)(2n-4+3)}6=\frac {n(n-1)(n-2)}3+\frac {n(n-1)}2$$ and this is easily the sum of two integers since the product of $r$ successive integers is divisible by $r$ (easily proved by induction), or you can do the induction on $n$ based on this form of $f(n)$, which will should work easily.

Answer 6

After writing it in the form $\,a_n/6$ we need only show that $a_n\equiv0\pmod 6$ for all $n,\,$ doable by testing all values $\,n\equiv 0,\pm1,\pm2,3\pmod 6.\,$ Equivalently we can test all values mod $2$ and $3$ and then we need only test values $\equiv 0,\pm1,$ which we can do quickly as below, in a way that generalizes.

$n\equiv\pm1\Rightarrow \color{#c00}{n^2\equiv 1}\Rightarrow \underbrace{\overbrace{ 2n\color{#c00}{n^2}\!-\!3\color{#c00}{n^2}\!+\!n}^{\Large a_n}}_{\Large{\rm OP}\ =\ a_n/6}\equiv 3(n\!-\!1)\equiv 0\,$ mod $\,2$ & $3,\,$ so $\,2,3\mid a_n\Rightarrow 6\mid a_n$

Remark $\ $ More generally, as above, breaking $f(x)\in\Bbb Z[x]$ into odd and even parts shows

$$ \bbox[7px,border:1px solid #c00]{6\mid f(n) = g(n^2)n+h(n^2)\iff 6\mid h(0),\,\ 3\mid g(1),h(1),\,\ 2\mid g(1)+h(1)}\qquad\ \ $$

e.g. in OP $\ f(n) = (2n^2\!+\!1)n - 3n^2\ $ & $\ 3\mid g(1)\!=\!3,\,\ 3\mid h(1)\!=\!-3,\,\ 2\mid g(1)\!+\!h(1)=0$

For any polynomial $f(n)$ we can quickly mentally perform this test by computing $\!\bmod 6$ the values $\,g(1) \equiv $ sum of odd degree coefs, and $\,h(1)\equiv $ sum of even degree coefs, then apply the above tests.

Answer 7

A different appraoch:

Note that \begin{align} \frac{n^3}{3}-\frac{n^2}{2}+\frac{n}{6} &= \underbrace{\frac{n(n+1)(2n+1)}{6}}_{\displaystyle=\sum_{k=1}^n k^2 }-2\,\underbrace{\frac{n(n+1)}{2}}_{\displaystyle=\sum_{k=1}^{n}k}+n=\sum_{k=1}^n(k^2-2k+1)\in\Bbb Z \end{align}

Answer 8

Let's continue from your last step.

$$\frac{(k+1)^3}{3}-\frac{(k+1)^2}{2}+\frac{k+1}{6}=\frac{k^3}{3}+\frac{k^2}{2}+\frac{k}{6}$$ $$=\frac{k^3}{3}-\frac{k^2}{2}+2\frac{k^2}{2}+\frac{k}{6}$$ $$=\frac{k^3}{3}-\frac{k^2}{2}+\frac{k}{6}+k^2$$

By induction hypothesis, first three terms yileds an integer and $k^2$ is an integer.

Thus finally we have showed that $$\frac{(k+1)^3}{3}-\frac{(k+1)^2}{2}+\frac{k+1}{6}$$ is an integer.