- #1

issacnewton

- 1,026

- 36

- Homework Statement
- Prove that ##n##th Fibanacci number ##F_n## is even if and only if ##3|n##

- Relevant Equations
- Mathematical Induction

Let ##P(n)## be the statement that

$$ F_n \text{ is even} \iff (3 \mid n) $$

Now, my base cases are ##n=1,2,3##. For ##n=1##, statement I have to prove is

$$ F_1 \text{ is even} \iff (3 \mid 1) $$

But since ##F_1 = 1## (Hence ##F_1## not even) and ##3 \nmid 1##, the above statement is vacuously true. Now, for ##n=2##, statement is

$$ F_2 \text{ is even} \iff (3 \mid 2) $$

But, since ##F_2 = 1## (Hence ##F_2## not even) and ##3 \nmid 2##, the above statement is vacuously true. Lastly, for ##n=3##, statement is

$$ F_3 \text{ is even} \iff (3 \mid 3) $$

Since ##F_3=2##, we have ##F_3## as even and ##3 \mid 3 ##. Since both antecedent and consequent are true, the biconditional is true. So, base cases are true. Now, let ## k \geqslant 3## be an arbitrary in ##\mathbb{N}##. And suppose that ##P(m)## is true for ##1 \leqslant m \leqslant k##. i.e.

$$ F_m \text{ is even} \iff (3 \mid m) $$

for ##1 \leqslant m \leqslant k##. I have to prove that ##P(k+1)## is true. I have to prove that

$$ F_{k+1} \text{ is even} \iff (3 \mid k+1) $$

Since this is biconditional statement, I will first prove forward direction

$$ F_{k+1} \text{ is even} \to (3 \mid k+1) $$

Suppose that ##F_{k+1}## is even. Now, ##F_{k+1} = F_k + F_{k-1} = 2 F_{k-1} + F_{k-2}##. Using this, I must have ##F_{k-2}## as even. Since ##k \geqslant 3##, it implies ##1 \leqslant k-2 \leqslant k##. Now, I can use the inductive hypothesis and conclude that ##3 \mid (k-2)##. This means that ##k-2 = 3 \alpha## for some ##\alpha \in \mathbb{Z}##. It follows that ##k +1 = 3 (\alpha + 1)## and ##3 \mid (k+1)##.

This proves the forward direction. Now, I have to prove the reverse direction

$$ (3 \mid k+1) \to F_{k+1} \text{ is even} $$

Suppose ##3 \mid (k+1)##. I will try to prove this with contradiction, so assume the opposite of consequent. Hence suppose that ##F_{k+1}## is odd. Since ##F_{k+1} = 2 F_{k-1} + F_{k-2}##, it must be true that ##F_{k-2}## is odd. As before, since ##1 \leqslant k-2 \leqslant k##, using contrapositive of inductive hypothesis

$$ (F_{k-2} \text{ is odd}) \to (3 \nmid k-2)$$

Hence, it must be true that ##3 \nmid (k-2)##. But, as ##3 \mid (k+1)##, I have ## (k+1) = 3 \alpha## and ##(k-2) = 3(\alpha -1)##. This means that ##3 \mid (k-2)##. But this is a contradiction. So, initial assumption that ##F_{k+1}## is odd, is wrong. Hence ##F_{k+1}## is even. This proves the reverse direction. Hence

$$ F_{k+1} \text{ is even} \iff (3 \mid k+1) $$

So, ##P(k+1)## is true. Using strong induction, this means that ##P(n)## is true for all ##n \in \mathbb{N}##.

Is this a correct proof ?

Thanks ##\smile##

$$ F_n \text{ is even} \iff (3 \mid n) $$

Now, my base cases are ##n=1,2,3##. For ##n=1##, statement I have to prove is

$$ F_1 \text{ is even} \iff (3 \mid 1) $$

But since ##F_1 = 1## (Hence ##F_1## not even) and ##3 \nmid 1##, the above statement is vacuously true. Now, for ##n=2##, statement is

$$ F_2 \text{ is even} \iff (3 \mid 2) $$

But, since ##F_2 = 1## (Hence ##F_2## not even) and ##3 \nmid 2##, the above statement is vacuously true. Lastly, for ##n=3##, statement is

$$ F_3 \text{ is even} \iff (3 \mid 3) $$

Since ##F_3=2##, we have ##F_3## as even and ##3 \mid 3 ##. Since both antecedent and consequent are true, the biconditional is true. So, base cases are true. Now, let ## k \geqslant 3## be an arbitrary in ##\mathbb{N}##. And suppose that ##P(m)## is true for ##1 \leqslant m \leqslant k##. i.e.

$$ F_m \text{ is even} \iff (3 \mid m) $$

for ##1 \leqslant m \leqslant k##. I have to prove that ##P(k+1)## is true. I have to prove that

$$ F_{k+1} \text{ is even} \iff (3 \mid k+1) $$

Since this is biconditional statement, I will first prove forward direction

$$ F_{k+1} \text{ is even} \to (3 \mid k+1) $$

Suppose that ##F_{k+1}## is even. Now, ##F_{k+1} = F_k + F_{k-1} = 2 F_{k-1} + F_{k-2}##. Using this, I must have ##F_{k-2}## as even. Since ##k \geqslant 3##, it implies ##1 \leqslant k-2 \leqslant k##. Now, I can use the inductive hypothesis and conclude that ##3 \mid (k-2)##. This means that ##k-2 = 3 \alpha## for some ##\alpha \in \mathbb{Z}##. It follows that ##k +1 = 3 (\alpha + 1)## and ##3 \mid (k+1)##.

This proves the forward direction. Now, I have to prove the reverse direction

$$ (3 \mid k+1) \to F_{k+1} \text{ is even} $$

Suppose ##3 \mid (k+1)##. I will try to prove this with contradiction, so assume the opposite of consequent. Hence suppose that ##F_{k+1}## is odd. Since ##F_{k+1} = 2 F_{k-1} + F_{k-2}##, it must be true that ##F_{k-2}## is odd. As before, since ##1 \leqslant k-2 \leqslant k##, using contrapositive of inductive hypothesis

$$ (F_{k-2} \text{ is odd}) \to (3 \nmid k-2)$$

Hence, it must be true that ##3 \nmid (k-2)##. But, as ##3 \mid (k+1)##, I have ## (k+1) = 3 \alpha## and ##(k-2) = 3(\alpha -1)##. This means that ##3 \mid (k-2)##. But this is a contradiction. So, initial assumption that ##F_{k+1}## is odd, is wrong. Hence ##F_{k+1}## is even. This proves the reverse direction. Hence

$$ F_{k+1} \text{ is even} \iff (3 \mid k+1) $$

So, ##P(k+1)## is true. Using strong induction, this means that ##P(n)## is true for all ##n \in \mathbb{N}##.

Is this a correct proof ?

Thanks ##\smile##