피보나치 수 구하기

$$피보나치\;수\;구하기$$

$$F_0\;=\;F_1\;=\;1,\;F_{n+1}\;=\;F_n\;+\;F_{n-1},\;n\;\geq\;1$$

$$1,\;1,\;2,\;3,\;5,\;8\;....$$

$$위와\;같은\;수열이\;피보나치\;수열이다.$$

$$f_0\;=\;0,\;f_1\;=\;1,\;f_{n+1}\;=\;f_n\;+\;f_{n-1},\;n\;\geq\;1$$

$$0,\;1,\;1,\;2,\;3,\;5,\;8\;....$$

$$편의를\;위해\;0\;부터\;시작하기도\;한다.$$

$$f_k+1\;=\;F_k,\;k\;>\;0$$

$$n\;번째\;피보나치\;수\;f_n\;은\;어떻게\;구할까?$$

$$f_2\;=\;f_1\;+\;f_0$$

$$f_3\;=\;f_2\;+\;f_1$$

$$...$$

$$f_{n-1}\;=\;f_{n-2}\;+\;f_{n-3}$$

$$f_{n}\;=\;f_{n-1}\;+\;f_{n-2}$$

$$n-1번\;계산하면\;구할\;수\;있다.$$

$$행렬\;연산을\;이용하면\;좀\;더\;효율적으로\;구할\;수\;있다.$$

$$A^n\;=\;\left(\begin{array}{cc} f_{n-1} & f_n \\ f_n & f_{n+1} \end{array}\right),\;n\;\geq\;1$$

$$피보나치\;행렬은\;위와\;같다.$$

$$A\;=\;\left(\begin{array}{cc} f_{0} & f_1 \\ f_1 & f_2 \end{array}\right)\;=\;\left(\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\right)$$

$$행렬\;곱의\;성질에\;의하면$$

$$A^{2n}\;=\;A^n\;\times\;A^n$$

$$A^2\;=\;A\;\times\;A\;=\;\left(\begin{array}{cc} f_0 & f_1 \\ f_1 & f_2 \end{array}\right)\left(\begin{array}{cc} f_0 & f_1 \\ f_1 & f_2 \end{array}\right)\;=\;\left(\begin{array}{cc} f_1 & f_2 \\ f_2 & f_3 \end{array}\right)$$

$$A^4\;=\;A^2\;\times\;A^2\;=\;\left(\begin{array}{cc} f_1 & f_2 \\ f_2 & f_3 \end{array}\right)\left(\begin{array}{cc} f_1 & f_2 \\ f_2 & f_3 \end{array}\right)\;=\;\left(\begin{array}{cc} f_3 & f_4 \\ f_4 & f_5 \end{array}\right)$$

$$A^8\;=\;A^4\;\times\;A^4\;=\;\left(\begin{array}{cc} f_3 & f_4 \\ f_4 & f_5 \end{array}\right)\left(\begin{array}{cc} f_3 & f_4 \\ f_4 & f_5 \end{array}\right)\;=\;\left(\begin{array}{cc} f_7 & f_8 \\ f_8 & f_9 \end{array}\right)$$

$$...$$

$$A^{2n}\;=\;A^n\;\times\;A^n\;=\;\left(\begin{array}{cc} f_n-1 & f_n \\ f_n & f_n+1 \end{array}\right)\left(\begin{array}{cc} f_n-1 & f_n \\ f_n & f_n+1 \end{array}\right)\;=\;\left(\begin{array}{cc} f_{2n-1} & f_{2n} \\ f_{2n} & f_{2n+1} \end{array}\right)$$

$$n\;이\;2^x\;의\;형태로\;표현되는\;수라면$$

$$f_n\;을\;구하기\;위해\;\log_2 n\;번\;계산하면\;된다.$$ 

$$n\;이\;2^x\;의\;형태로\;표현되는\;못하는\;수라면$$

$$A^{m+n}\;=\;A^m\;\times\;A^n$$

$$\left(\begin{array}{cc} f_m-1 & f_m \\ f_m & f_m+1 \end{array}\right)\left(\begin{array}{cc} f_n-1 & f_n \\ f_n & f_n+1 \end{array}\right)\;=\;\left(\begin{array}{cc} f_{m+n-1} & f_{m+n} \\ f_{m+n} & f_{m+n+1} \end{array}\right)$$

$$식을\;전개하면\;새로운\;성질을\;발견할\;수\;있다.$$

$$\left(\begin{array}{cc} f_{m+n-1} & f_{m+n} \\ f_{m+n} & f_{m+n+1} \end{array}\right)\;=\;\left(\begin{array}{cc} f_mf_n+f_{m-1}f_{n-1} & f_mf_{n+1}+f_{m-1}f_n \\ f_{m+1}f_n+f_mf_{n-1} & f_{m+1}f_{n+1}+f_mf_n \end{array}\right)$$

$$f_{m+n}\;=\;f_mf_{n+1}+f_{m-1}f_n$$

$$f_{m+n}\;=\;f_{m+1}f_n+f_mf_{n-1}$$

$$첫번째\;식을\;기준으로\;잡으면$$

$$m+n\;=\;(m+1)\;+\;(n-1)$$

$$f_{(m+1)+(n-1)}\;=\;f_{(m+1)}f_{(n-1)+1}+f_{(m+1)-1}f_{(n-1)}\;=\;f_{m+1}f_n+f_mf_{n-1}$$

$$이런\;성질들을\;응용하면\;차례대로\;구하지\;않고\;특정\;피보나치\;수를\;구할\;수\;있다.$$