# Proving that $f(n)$ is an integer using mathematical induction

I want to prove that

$$\frac{n^3}{3}+\frac{n^5}{5}+\frac{7 n}{15}$$

is an integer for every integer $n \geq 1$.

I define P(n) to be:

$$\frac{n^3}{3}+\frac{n^5}{5}+\frac{7 n}{15}$$ is an integer.

For my basis step, P(1) is true because

$$\frac{1^3}{3}+\frac{1^5}{5}+\frac{7}{15}=1$$ which is an integer.

The inductive step is what's tripping me up...

Let k be an arbitrary positive integer. Assume that P(k) is true, that is,

$$\frac{k^3}{3}+\frac{k^5}{5}+\frac{7 k}{15}$$ is an integer.

So based on that assumption, I need to now show that P(k+1) is true, i.e., that

$$\frac{(k+1)^3}{3} +\frac{(k+1)^5}{5} +\frac{7 (k+1)}{15}$$ is an integer.

At this point, I am stuck as to where to go next...

I have tried rewriting the assumption:

$$\frac{k^3}{3}+\frac{k^5}{5}+\frac{7 k}{15}=15 m$$ for some integer m. Then I solve for m:

$$\frac{1}{15} \left(\frac{k^3}{3}+\frac{k^5}{5}+\frac{7 k}{15}\right)=m$$

But this looks like a dead-end, seems there's nothing I can do with this to the "to prove" equation.

I have also tried re-writing the "to show" equation as this, but I get a dead end there and am not sure where to go next:

$$\frac{1}{15} \left(5 (k+1)^3+3 (k+1)^5+7 (k+1)\right)$$

-
You want to prove $A(n)$ is an integer for every $n\geqslant1$ and you know $A(1)$ is. You could compute $A(n+1)-A(n)$ and show this is an integer for every $n\geqslant1$. – Did Nov 3 '11 at 12:06

Why do you think that $P(k) = 15m$ for some integer $m$ if it does not hold for, say $k=1$? If you assume that $P(k)$ is integer then the strategy is to show that $$P(k+1) - P(k) \in\mathbb Z$$ and let us do it: $$P(k+1) - P(k) = \frac{1}{5}((n+1)^5-n^5)+\frac13((n+1)^3 - n^3)+\frac7{15} =$$ $$= \frac15(5n^4+10n^3+10n^2+5n+1) +\frac13(3n^2+3n+1)+\frac7{15}$$ $$= n^4+2n^3+2n^2+n +\frac15+n^2+n+\frac13+\frac{7}{15}$$ $$= n^4+2n^3+3n^2+2n+1$$ $$=(n^2+n+1)^2\in \mathbb Z$$ and you're done.

-
The last bit is written more neatly as $(n^2+n+1)^2$. – J. M. Nov 3 '11 at 12:13
Thanks! Just what I needed – mathemagician11 Nov 3 '11 at 12:19
@JM: thanks, now it's even more pyramidal. – Ilya Nov 3 '11 at 12:20

This problem becomes trivial when thought of in terms of division. Realize that the common denominator of the fractions is 15. Thus, all we need to show is that $$15 \mid 3n^5+5n^3+7n\;\;\forall n$$ Since $15=3 \cdot 5$, all we have to show is that both 3 and 5 will divide this for all $n$. To make this easy, we simply show the equation is 0 modulo 3 and modulo 5 for all $n$.

Note that mod 3, we are left with $2n^3+n$ and need only consider $n=0,1,2$. This checks out easily.

Similarly, mod 5, we are left with $3n^5+2n$ and must consider $n=0,1,2,3,4$. Again, this checks out.

Since $\gcd(3,5)=1$ it follows that this equation will be divisible by their product, 15, for all $n$ as well.

-
A general theorem tells us that $x^p=x$ in $\mathbb{Z}/p$ if $p$ is a prime. Therefore, $3n^5=3n$ in $\mathbb{Z}/5$, so $3n^3+2n=5n=0$ in $\mathbb{Z}/5$. Likewise, $2n^3+n=2n+n=3n=0$ in $\mathbb{Z}/3$. – Baby Dragon Oct 11 '13 at 18:24

Here is a proof not by induction, but which may be instructive.

Using repeated differences on the first few values of $P(n)$ we get $$\begin{array}{llll} 0 & 1 & 10 & 59 & 228 & 669 & 1630 & \\ 1 & 9 & 49 & 169 & 441 & 961 & \\ 8 & 40 & 120 & 272 & 520 & \\ 32 & 80 & 152 & 248 & \\ 48 & 72 & 96 & \\ 24 & 24 & \\ 0 & \\ \end{array}$$ Newton's interpolation formula then gives us $$P(n)= 0 \binom{n}{0} + 1 \binom{n}{1} + 8 \binom{n}{2} + 32 \binom{n}{3} + 48 \binom{n}{4} + 24 \binom{n}{5}$$

This is clearly an integer for all $n\ge 0$.

In general, if a polynomial of degree $d$ and with rational coefficients takes integer values for $d+1$ consecutive integers, then it takes integers values for all integer arguments because all repeated differences are integers and so are the coefficients in Newton's interpolation formula.

-

Expand the binomials and group the resulting fractions such that you get integers.

In other words, you know that

$$(k + 1)^3 = k^3 + 3k^2 + 3k + 1$$

and

$$(k + 1)^5 = k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1$$

That should do the trick.

-

You are needed to use the fact that integer is another integer. Now put $k$ and consider the result true then go for $k-1$. From step in which you put $k$ you get an equation that give an $\frac{k^3}{3}+\frac{k^5}{5}+\frac{7k}{15}=p$ (an integer). Using it and fact stated in line $1$ solves the problem.

-
You should try not to call a question "easy" when helping someone. It does little more squash flat that person's confidence. – user1729 Jul 11 '14 at 10:55
Yeah, this is just unkind, poorly formatted, and unhelpful. – JHance Jul 11 '14 at 13:47