피보나치 수열

피보나치 수열의 점화식은 다음과 같다.

$F_{n+2}=F_{n+1}+F_{n}$

 

$1\ 1\ 2\ 3\ 5\ 8\ 13\ \cdot\cdot\cdot$

잘 살펴보면 

$F_{4}=(F_{3})^{2}-(F_{1})^{2}$

$F_{6}=(F_{4})^{2}-(F_{2})^{2}$

가 성립하는 것을 알 수 있다. 그럼

성질 1: $F_{2n}=(F_{n+1})^{2}-(F_{n-1})^{2}$

가 성립하는 것일까? 증명해보자.

 

<성질 1 증명>

수열 $\left\{a_{n}\right\}$ 를 다음과 같이 정의한다.

$a_{n}=(F_{n+1})^{2}-(F_{n-1})^{2}$

$(F_{n+2})^{2}-(F_{n})^{2}$

$=(F_{n+1})^{2}+2F_{n+1}F_{n}-(F_{n-1})^{2}+(F_{n-1})^{2}$

$=a_{n}+2F_{n+1}F_{n}+(F_{n-1})^{2}$

$=a_{n}+2F_{n}(F_{n}+F_{n-1})+(F_{n-1})^{2}$

$=a_{n}+(F_{n})^{2}+(F_{n+1})^{2}$

$=a_{n}+F_{2n+1}$ ($\because$ 성질 2)

$a_{n+1}-a_{n}=F_{2n+2}-F_{2n}$

$a_{0}=0, F_{0}=0$ 이므로

 

# 이유가 궁금하면 클릭

$a_{0}=(F_{1})^{2}-(F_{-1})^{2}$

$F_{2}=F_{1}+F_{0}$

$F_{0}=0$

$F_{1}=F_{0}+F_{-1}$

$F_{-1}=1$

$\therefore a_{0}=0$

# 닫기

 

$a_{n+1}=F_{2n+2}$

$\therefore a_{n}=F_{2n}$

$\blacksquare$

 

<성질 2 증명>

$F_{2k+1}$

$=F_{2k}+F_{2k-1}$

$=2F_{2k-1}+F_{2k-2}$

$=3F_{2k-2}+2F_{2k-3}$

$=5F_{2k-3}+3F_{2k-4}$

$\cdot$

$\cdot$

$\cdot$

$=F_{i+1}F_{2k-i+1}+F_{i}F_{2k-i}$

$=(F_{k+1})^{2}+(F_{k})^{2}$

 

2번쨰 성질은 이미 1번째 성질을 증명하면서 증명해버렸다.

성질 2: $F_{2n+1}=(F_{n+1})^{2}+(F_{n})^{2}$

3번째 성질은 다음과 같다.

성질 3: $F_{n+1}F_{n+2}-F_{n}F_{n+3}=(-1)^{n}$

$\blacksquare$

 

<성질 3 증명>

수열 $\left\{b_{n}\right\}$를

$b_{n}=F_{n+1}F_{n+2}-F_{n}F_{n+3}$

로 정의한다.

위 식의 각 피보나치 항을 연속된 두 개의 피보나치 항으로 쪼갠다.

$=(F_{n}+F_{n-1})(F_{n+1}+F_{n})-(F_{n-1}+F_{n-2})(F_{n+1}+F_{n+2})$

$=F_{n-1}F_{n}-F_{n-2}F_{n+1}+F_{n}(F_{n+1}+F_{n})-F_{n+2}(F_{n-1}+F_{n-2})$

$=F_{n-1}F_{n}-F_{n-2}F_{n+1}=b_{n-2}$

이 뜻은 $n$이 홀수일때 모두 같고 짝수일 떄 모두 같다는 것을 의미한다.

그럼 우리는 $n$이 0일 때 1일 때를 알면 모든 경우를 알 수 있다.

$b_{0}=F_{1}F_{2}-F_{0}F_{3}=1$

$b_{1}=F_{2}F_{3}-F_{1}F_{4}=-1$

각 경우를 합쳐서 생각하면

$b_{n}=(-1)^{n}$

$\blacksquare$

---

<피보나치 수열의 일반항>

피보나치 수열의 일반항은 다음과 같다.

$F_{n}= {{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}} \over {2^{n}\sqrt{5}}}$

이를 간단하게 만들어보자.

각각을 이항정리를 이용하여 전개하면

 

<피보나치 수열의 조합적 성질>

점화식을 좀 더 살펴보자.

$F_{n}=F_{n-1}+F_{n-2}$

$=F_{n-2}+2F_{n-3}+F_{n-4}$

$=F_{n-3}+3F_{n-4}+3F_{n=5}+F_{n-6}$

이는 앞서 조합 포스팅에서 올렸던 형상과 같다.

$n$번 반복하면 다음을 얻는다.

$= _{n}C_{0}F_{0}+ _{n}C_{1}F_{-1}+\cdot\cdot\cdot+ _{n}C_{n}F_{-n}$

간단히 하면

사실 이 식은 계산하기에 별로 효율적인 식은 아니다. 좀 더 효율적이려면

이런식으로 되어야 할 것이다. 

 

<마치며>

이번 포스팅을 작성하면서 여러가지 재미있는 관찰을 하였다.

피사노 주기의 곱셈적 성질, 소수일 때의 피사노 주기, 5을 2차 비잉여로 가지는 소수들의 표현...

아직 연구해야할게 많이 남았다. 

이 연구는 LCY와의 협업으로 이루어졌습니다.