피보나치 수열에 대하여

 

 

1. 피보나치 수열의 일반항

 

피보나치 수열은 마지막 두 항을 더하여 새로운 항을 만드는 수열이다.

 

$$ F_n = \{1, 1, 2, 3, 5, 8, 13, ...\} $$

 

피보나치 수열의 일반항을 쓰는 방법이 있는데, Binet's formula라고 부른다.

 

$$ F_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2}\right)^n - \left( \frac{1 - \sqrt{5}}{2}\right)^n \right) $$

 

수열의 유도 과정은 아래와 같다.

 

실수 $x$가 다음 방정식을 만족한다고 하자.

 

$$ x^2 = x + 1 $$

 

양변에 $x$를 곱하면

 

\begin{align}
x^3 &= x^2 + x \\
&= 2x + 1\end{align}

 

양변에 또 $x$를 곱하면

 

\begin{align}
x^4 &= 2x^2 + x \\
&= 2(x+1) + x \\
&= 3x + 2
\end{align}

 

양변에 또 $x$를 곱하면

 

\begin{align}
x^5 &= 3x^2 + 2x \\
&= 3(x+1) + 2x \\
&= 5x + 3
\end{align}

 

이 과정으로부터 아래가 됨을 유추할 수 있다.

 

$$ x^n = F_n x + F_{n-1} , n \ge 2 $$

 

위 식은 수학적 귀납법으로 증명할 수 있다. 우선 아래가 만족하며,

 

\begin{align}
x^2 = F_2 x + F_1 \\
x^3 = F_3 x + F_2
\end{align}

 

만약 아래를 만족한다면,

 

$$ x^n = F_n x + F_{n-1} $$

 

아래도

 

\begin{align}
x^{n+1} &= F_n x^2 + F_{n-1} x \\
&= F_n (x+1) + F_{n-1} x \\
&= (F_n + F_{n-1}) x + F_n \\
&= F_{n+1} x + F_n
\end{align}

 

만족한다.

■

 

처음에 나왔던 식

 

$$ x^2 = x + 1 $$

 

의 두 해를 각각 $\sigma$와 $\tau$라고 하면

 

$$\sigma = \frac{1+\sqrt{5}}{2}, \tau = \frac{1-\sqrt{5}}{2} $$

 

아래의 두 식이 정립한다.

 

\begin{align}
\sigma^n = F_n \sigma + F_{n-1} \\
\tau^n = F_n \tau + F_{n-1}
\end{align}

 

두 식의 차이는 아래와 같으므로

 

$$ \sigma^n - \tau^n = F_n (\sigma - \tau) $$

 

식을 정리하면 아래와 같다.

 

$$ F_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2}\right)^n - \left( \frac{1 - \sqrt{5}}{2}\right)^n \right) $$

■

 

---

 

피보나치 수열의 일반항은 구했으나 무리수가 들어있는 것이 살짝 불편하다. 이것을 정수로만 표현할 수 있다. 우선 아래와 같이 바꾸고,

 

$$ 2^n \sqrt{5} F_n =  \left(1 + \sqrt{5}\right)^n - \left( 1 - \sqrt{5}\right)^n $$

 

이항정리를 이용하면

 

\begin{align}
2^n \sqrt{5} F_n &= \sum_{r=0}^{n} \binom{n}{r} (\sqrt{5})^r - \sum_{r=0}^{n} \binom{n}{r} (-\sqrt{5})^r\\
&= \sum_{r=0}^{n} \binom{n}{r} \left( (\sqrt{5})^r - (-\sqrt{5})^r \right)\\
&= 2 \sqrt{5} \sum_{k=0}^{[n/2]} \binom{n}{2k+1} 5^k
\end{align} 

 

가 되므로 피보나치 수 $F_n$은 아래와 같이 쓸 수 있다.

 

