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

I want to prove that

$$n^3/3 + n^5/5 + 7n/15$$

is an integer for every integer n >= 1.

I define P(n) to be: $$n^3/3 + n^5/5 + 7n/15$$ is an integer.

For my basis step, P(1) is true because $$1^3/3 + 1^5/5 + 7(1)/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, $$k^3/3 + k^5/5 + 7k/15$$ is an integer.

So based on that assumption, I need to now show that P(k+1) is true, i.e., that $$(k+1)^3/3 + (k+1)^5/5 + 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:

$$k^3/3 + k^5/5 + 7k/15 = 15m$$ for some integer m. Then I solve for m: $$(k^3/3 + k^5/5 + 7k/15)/15 = 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:

$$(5(k+1)^3 + 3(k+1)^5 + 7(k+1)) / 15$$

-
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

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.

-

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.

-