# Math Help - Fibonacci proof

1. ## Fibonacci proof

Here is my latest problem. Little help please. NOTE: u(n) is read u "sub" n

Prove by induction that u(n) is even if 3 divides n. In addition I also have a logic question just in reading this problem.

Is (3 divides n implies u(n) is even) the same thing as
u(n) is even if 3 divides n.

Your interpretation of that implication is correct.

Prove by induction that $u_n$ is even if 3 divides $n$.

We wish to prove that: .If $n = 3k$, then $u_n$ is even.

Verify $S(1)\!:\;k = 1,\:n = 3\quad\Rightarrow\quad u_3 \:=\:2$ . . . True!

Assume $S(k)$ is true: . $u_{3k} \:=\:2a$ for some integer $a.$

. . and we wish to prove that: . $u_{3(k+1)}$ is even.

We have: . $u_{3(k+1)} \;=\;u_{3k+3}$

. . . . . . . . . . . . $= \;\underbrace{u_{3k+2}} +\, u_{3k+1}$

. . . . . . . . . . $=\;\overbrace{\left(u_{3k+1} + u_{3k}\right)} +\, u_{3k+1}$

. . . . . . . . . . $=\;2\!\cdot\!u_{3k+1} + \underbrace{u_{3k}}_{\text{This is }2a}$

. . . . . . . . . . $= \;2\!\cdot\!u_{3k+1} + 2a$

. . . . . . . . . . $= \;2\left(u_{3k+1} + a\right)$

Therefore: . $u_{3(k+1)}$ is even.