피보나치 수

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
피보나치 수를 이용한 사각형 채우기

피보나치 수(영어: Fibonacci Numbers)수학에서 아래의 점화식으로 정의되는 수열이다.

피보나치 수렴 그래프

피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다. n = 0, 1,...에 해당하는 피보나치 수는 (OEIS의 수열 A000045)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...

이다.

역사[편집]

피보나치 수가 처음 언급된 문헌은 기원전 5세기 인도수학자 핑갈라가 쓴 책이다. 한편 유럽에서 피보나치 수를 처음 연구한 것은 레오나르도 피보나치토끼 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다. n 번째 달의 토끼 수는

  • 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
  • 두 달 이상이 된 토끼는 번식 가능하다.
  • 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
  • 토끼는 죽지 않는다.

따라서 첫 달에는 새로 태어난 토끼 한 쌍이 있고, 두 번째 달에는 그대로 토끼 한 쌍, 세 번째 달부터는 이 토끼 한 쌍이 새끼를 낳게 되어 토끼가 2쌍이 되고, 네 번째 달에는 3쌍, 다섯 번째 달에는 5쌍이 된다. 이때 n번째 달에 a 쌍의 토끼가 있었고, 다음 n+1번째 달에는 새로 태어난 토끼를 포함해 b쌍이 있었다고 하자. 그러면 그다음 n+2 번째 달에는 a+b 쌍의 토끼가 있게 된다. 이는 n번째 달에 살아있던 토끼는 충분한 나이가 되어 새끼를 낳을 수 있지만, 바로 전 달인 n+1번째 달에 막 태어난 토끼는 아직 새끼를 낳을수 없기 때문이다.

피보나치 수의 성질[편집]

피보나치 수의 생성함수

로 정리된다. 이 식으로부터 n번째 피보나치 수는 간단히

로 정리된다. 이 식은 레온하르트 오일러1765년 처음 발표했으나 잊혔다가, 1848년 자크 비네에 의해 재발견되었다. 이 식을 비네의 식 또는 비네의 공식이라고 부른다. 황금비 값을 라 하면

라 적을 수도 있다.

피보나치 수의 정의를 음의 정수에 대해 확장할 수 있다. 음의 정수 -n에 대해

라 정의하면 이 값은 위의 점화식과 비네의 식을 모두 만족한다.

또한, 피보나치 수열은 서로 인접한 항끼리 서로소이다. 이것은 귀납법으로 간단히 증명할 수 있다.

피보나치 수열의 인접한 두 항의 비()는 황금비(1.618033988749894848...)에 수렴하는 성질이 있다.[1]

FibonacciNumbers001.svg

피보나치 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...을 가지고 직접 이웃한 항 간 비율을 계산해 보면,

1÷1 = 1.00000 00000... 2÷1 = 2.00000 00000... 3÷2 = 1.50000 00000... 5÷3 = 1.66666 66666... 8÷5 = 1.60000 00000... 13÷8 = 1.62500 00000... 21÷13 = 1.61538 46153... 34÷21 = 1.61904 76190... 55÷34 = 1.61764 70588... 89÷55 = 1.61818 18181... 144÷89 = 1.61797 75280... 233÷144 = 1.61805 55555... 로 점점 황금비(대략 1.618)에 수렴하는 것을 알 수 있다.

피보나치 수열의 인접한 두 항의 비가 황금비 상수 에 수렴할때, 그 비율은 교대로 황금비보다 커졌다 작아졌다 하며 접근하는 성질이 있다.

피보나치 수 구하기[편집]

피보나치 수를 컴퓨터 등에서 구할 때는 피보나치 수의 정의를 이용하여 부터 차례대로 앞의 두 항을 더해서 얻는 방법과 비네의 공식을 이용하는 방법이 있다.

n 값에 대해서는 다음의 행렬 연산식을 이용해서 빨리 구할 수 있다.

피보나치 수를 구하는 다른 코드는 피보나치 수 프로그램을 참고하라.

항등식[편집]

  • (카시니의 항등식)

같이 보기[편집]

외부 링크[편집]

각주[편집]