# 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. is a poor mathematician 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