# Proving $n^4-4n^2$ is divisible by $3$ using induction

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

-
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

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.

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

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

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

-
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