# Proof by induction that the sum of terms is integer

I'm having some trouble in order to solve this induction proof.

Proof that $\forall{n} \in \mathbb{N}$ the number $\frac{1}{5}n^5+\frac{1}{3}n^3 + \frac{7}{15}n$ is an integer.

I've tried proving this by induction, but I've not succeed so far. What I did was:

Let's assume that $\frac{1}{5}n^5+\frac{1}{3}n^3 + \frac{7}{15}n = k$, with $k \in \mathbb{Z}$. So, by induction,

$n=1$
$\frac{1}{5} + \frac{1}{3} + \frac{7}{15} = 1$ and $1 \in \mathbb{Z}$.

Inductive step
I want to prove that if $\frac{1}{5}n^5+\frac{1}{3}n^3 + \frac{7}{15}n = k$, with $k \in \mathbb{Z}$ then $\frac{1}{5}(n+1)^5+\frac{1}{3}(n+1)^3 + \frac{7}{15}(n+1) = l$, with $l \in \mathbb{Z}$

And then I'm stuck. I've tried developing every binomial but, for example, for $\frac{1}{5}(n+1)^5$ I get a $\frac{1}{5}n^4$ that is not in the inductive hypothesis, so therefore, I cannot get rid of it and it's not an integer, so I cannot conclude that $l \in \mathbb{Z}$.

Any help or ideas from where I can follow? Thanks in advance!

-
You don't get a $\frac15n^4$, you get $n^4$. – Alex Becker Jul 14 '13 at 18:14
you're right, my mistake! Thanks a lot for all your quick answers! – pmartelletti Jul 14 '13 at 18:19

You want to try to write this expression in terms of the previous one. So, start by expanding out the terms: \begin{align*} \frac{1}{5}(n+1)^5&=\frac{1}{5}\sum_{k=0}^{5}\binom{5}{k}n^k\\ &=\frac{1}{5}(n^5+5n^4+10n^3+10n^2+5n+1)\\ &=\frac{1}{5}n^5+n^4+2n^3+2n^2+n+\frac{1}{5} \end{align*} Do the same thing for $(n+1)^3$ and $(n+1)$. Now, you can pick out the terms corresponding to the inductive hypothesis; all that's left is to show that the other remaining terms ALSO give you an integer.

-
Did the trick... newton's binomial, right? – pmartelletti Jul 14 '13 at 18:24
@pmartelletti Exactly right - the Binomial Theorem. (Or, just some careful multiplication. :-) ) – Nick Peterson Jul 14 '13 at 18:25

Let $f(n)=\frac{n^5}5+\frac{n^3}3+\frac{7n}{15}$

$$f(n+1)-f(n)=\frac{(n+1)^5}5+\frac{(n+1)^3}3+\frac{7(n+1)}{15}-\left(\frac{n^5}5+\frac{n^3}3+\frac{7n}{15}\right)$$

$$=\frac{(n+1)^5-n^5}5+\frac{(n+1)^3-n^3}3+\frac{7(n+1)-7n}{15}$$

$$=\frac{5n^4+10n^3+10n^2+5n+1}5+\frac{3n^2+3n+1}3+\frac{7}{15}$$

$$=(n^4+2n^3+2n^2+n)+(n^2+n)+\left(\frac15+\frac13+\frac7{15}\right)$$ (using Binomial Theorem)

Now, as you have shown $\frac15+\frac13+\frac7{15}=1$

$$\text{So, if }f(n)=\frac{n^5}5+\frac{n^3}3+\frac{7n}{15} \text{ is an integer for integer } n$$

$$\text{ so will be }f(n+1)=\frac{(n+1)^5}5+\frac{(n+1)^3}3+\frac{7(n+1)}{15}$$

This problem can be extended to more primes and proved using the fact that prime $p$ divides $\binom pr$ for $1\le r\le p-1$

I can not keep back a non-inductive proof:

$$\frac{n^5}5+\frac{n^3}3+\frac{7n}{15}=\frac{n^5-n}5+\frac{n^3-n}3+\frac{7n}{15}+\frac n3+\frac n5=\frac{n^5-n}5+\frac{n^3-n}3+n$$

Now, using Fermat's Little Theorem, $n^p-n\equiv0\pmod p$ for any integer $n$ and prime $p$