\begin{align}
F_n = \frac{1}{2^{n-1}} \sum_{k=0}^{[n/2]} \binom{n}{2k+1} 5^k
\end{align} 

 

여기서 $[x]$는 $x$보다 크지 않은 최대 정수이다.

 

---

 

2. 피보나치 수열의 합

 

피보나치 수열의 첫 $n$개 항을 더하고 1을 더하면 $n+2$번째 피보나치 수가 된다.

 

Claim:

$$\sum_{k=1}^{n} F_k +1 = F_{n+2}$$

 

간단하게는 수학적 귀납법으로 증명 가능하다.

 

\begin{align}
&F_1 + F_2 + 1 &&= 3 = F_4 \\
&F_1 + F_2 + F_3 + 1 &&= 5 = F_5
\end{align} 

 

Suppose,

\begin{align}
F_1 + F_2 + \cdots + F_n + 1 = F_{n+2}
\end{align} 

 

Then,

\begin{align}
F_1 + F_2 + \cdots + F_n +F_{n+1} + 1 = F_{n+1} + F_{n+2} = F_{n+3} \\
\end{align}  

■

 

피보나치 수열의 일반항을 이용해서도 증명할 수 있다.

 

\begin{align}
\sigma := \frac{1+\sqrt{5}}{2}, \tau := \frac{1-\sqrt{5}}{2}
\end{align}

 

\begin{align}
F_n = \frac{1}{\sqrt{5}} \left( \sigma^n - \tau^n \right)
\end{align}

 

Then,

\begin{align}
\sum_{k=1}^{n} F_k  &= \frac{1}{\sqrt{5}} \sum_{k=1}^{n} \left( \sigma^k - \tau^k \right)\\
&= \frac{1}{\sqrt{5}} \left( \frac{\sigma (1-\sigma^n)}{1-\sigma} - \frac{\tau (1-\tau^n)}{1-\tau} \right) \\
&= \frac{1}{\sqrt{5}} \left( -(1+\sigma) (1-\sigma^n) + (1+\tau) (1-\tau^n) \right) \\
&= \frac{1}{\sqrt{5}} \left( -\sqrt{5} + (\sigma^n - \tau^n) + (\sigma^{n+1} - \tau^{n+1}) \right) \\
&= -1 + F_n + F_{n+1}\\
&= -1 + F_{n+2}
\end{align} 

■

 

사실 이 내용은 첫 두 항이 1, 1이 아니어도 +1만 적당히 바꾸면 성립한다. 수학적 귀납법 증명 과정을 보면 자명하다.

 

---

 

피보나치 수열의 $F_2$부터 $F_{2n}$까지 짝수번째 항을 모두 더하고 1을 더하면 $F_{2n+1}$이다.

 

Claim:

$$\sum_{k=1}^{n} F_{2k} +1 = F_{2n+1}$$

 

수학적 귀납법으로 증명 가능하다.

 

\begin{align}
&F_2 + F_4 + 1 &&= 5 = F_5 \\
&F_2 + F_4 + F_6 + 1 &&= 13 = F_7
\end{align} 

 

Suppose,

\begin{align}
F_2 + F_4 + \cdots + F_{2n} + 1 = F_{2n+1}
\end{align} 

 

Then,

\begin{align}
F_2 + F_4 + \cdots + F_{2n} +F_{2n+2} + 1 = F_{2n+1} + F_{2n+2} = F_{2n+3} \\
\end{align}  

■

 

---

 

 

피보나치 수열의 $F_3$부터 $F_{2n+1}$까지 홀수번째 항을 모두 더하고 1을 더하면 $F_{2n+2}$이다.

 

Claim:

$$\sum_{k=1}^{n} F_{2k+1} +1 = F_{2n+2}$$

 

수학적 귀납법으로 증명 가능하다.

 

\begin{align}
&F_3 + F_5 + 1 &&= 8 = F_6 \\
&F_3 + F_5 + F_7 + 1 &&= 21 = F_8
\end{align} 

 

