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.

$n^4 – 4n^2$ is divisible by $3$ for all $n \geq 0$.

Okay so the help earlier has been working on the questions up until now. I cannot figure out how to "factor" this one. So once I prove the base case for $n = 0$ (I also did for $n =1$) I proceed to the inductive step. However I'm a little confused.

Normally I understand that if we $S(N) = X$ condition. We do induction by, $S(N) + \text{(N +1 additive)} = S(N+ 1)$. However no idea how to do this here. I need help. <,< Sorry!

share|improve this question
2  
Hint: You can take an $n^2$ out of each term, then you have ... That makes it work without induction. –  Ross Millikan Sep 16 '11 at 4:40

4 Answers 4

HINT $\ $ Put $\rm\ f(n)\: =\: n^3 - 4\ n\:.\:$ To show that $\rm\ 3\ |\ n\ f(n)\:$ it suffices too show $\rm\ 3\ |\ f(n)\:.\:$ To prove this by induction note that $\rm\ 3\ |\ f(n+1)-f(n)\ =\ 3\ (n^2+n-1)\:.\: $ Therefore we deduce that

$\qquad$ since $\rm\ \ 3\ |\ f(n+1)-f(n),\ \ $ if $\rm\ \ 3\ |\ f(n)\: \ $ then $\rm\ \ 3\ |\ f(n+1)-f(n)+f(n) \ =\ f(n+1)$

which yields the inductive step, viz. $\rm\ 3\ |\ f(n)\ \Rightarrow\ 3\ |\ f(n+1)\:.\:$ The base step is: $\rm\:3\ |\ f(0)\: =\: 0\:.\:$

The same technique works very generally - see my many prior posts on telescopy.

share|improve this answer
    
What is up with the 3| ? –  oorosco Sep 16 '11 at 6:11
    
@Pat: $\rm\ a\ |\ b\ $ means $\rm\:a\:$ divides $\rm\:b\ $ (standard number theory notation) –  Bill Dubuque Sep 16 '11 at 6:13
    
So a|b means b/a ? –  oorosco Sep 16 '11 at 6:21
1  
@Pat: No, $\rm\:a\:$ divides $\rm\:b\:$ means $\rm\:b/a\:$ is an integer $\rm\:n\:,\:$ i.e. $\rm\ a\:n = b\:$ for some integer $\rm\:n\:.$ –  Bill Dubuque Sep 16 '11 at 6:24
    
Oh so a| b means that a is a multiple of b? Because in the equation above n would be the multiple required to make a equal b. Sorry that i'm confused, never saw this notation before. –  oorosco Sep 16 '11 at 6:27

Hint: To do it with induction, you have for $n=1, n^4-4n^2=-3, $ which is divisible by $3$ as you say. So assume $k^4-4k^2=3p$ for some $p$. You want to prove $(k+1)^4-4(k+1)^2=3q$ for some $q$. So expand it, insert the $3p$ you know about, and you should find the rest is divisible by $3$.

Added: as Srivatsan Narayanan points out, you will need that $n^3-n$ is divisible by $3$. We can just see that, as $n^3-n=(n-1)n(n+1)$ and one of them must be divisible by $3$. But suppose we don't see that. We can say $1^3-1=0$ is divisible by $3$. So suppose $k^3-k=3p$ Then we want to show $(k+1)^3-(k+1)=3q$. But $(k+1)^3-(k+1)=k^3+3k^2+3k+1-k-1=3p+3k^2+3k=3(p+k^2+k)$ so it is divisible by $3$

share|improve this answer
    
It's not that simple. The difference involves some multiples of 3, and then a $4(n^3-n)$. So you need to prove that $n^3-n$ is divisible by 3, presumably again by induction. –  Srivatsan Sep 16 '11 at 4:45
    
@Srivatsan Narayanan: You are right. If I were proving it, I wouldn't use induction at all (as in my comment). So having used it once, maybe I can get away with just factoring $n^3-n$, or maybe I do need to induct again. –  Ross Millikan Sep 16 '11 at 4:49
1  
Well, or there's this underhanded solution. One can rearrange $f(n+1)$ as $$f(n+1) = 2 f(n) - f(n-1) + 12n^2 - 6 .$$ Then applying strong induction will give the claim. I don't want to post this solution because unless motivated via second order differences ($f(n+1) - f(n) - (f(n) - f(n-1))$), this might look like a mysterious way to rearrange the polynomial. –  Srivatsan Sep 16 '11 at 4:53
    
Yeah which is why i'm having a problem here, not making much sense to me. <,< Induction is such a problem for me, having such a hard time grasping the topic –  oorosco Sep 16 '11 at 4:55
    
You might check out math.stackexchange.com/questions/19485/… –  Ross Millikan Sep 16 '11 at 4:58

Why not try n=0,n=1,n=2? Then you only need to do induction by, S(N)+(N +3 additive)=S(N+3).

Added: $(k+3)^4−4(k+3)^2=(k^4+4k^3\times 3+6k^2\times 3^2+4k\times3^3+3^4)-4(k^2+2k\times 3+3^2)$ $=k^4+3p-4(k^2+3q)=k^4-4k^2+3r$. So it is divisible by 3.

share|improve this answer
    
That's a very nice solution! :) Perhaps you should little more details. –  Srivatsan Sep 16 '11 at 5:07
    
@Srivatsan Narayanan: Can you help me to make it clear? English is not my mother tongue, and I also want to see how it is. Thanks in advance. –  puresky Sep 27 '11 at 5:05
    
I wrote my comment before you added more details to your solution, requesting you to elaborate your answer a bit ("Added: $(k+3)^4 - 4(k+3)^2 = \ldots$"). The comment is not that relevant anymore. :) –  Srivatsan Sep 27 '11 at 15:18
    
@Srivatsan Narayanan: Still thanks. And it will be great if you make it like a formal proof. Thanks again:) –  puresky Oct 4 '11 at 14:59

$n^{4}-4n^{2}=n^{2}(n^{2}-4)$. $n^2$ is always $1\bmod 3$ or $0\bmod 3$, so $n^2-4$ is $0\bmod 3$ in either cases.

share|improve this answer
2  
First, this proof doesn't use induction :). Also, it's incomplete/incorrect. You forgot to discuss the case $n=0 \mod{3}$. –  Srivatsan Sep 16 '11 at 5:06
    
Err thanks. :D but I gave this since the OP told he was not able to figure out factors.For the incompletion thing i am going to edit :) –  Dinesh Sep 16 '11 at 5:08

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.