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

  • 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