2
$\begingroup$

Prove that the following holds: $3|F_n$ if and only if $4|n$

Base case for $n=1$:

$F_1$=1, so $F_1$ is not divisible by 3 and 1 is not divisble by 4.

So the proposition holds for $k=1$

Continue for n=2, n=3 and n=4.

Inductive step

Assume $3|F(4k)$. We now have to prove that the proposition also holds for $4(k+1)=4k+4$.

$F(4k+4)=F(4k+3)+F(4k+2)=2F(4k+2)+F(4k+1)=3F(4k+1)+2F(4k)=5F(4k)+3F(4k-1)$

$5F(4k)$ is divisible by 3 by our hypothesis and it is obvious that $3F(4k-1)$ is divisible by 3.

$F(4k+3)=3F(4k)+2F(4k-1)$

$3F(4k)$ is divisble by 3 by our hypothesis and since $n$ already is a multiple of 4 $(n-1)$ can't possibly be a multiple of 4 to. So by our hypothesis $2F(4k-1)$ is not divisible by 3 and thus $F(4k+3)$ is not divisible by 3.

I continue the proof for $F(4k+2)$ and $F(4k+1)$ and conclude that by induction $3|F_n$ holds if $4|n$ holds, but the proposition involves a bi-implication, so I need to prove that $4|n$ holds if $3|F_n$ holds. However, I don't know where to begin.

I also think my proof is too lengthy. So I would like to know if there is a simpler, more elegant way to prove the proposition (induction is not required).

$\endgroup$
1
  • $\begingroup$ Please do not deface your question by removing essential parts. In the worst cases that is called vandalism in these parts. $\endgroup$ – Jyrki Lahtonen Feb 19 '15 at 6:46
1
$\begingroup$

Consider the sequence $R_k$ of reminders modulo 3 instead.

This is: $$ R_1 = 1\\ R_2 = 1\\ R_3 = 2\\ R_4 = 0\\ R_5 = 2\\ R_6 = 2\\ R_7 = 1\\ R_8 = 0\\ $$ and the values repeat exactly. Hence $R_k = 0\iff 4|k$.

$\endgroup$
4
  • $\begingroup$ No, the values do not repeat exactly. $F_5 \equiv 2$ not $1$. $\endgroup$ – Mark Fischler Nov 10 '14 at 19:48
  • $\begingroup$ @MarkFischler thanks. $\endgroup$ – mookid Nov 10 '14 at 19:55
  • $\begingroup$ How do I prove that the remainders form a repeating sequence? $\endgroup$ – Collin Nov 10 '14 at 20:06
  • $\begingroup$ @Mark this is a very easy induction. The point is that $(R_9, R_{10},R_{11}) = (R_0,R_1,R_2)$. $\endgroup$ – mookid Nov 10 '14 at 20:07
0
$\begingroup$

Along the lines off mookid:

Lemma: In mod 3 arithmetic, for all $k \in \Bbb{N}$, $$ \begin{array}{c} F_{8k-7} \equiv 1 \\ F_{8k-6} \equiv 1 \\ F_{8k-5} \equiv 2 \\ F_{8k-4} \equiv 0 \\ F_{8k-3} \equiv 2 \\ F_{8k-2} \equiv 2 \\ F_{8k-1} \equiv 1 \\ F_{8k} \equiv 0 \\ \end{array} $$ Proof: The basis is trivially established by inspecting $F_1$ through $F_8$. Assume the Lemma for $k$. Then $$ \begin{array}{c} F_{8(k+1)-7} = F_{8k+1} \equiv F_{8k} + F_{8k-1} = 0+1 = 1 \\ F_{8(k+1)-6} = F_{8k+2} \equiv F_{8k+1} + F_{8k} = 1+0 = 1 \\ F_{8(k+1)-5} = F_{8k+3} \equiv F_{8k+2} + F_{8k+1} = 1+1 = 2 \\ F_{8(k+1)-4} = F_{8k+4} \equiv F_{8k+3} + F_{8k+2} = 2+1 = 0 \\ F_{8(k+1)-3} = F_{8k+5} \equiv F_{8k+4} + F_{8k+3} = 0+2 = 2 \\ F_{8(k+1)-2} = F_{8k+6} \equiv F_{8k+5} + F_{8k+4} = 2+0 = 2 \\ F_{8(k+1)-1} = F_{8k+7} \equiv F_{8k+6} + F_{8k+5} = 2+2 = 1 \\ F_{8(k+1)} = F_{8k+8} \equiv F_{8k+7} + F_{8k+6} = 2+1 = 0 \end{array} $$ This establishes induction so the lemma is true. Finally, the theorem to be proved can be read from the lemma, by noting that only $F_{8k-4}$ and $F_{8k}$ are zero mod $3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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