피보나치 수열에 대하여

 

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

$$x^2=x+1$$

 

양변에 $x$를 곱하면

 

$$\begin{array}{rl}{x}^3& =x^2+x\\ & =2x+1\end{array}$$

 

양변에 또 $x$를 곱하면

 

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

 

양변에 또 $x$를 곱하면

 

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

 

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

 

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

 

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

 

$$\begin{array}{r}{x}^2=F_{2}x+F_1\\ x^3=F_{3}x+F_2\end{array}$$

 

만약 아래를 만족한다면,

 

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

 

아래도

 

$$\begin{array}{rl}{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{array}$$

 

만족한다.

■

 

처음에 나왔던 식

 

$$x^2=x+1$$

 

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

 

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

 

아래의 두 식이 정립한다.

 

$$\begin{array}{r}{\sigma }^n=F_n\sigma +F_{n-1}\\ {\tau }^n=F_n\tau +F_{n-1}\end{array}$$

 

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

 

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

 

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

 

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

■

 

---

 

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

 

$$2^n\sqrt{5}{F}_n={(1+\sqrt{5})}^n-{(1-\sqrt{5})}^n$$

 

이항정리를 이용하면

 

$$\begin{array}{rl}{2}^n\sqrt{5}{F}_n& =\sum _{r=0}^n(\genfrac{}{}{0ex}{}{n}{r})(\sqrt{5}{)}^r-\sum _{r=0}^n(\genfrac{}{}{0ex}{}{n}{r})(-\sqrt{5}{)}^r\\ & =\sum _{r=0}^n(\genfrac{}{}{0ex}{}{n}{r})((\sqrt{5}{)}^r-(-\sqrt{5}{)}^r)\\ & =2\sqrt{5}\sum _{k=0}^{[n/2]}(\genfrac{}{}{0ex}{}{n}{2k+1})5^k\end{array}$$ 

 

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

 

$$\begin{array}{r}{F}_n=\frac{1}{2^{n-1}}\sum _{k=0}^{[n/2]}(\genfrac{}{}{0ex}{}{n}{2k+1})5^k\end{array}$$ 

 

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

 

---

 

2. 피보나치 수열의 합

 

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

 

Claim:

$$\sum _{k=1}^n{F}_k+1=F_{n+2}$$

 

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

 

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

 

Suppose,

$$\begin{array}{r}{F}_1+F_2+\cdots +F_n+1=F_{n+2}\end{array}$$ 

 

Then,

$$\begin{array}{r}{F}_1+F_2+\cdots +F_n+F_{n+1}+1=F_{n+1}+F_{n+2}=F_{n+3}\end{array}$$  

■

 

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

 

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

 

$$\begin{array}{r}{F}_n=\frac{1}{\sqrt{5}}({\sigma }^n-{\tau }^n)\end{array}$$

 

Then,

$$\begin{array}{rl}\sum _{k=1}^n{F}_k& =\frac{1}{\sqrt{5}}\sum _{k=1}^n({\sigma }^k-{\tau }^k)\\ & =\frac{1}{\sqrt{5}}(\frac{\sigma (1-{\sigma }^n)}{1-\sigma }-\frac{\tau (1-{\tau }^n)}{1-\tau })\\ & =\frac{1}{\sqrt{5}}(-(1+\sigma )(1-{\sigma }^n)+(1+\tau )(1-{\tau }^n))\\ & =\frac{1}{\sqrt{5}}(-\sqrt{5}+({\sigma }^n-{\tau }^n)+({\sigma }^{n+1}-{\tau }^{n+1}))\\ & =-1+F_n+F_{n+1}\\ & =-1+F_{n+2}\end{array}$$ 

■

 

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

 

---

 

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

 

Claim:

$$\sum _{k=1}^n{F}_{2k}+1=F_{2n+1}$$

 

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

 

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

 

Suppose,

$$\begin{array}{r}{F}_2+F_4+\cdots +F_{2n}+1=F_{2n+1}\end{array}$$ 

 

Then,

$$\begin{array}{r}{F}_2+F_4+\cdots +F_{2n}+F_{2n+2}+1=F_{2n+1}+F_{2n+2}=F_{2n+3}\end{array}$$  

■

 

---

 

 

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

 

Claim:

$$\sum _{k=1}^n{F}_{2k+1}+1=F_{2n+2}$$

 

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

 

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

 

Suppose,

$$\begin{array}{r}{F}_3+F_5+\cdots +F_{2n+1}+1=F_{2n+2}\end{array}$$ 

 

Then,

$$\begin{array}{r}{F}_3+F_5+\cdots +F_{2n+1}+F_{2n+3}+1=F_{2n+2}+F_{2n+3}=F_{2n+4}\end{array}$$  

■

 

---

 

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

 

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

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

 

$$\begin{array}{r}\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{array}$$ 

$$\begin{array}{r}{F}_n=\frac{1}{\sqrt{5}}({\sigma }^n-{\tau }^n)\end{array}$$

 

Then,

 

$$\begin{array}{rl}\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{array}$$ 

 

$$\begin{array}{r}\therefore \underset{n\to \mathrm{\infty }}{lim}\frac{F_{n+1}}{F_n}=\sigma \end{array}$$

■

 

---

 

 

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

 

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

 

$$\begin{array}{r}{F}_{(a,b)}=a,b,a+b,a+2b,2a+3b,3a+5b,5a+8b,\cdots \end{array}$$

 

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

 

 

 

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

 

$$\begin{array}{rl}{F}_{(a,b)}(n)& =a{F}_{(1,0)}(n)+b{F}_{(0,1)}(n)\\ & =\frac{1}{\sqrt{5}}(a({\sigma }^{n-2}-{\tau }^{n-2})+b({\sigma }^{n-1}-{\tau }^{n-1}))\end{array}$$ 

 

연속된 두 항의 비율은

 

$$\begin{array}{rl}\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{array}$$

 

이 값의 극한은

 

$$\begin{array}{r}\underset{n\to \mathrm{\infty }}{lim}\frac{F_{(a,b)}(n+1)}{F_{(a,b)}(n)}=\frac{a(\sigma )+b({\sigma }^2)}{a(1)+b(\sigma )}=\sigma \end{array}$$ 

■

 

 

끗