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 $\displaystyle u_n$ is even if 3 divides $\displaystyle n$.

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

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

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

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

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

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

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

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

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

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

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