Similarly, $$\frac{n^7-n}7+\frac{n^5-n}5+\frac{n^3-n}3+n-\left(\frac n7+\frac n3+\frac n5\right)=\frac{n^7}7+\frac{n^5}5+\frac{n^3}3+\frac{34n}{105}$$ will be an integer

-
Great answer.. non-inductive proof is very usefull! Although the question was in an inductive guide, and therefore, I assumed I had to solve it by induction, it's nice to see there are many ways to solve the same problem. Thanks! – pmartelletti Jul 14 '13 at 18:26
@pmartelletti, my pleasure. To me, induction is just a verification of a proposition.I personally prefer non-inductive derivation – lab bhattacharjee Jul 14 '13 at 18:35
I'm sorry, but I don't understand from where do you get the first term.. why are you subtracting the I.H.? – pmartelletti Jul 14 '13 at 18:35
@pmartelletti, if $f(n)=\frac{n^5}5+\frac{n^3}3+\frac{7n}{15}$ (whcih is given) $f(n+1)=??$ Now, if $f(n+1)-f(n)$ is an integer, We find $f(n+1)=$integer +integer as we have assumed $f(n)$ to be integer – lab bhattacharjee Jul 14 '13 at 18:38
There we go.. great and detailed answer. I'm choosing @nrpeterson as the accepted answer as that's how teachers expect me to solve the exercise, with the tools the tought us. But yours was excellent, thanks a lot! – pmartelletti Jul 14 '13 at 18:46

There are many nice solutions here, so I struggle to give another one. But then again, most solutions use a trick as some neat rearranging or the Binomial theorem and I wanted to give a solution in a straightforward way, a way, in which maybe you would approach this:

1. Checking for some expression to be an integer usually reduces to some divisibility condition. Converting to a common denominator is a good start: $$\frac15x^5+\frac13x^3+\frac7{15}x=\frac3{15}x^5+\frac5{15}x^3+\frac7{15}x=\frac{3x^5+5x^3+7x}{15}$$ So, it boils down to proving, that $15$ divides $3x^5+5x^3+7x$.
2. $15=3\cdot 5$, so this is the same as proving both $$3\mid 3x^5+5x^3+7x$$ and $$5\mid 3x^5+5x^3+7x$$
3. This is where your knowledge about elementary number theory comes into play.

• If you do know Fermat's little theorem, you can easily conclude $x^3\equiv x\pmod{3}$ and $x^5\equiv x\pmod{5}$, which gives $$3x^5+5x^3+7x\equiv 3x^5+5x+7x\equiv 3x^5+12x\equiv 0x^5+0\equiv 0\mod 3$$ and similary for the other case.
• Otherwise - and this is a standard procedure for such divisibility problems on an elementary level - distinguish cases. If you want to investigate divisibility by $3$, then write $x$ either as $x=3k$, $x=3k+1$ or $x=3k+2$ and insert this into the above expression.

I won't do this here, because this method is a little tedious and I am sure, that you can do it. It might take some time, but this way is pretty straightforward and generally you will not fail.

-

Hint: Use $$(x+1)^n = x^n + \boxed{n} x^{n-1} + \frac 1 2 n(n-1) x^{n-2} +\cdots$$

-

Hint

$$5|(n+1)^5-n^5-1 \,.$$ $$3|(n+1)^3-n^3-1 \,.$$

Write $a=\frac{(n+1)^5-n^5-1}{5} \,;\, b=\frac{(n+1)^3-n^3-1}{3}$, and express $P(n+1)-P(n)$ in terms of $a,b$, where $P(n)=\frac{1}{5}n^5+\frac{1}{3}n³ + \frac{7}{15}n$.

To prove the Hint, you can use either Fermat Little Theorem or binomial Theorem.

-

A direct solution (without using induction), is to realize that

$$\frac{n^5}{5} + \frac{n^3}{3} + \frac{7n}{15} = \frac{ 3n^5 + 5n^2 -8 } { 15} + 1 = \frac{ n (n-1)(n+1)(3n^2 + 8 ) } { 15} + 1$$

$n(n-1)(n+1)$ is clearly a multiple of $3$ for all values of $n$.

$n(n-1)(n+1)$ is a multiple of $5$ if $n = 5k, 5k-1, 5k+1$.
$3n^2 + 8$ is a multiple of 5 if $n = 5k+2, 5k+3$.

Hence, this is an integer.

-