3
$\begingroup$

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

  • 2
    Hint: You can take an $n^2$ out of each term, then you have ... That makes it work without induction.2011-09-16

4 Answers 4

7

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.

  • 0
    What is up with the 3| ?2011-09-16
  • 0
    @Pat: $\rm\ a\ |\ b\ $ means $\rm\:a\:$ divides $\rm\:b\ $ (standard number theory notation)2011-09-16
  • 0
    So a|b means b/a ?2011-09-16
  • 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\:.$2011-09-16
  • 0
    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.2011-09-16
  • 0
    @Pat: No, it means $\rm\:b\:$ is a multiple of $\rm\:a\:.\:$ It's simply a concise way to notate such divisibility or multiple relations (which are ubiquitous in number theory).2011-09-16
1

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$

  • 0
    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.2011-09-16
  • 0
    @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.2011-09-16
  • 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.2011-09-16
  • 0
    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 topic2011-09-16
  • 0
    You might check out http://math.stackexchange.com/questions/19485/dominoes-and-induction-or-how-does-induction-work/19488#194882011-09-16
1

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.

  • 0
    That's a very nice solution! :) Perhaps you should little more details.2011-09-16
  • 0
    @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.2011-09-27
  • 0
    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. :)2011-09-27
  • 0
    @Srivatsan Narayanan: Still thanks. And it will be great if you make it like a formal proof. Thanks again:)2011-10-04
0

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

  • 2
    First, this proof doesn't use induction :). Also, it's incomplete/incorrect. You forgot to discuss the case $n=0 \mod{3}$.2011-09-16
  • 0
    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 :)2011-09-16