피보나치 수(Fibonacci number)이란?

피보나치 수열는 피보나치가 토끼의 성장과 번식을 관찰하다가 발견한 수열이라고 합니다.

피보나치 수(Fibonacci number)의 정의는 간단합니다.

0과 1로 시작해서 덧셈을 계속 이어가면 얻어지는 수들입니다.

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

초항을 제 0항으로 하고 제 0항, 제 1항, 제 2항, ...... 순으로 나열하면

    F(0),  F(1),  F(2),  F(3),  F(4), F(5),  F(6),  F(7),  F(8),  F(9),  F(10), ......

이 되고, 번호를 괄호 속에 넣지 않고 우측 첨자로 붙여 나열하면,

    F₀,  F₁,  F₂,  F₃,  F₄,  F₅,  F₆,  F₇,  F₈,  F₉,  F₁₀, ......

이 됩니다.  즉, 

                  F₀ = F(0) = 0

                  F₁ = F(1) = 1

                  F₂ = F(2) = 1

                  F₃ = F(3) = 2

                  F₄ = F(4) = 3

                  F₅ = F(5) = 5

                  F₆ = F(6) = 8

                  F₇ = F(7) = 13

                  F₈ = F(8) = 21

                  F₉ = F(9) = 34

                  F₁₀ = F(10) = 55

                   ........................

피보나치 수들을 점화공식(recurrence formula)으로 정의하면

        F(n) = F(n - 1) + F(n - 2)     ∀ n = 2, 3, 4, 5, ...

        F(0) = 0,  F(1) = 1

가 됩니다.

            0 + 1 = 1

            1 + 1 = 2

            1 + 2 = 3

            2 + 3 = 5

            3 + 5 = 8

            5 + 8 = 13

             ..........

위의 점화공식  F(n) = F(n - 1) + F(n - 2)  은 

               F(n) - F(n - 1) = F(n - 2) 

혹은

               F(n) - F(n - 2) = F(n - 1) 

으로 사용되어지기도 합니다.