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

Question

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 $$

Answer 1

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.

Answer 2

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.

Answer 3

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.