6
$\begingroup$

I've been asked to provide a proof for

If $n$ is an integer then

$$\frac{n}{3} + \frac{n^2}{2} + \frac{n^3}{6}$$

is also an integer.

Any help would be appreciated

$\endgroup$
  • 1
    $\begingroup$ Hint: You can express any $n$ as $6m+k$ for $k\in\{0,\dots,5\}$. Try re-expressing $\frac n3+\frac{n^2}2+\frac{n^3}6$ in terms of $m$ and $i$. Then prove the statement for each of the 6 values of $i$. $\endgroup$ – Tim Jun 3 '13 at 11:36
  • 5
    $\begingroup$ One way is to factorize it, to see that it's $n(n+1)(n+2)/6$. $\endgroup$ – ShreevatsaR Jun 3 '13 at 11:37
13
$\begingroup$

Hint:$$\frac{n}{6}(n^2+3n+2)=\frac{n}{6}(n+1)(n+2)$$ What can you say about the divisibility of $n,(n+1),(n+2)$ by $2$ and $3$?

$\endgroup$
12
$\begingroup$

Hint $\ \ \displaystyle \frac{n^3}{6} + \frac{n^2}{2} + \frac{n}{3}\, =\, \frac{n^3+3n^2+2n}6\,=\, \frac{(n+2)(n+1)n}6\, =\, {n+2\choose 3}\in\Bbb Z$

Remark $\ \ $ This is a special case of a classical result of Polya and Ostrowski $(1920).$ Namely, $\,f(x) \in \mathbb Q[x]$ is an integer-valued polynomial, i.e. $f(\mathbb Z)\subset \mathbb Z\:,\:$ iff $f(x)$ is an integral linear combination of binomial coefficients ${x\choose k},\:$ for $\: k\le \deg f$. For a proof see e.g. Polya And Szego, Problems and theorems in analysis, vol II, Problem 85 p. 129 and its solution on p. 320. This theorem has been extended to more general rings (e.g. Dedekind domains) by Cahen and others.

$\endgroup$
5
$\begingroup$

Start with $n=1$ and you'll get $S(1)=\frac13+\frac12+\frac16=1$, so at least here we know that we get an integer back. Now calculate the difference $$ \Delta S(n)= S(n+1)-S(n) = \left(\frac{n+1}{3}+\frac{(n+1)^2}{2}+\frac{(n+1)^3}{6}\right)-\left(\frac{n}{3}+\frac{n^2}{2}+\frac{n^3}{6}\right)\\ $$

$$\hskip1.7in =\frac12n(n+3)+1.$$

This gives you the value you have to add to $S(n)$. Can you see why $\Delta S(n)$ always gives an integer independant of $n$?

If you can, you know that, once you've started out with an integer you always add integers...

$\endgroup$
  • $\begingroup$ And if you can't immediately see why $\Delta S(n) = S(n+1) - S(n)$ always gives an integer, consider $\Delta \Delta S(n) = \Delta S(n+1) - \Delta S(n)$... :-) $\endgroup$ – ShreevatsaR Jun 3 '13 at 15:59
3
$\begingroup$

Hint: If you can collect all the terms together into a single fraction, the problem reduces to showing that the numerator will always be divisible by the denominator.

Hint 2: Do you know modular arithmetic? If not, see Tim's comment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.