Post

피보나치 수

0,1,1,2,3,5,8,13,21,34,55,

피보나치 수 는 다음 점화식으로 정의된다.

F0=0 F1=1 Fi=Fi1+Fi2(i2)

보통 피보나치 수를 구할 때 앞에서부터 두항 씩 더해 구해나갈텐데, 다음 성질을 이용해서 구하는 방법도 있다.

피보나치 수는 황금률 ϕ와 그 켤레수 ϕ^와 관련이 있다. ϕϕ^는 다음 방정식의 두 근이다. x2=x+1 ϕ=1+52ϕ^=152

두 근에 대해 다음 식이 성립한다.

Fi=ϕiϕi^5 * 이는 수학적 귀납법으로 증명할 수 있다.

|ϕi^|<1이므로 |ϕi^|5<15<12이고, 따라서 다음과 같음을 알 수 있다. Fi=ϕi5+12 즉, Fiϕi/5를 가장 가까운 정수로 반올림한 값과 같다. 따라서 피보나치 수는 지수적으로 증가한다.

This post is licensed under CC BY 4.0 by the author.