5
$\begingroup$

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

  • 2
    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$.2011-11-03

5 Answers 5

5

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.

  • 2
    @JM: $t$hanks, now it's even more pyramidal.2011-11-03
2

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.

  • 0
    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$.2013-10-11
1

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.

  • 0
    See also [Integer-valued polynomial](http://en.wikipedia.org/wiki/Integer-valued_polynomial).2014-07-11
0

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.

-2

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.

  • 0
    Yeah, this is just unkind, poorly formatted, and unhelpful.2014-07-11