Suppose,

\begin{align}
F_3 + F_5 + \cdots + F_{2n+1} + 1 = F_{2n+2}
\end{align} 

 

Then,

\begin{align}
F_3 + F_5 + \cdots + F_{2n+1} +F_{2n+3} + 1 = F_{2n+2} + F_{2n+3} = F_{2n+4} \\
\end{align}  

■

 

---

 

3. 피보나치 수열의 연속된 항의 비율

 

피보나치 수열에서 연속된 두 항의 비율은 $(1+\sqrt{5})/2$로 수렴한다.

일반항 표현식으로 증명 가능하다.

 

\begin{align}
\sigma := \frac{1+\sqrt{5}}{2}, \tau := \frac{1-\sqrt{5}}{2} \to \left| \frac{\tau}{\sigma} \right| = \left| \frac{\sqrt{5}-3}{2} \right| <1
\end{align} 

\begin{align}
F_n = \frac{1}{\sqrt{5}} \left( \sigma^n - \tau^n \right)
\end{align}

 

Then,

 

\begin{align}
\frac {F_{n+1}}{F_n} &= \frac{\sigma^{n+1}-\tau^{n+1}}{\sigma^n-\tau^n}\\
&=\frac{\sigma - \left( \tau/\sigma \right)^{n+1}}{1-\left( \tau/\sigma\right)^n} \\
\end{align} 

 

\begin{align}
\therefore \lim_{n\to\infty} \frac{F_{n+1}}{F_n} = \sigma
\end{align}

■

 

---

 

 

Fun fact: 사실 피보나치 수열의 첫 두 항을 아무렇게나 잡아도, 연속된 항의 비율은 $(1+\sqrt{5})/2$로 수렴한다. (첫 두 항 중 적어도 하나는 0이 아니어야 한다.) 아이디어는 이곳에서 가져왔다.

 

피보나치 수열의 첫 두 항이 $a$, $b$인 피보나치 수열을 $F_{(a,b)}$라고 쓰면, 이 수열은 아래와 같다.

 

\begin{align}
F_{(a,b)} = a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b, \cdots 
\end{align}

 

각 항에서 $a$와 $b$의 계수를 보면 계수가 피보나치 수열임을 알 수 있다.

 

 

 

이제 이 일반화된 피보나치 수열은 아래와 같이 쓸 수 있다.

 

\begin{align}
F_{(a,b)}(n) &= a F_{(1,0)}(n) + b F_{(0,1)} (n)\\
&= \frac{1}{\sqrt{5}} \left( a(\sigma^{n-2} - \tau^{n-2} ) +b (\sigma^{n-1} - \tau^{n-1} ) \right)
\end{align} 

 

연속된 두 항의 비율은

 

\begin{align}
\frac{F_{(a,b)}(n+1)}{F_{(a,b)}(n)} 
&= \frac{ a(\sigma^{n-1} - \tau^{n-1} ) +b (\sigma^{n} - \tau^{n} ) }
{  a(\sigma^{n-2} - \tau^{n-2} ) +b (\sigma^{n-1} - \tau^{n-1} ) }\\
&=\frac{ a(\sigma - \tau \left(\frac{\tau}{\sigma}\right)^{n-2} ) +b (\sigma^{2} - \tau^{2} \left(\frac{\tau}{\sigma}\right)^{n-2}   )  }{  a(1 - \left(\frac{\tau}{\sigma}\right)^{n-2} ) +b (\sigma - \tau \left(\frac{\tau}{\sigma}\right)^{n-2} ) }
\end{align}

 

이 값의 극한은

 

\begin{align}
\lim_{n\to\infty} \frac{F_{(a,b)}(n+1)}{F_{(a,b)}(n)} 
=\frac{ a(\sigma) +b (\sigma^{2})}{a(1) +b (\sigma) } =\sigma
\end{align} 

■

 

 

끗