Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

6 Answers 6

up vote 2 down vote accepted

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.

share|improve this answer
    
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. :-) ) –  Nicholas R. 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

share|improve this answer
    
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
1  
@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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.