피보나치 수열이란 첫 두 항 F(1)와 F(2)의 값이 1이고, 그 다음부터는 n>=3인 자연수에 대해 F(n) = F(n-1)+F(n-2)이라고 재귀적으로 정의되는 수열이다.
1, 1, 2, 3, 5, 8, 13, 21, 34 …와 같은 순으로 숫자가 나열되며, 수가 커질수록 인접한 두 항의 비율은 황금비 (1+sqrt(5))/2로 수렴한다. 즉, 얘는 1 2 4 8 같은 등비수열과 동일한 형태는 아니지만, 수가 증가하는 정도가 등비수열과 동급이다.
그런데 다른 F 값에 의존하지 않고 F(n)의 값을 곧바로 구할 수는 없을까? 다시 말해 F(n)의 일반항을 구할 수는 없을까?
결론부터 말하자면.. 구할 수 있을 뿐만 아니라 더 나아가 0이 아닌 아무 a,b,c와 초기값 F(1), F(2)에 대해서 a*F(n+2) + b*F(n+1) + c*F(n) = 0꼴의 점화식 자체의 일반항을 구하는 것도 가능하다.
저런 점화식의 일반항은 X^n ± Y^n 의 형태로 귀착된다(X, Y는 임의의 상수). 피보나치 수열은 저기서 a=1이고 b=c=-1, F(1)=F(2)=1인 경우일 뿐이다.
이 점화식을 푸는 것의 핵심은 점화식을 동일하게 유지하면서 기존 a, b, c 계수를 각각 1, -(p+q), p*q라는 형태로 바꾸는 것이다. a는 a, b, c를 똑같이 a로 나눠 주면 1로 바꿀 수 있고, b와 c는 합이 -b이고 곱이 c인 p, q라는 또 다른 숫자쌍을 구해서 바꾸면 된다. 이런 식으로 일반성을 유지하면서 계수의 형태를 치환하는 건 3차나 4차 같은 대수방정식을 풀 때도 볼 수 있는 테크닉이다.
계수의 형태를 저렇게 바꿈으로써 우리는 동일한 점화식을 F(n+2) - p*F(n+1) = q*( F(n+1) - p*F(n) )이라고.. 우리가 처리하기 더 유리한 단순한 형태로 변형할 수 있다. 어떤 점에서 더 유리한지는 곧 알게 될 것이다.
p와 q 둘 중 하나가 0이면 F(n)은 그냥 평범한 등비수열이 되겠지만, 단서가 더 추가됨으로써 변형이 가해진 좀 더 복잡한 수열을 만들 수 있다.
가령, F(1)=F(2)=1이면서 p=2, q=-1이면 이 수열은 1 1 3 5 11 21 43 ... 즉, 앞의 수의 2배에다가 1을 더하거나 뺀 형태가 되며,
p=3, q=-2이면 1 1 7 13 55 133 463 1261 ... 앞의 수의 3배에다가 각각 4, -8, 16, -32를 더한.. 기묘한 수열이 만들어진다.
이런 유형의 수열을 저 점화식으로 표현할 수 있다는 것이다. 그리고 피보나치 수열은 p+q=1, pq=-1인 경우이다.
(그러고 보니 다른 수학 교재에서는 이때 p, q 대신 알파와 베타를 쓰는 편이더라만.. 그건 그냥 기분과 취향 문제이니 이 글에서는 계속해서 p, q를 쓰도록 하겠다.)
F(n+2) - p*F(n+1) = q*( F(n+1) - p*F(n) ) 이라는 식을 잘 살펴보면.. 그 정의상 초기항인 F(2) - p*F(1)에다가 q를 곱해 주는 것만으로 F의 등급을 쭉쭉 올릴 수 있다. 무슨 얘기냐 하면, n>=1에 대해서 F(n+2) - p*F(n+1) = q^n * (F(2) - p*F(1))이라는 것이다. 이런 놀라운 특성 때문에 점화식을 이런 형태로 바꾼 것이다.
저렇게 하면 식의 우변이 p, q, F(1), F(2)라는 상수 형태로 완전히 바뀐다. 아, 우변이 F(n)에 대한 의존도만 없어졌지 n에 대한 지수함수이기 때문에 완전한 상수는 아니다. 완전한 상수라면 이 형태만으로 문제가 다 풀렸을 것이다.
이 상태에서 식을 더 단순화시키기 위해서 우리가 활용하는 특성은 바로.. p, q의 값이 서로 뒤바뀌어도 생성되는 순열 결과는 달라지지 않는다는 것이다.
애초에 덧셈과 곱셈은 교환 법칙이 성립하는 연산이다. 그러니 p, q의 등장 순서를 뒤바꿔도 합 -b와 곱 c는 바뀌지 않을 것이다. 위의 점화식을 F(n+2) - q*F(n+1) = p*( F(n+1) - q*F(n) ) 이라고 바꿔 줘도 달라지는 것은 전혀 없다.
기하학적으로 생각하자면 저건 쌍곡선(곱이 같음 = 반비례)과 직선(합이 같음 = 정비례)의 교점을 구하는 것과 같다. 그 직선이 쌍곡선의 점근선 중 하나와 수직-평행 관계가 아닌 한, 교점은 “둘” 존재하게 될 것이다.
대수적으로 생각한다면야 저건 평범한 이차방정식을 푸는 것과 같다. -(p+q)와 p*q는 이차방정식 (x-p)(x-q)와 정확하게 대응한다. (x-p)(x-q)를 하든 (x-q)(x-p)를 하든 식이 달라지는 것은 없다. 너무 당연한 얘기이다.
F(n+2) - p*F(n+1) = q^n *( F(2) - p*F(1) )
F(n+2) - q*F(n+1) = p^n *( F(2) - q*F(1) )
그래서 위의 등식에서 아래의 등식을 그대로 빼 버리면.. F(n-2)가 없어지고 등식 전체에서 F(n+1) 하나만 남게 된다.
F(n+1)의 앞에 붙은 q-p라는 계수로 양변을 나누고, n을 n-1로 치환하면 일반항 유도가 완료된다. 대략
F(n) = ( (q*F(1) - F(2))*p^(n-1) - (p*F(1) - F(2))*q^(n-1) ) / (q-p)
라는 비교적 깔끔한 식이 나온다. 이 정도는 심하게 복잡하지는 않으니 이미지 대신 그냥 문자 형태로 때웠다. ㄲㄲ
양변을 덧셈이 아니라 뺄셈을 했기 때문에 F(1)과 F(2)의 부호가 반대로 바뀌었다.
피보나치 수열의 일반항은 저기에서 F(1)=F(2)=1, 그리고 p와 q에다가는 x^2 - x - 1 = 0의 근인 (1+sqrt(5))/2와 (1-sqrt(5))/2를 각각 대입하기만 하면 구할 수 있다.
번거로운 계산이 많긴 하지만 F(n) = (p^n - q^n)/(p-q)의 형태가 된다. 형태가 꽤 복잡해 보이는데, 그래도 n에다가 자연수를 대입해 보면 근호(루트)는 거짓말처럼 없어져서 최종 결과값이 자연수로만 딱딱 떨어진다.
분자의 거듭제곱은 그렇다 쳐도 분모는 p-q는 sqrt(5)로 깔끔하게 나오기 때문에 표기가 그리 복잡하지 않다.
이상이다. 글을 쭉 쓰면서 본인도 이 분야에 대한 공부를 확실하게 다시 할 수 있었다.
메이플이나 매스매티카 같은 수학 패키지에는 점화식을 푸는 명령이 물론 존재한다.
F(x+2) - (p+q)*F(x+1) + p*q*F(x) = 0의 일반항은 단순무식 F(x+2) + b*F(x+1) + c*F(x) = 0 보다 훨씬 더 간단하게 나오는 걸 알 수 있다. 후자는 내부적으로 sqrt(b^2-4*c) 같은 근의 공식이 잔뜩 섞여서 매우 복잡하다.
그리고 끝으로 생각할 점은..
피보나치 수열 정도는 이전 항의 이전 항.. 즉 2단계까지 역참조하는 점화식인데, 그 단계가 3단계 정도로만 올라가도 식의 복잡도는 상상 이상으로 치솟을 거라는 점이다. 특성 방정식은 2차가 아니라 3차가 될 것이고, 변수들을 연립해 주는 식도 2차가 아닌 3차가 될 것이고.. 실용적인 방법으로 일반항을 구하는 게 도저히 가능하지 않겠다.
Posted by 사무엘
