수열의 귀납적 정의

Let $P( n )$ be, “$f_{4n}$ is a multiple of 3.” Since $f_4 = 3$, $P( 1 )$ is true. If $P( k )$ is true, then there exists an integer $m$ such that $f_{4k} = 3m$. We now need to prove that $P(k+1)$ is true or that $f_{4(k+1)}$ is a multiple of 3. We use the following:

$$\begin{aligned}f_{4 \left( k + 1 \right)} & = f_{4k + 4} \\ & = f_{4k+3} + f_{4k+2} \\ & = \left( f_{4k+2} + f_{4k+1} \right) + \left( f_{4k+1} + f_{4k} \right) \\ & = f_{4k+2} + 2 f_{4k+1} + f_{4k} \\ & = \left( f_{4k+1} + f_{4k} \right) + 2 f_{4k+1} + f_{4k} \\ & = 3f_{4k + 1} + 2f_{4k}\end{aligned}$$

We now use the assumption that $f_{4k} = 3m$ and the last equation to obtain $f_{4(k+1)} = 3f_{4k + 1} + 2\cdot 3m$ and hence, $f_{4(k+1)} = 3 \left( f_{4k +1} + 2m \right)$. Therefore, $f_{4(k+1)}$ is a multiple of 3 and this completes the proof of the inductive step.