라메의 정리
라메의 정리(Lamé's Theorem)는 2가지 방법으로 표현할 수 있다.
증명 편집
유클리드 알고리즘이 k단계로 끝나는 두수 Ak,Bk 가 있고 , Ak > Bk 라고 하자. 이 정리는 유클리드 알고리즘에 따라 (Ak+1,Bk+1) -> (Ak,Bk) -> (Ak-1,Bk-1)처럼 줄어 들 때, Bk+1 >= Bk + Bk-1이라는 주장을 바탕으로 한다. 이 주장이 옳은지 보기 위해서 계산 단계마다 Ak-1 = Bk , Bk-1 = (Ak%Bk)라는 규칙을 따른다는 것을 끌어들이자.
두 번째 식 (Bk-1 = (Ak%Bk))는 0보다 큰 정수 q가 있을 때 Ak = qBk + Bk-1이란 뜻이다.
그 이유를 풀어 본다면 Bk-1 = Ak%Bk 라고 할 때 Ak%Bk -> Ak - (Bk*(Ak/Bk) 라고 할 수 있다. 수의 범위가 정수이고 Ak > Bk 라고 정의 했기 때문에 (Bk*(Ak/Bk))가 Ak가 되지 않는다는 점에 유의하자.
그렇다면 Bk-1 = Ak - (Bk * (Ak / Bk))가 되고 이것은 다시 Ak = (Ak/Bk)*Bk + Bk-1 가 된다. 여기서 (Ak/Bk) 부분이 q가 되는 것이다.
q는 적어도 1보다 크거나 같기 때문에 Ak = qBk + Bk-1 >= Bk + Bk-1 이 된다. 이제 첫번째 식에서 Ak = Bk+1을 이끌어 낼 수 있다. 이를 합치면 Bk+1 = Ak = qBk + Bk-1 >= Bk + Bk-1 , 즉 Bk+1 >= Bk + Bk-1이 된다. 이제 정리를 증명해보자 (귀납법) k = 1이면 B가 적어도 Fib(1)=1 보다 크게 되므로 앞의 정리는 옳다. k보다 작거나 같은 모두 정수에 대해서 정리가 옮다고 가정한다면 k+1에서 (Ak+1,Bk+1) -> (Ak,Bk) -> (Ak-1,Bk-1) 로 줄어든다. 귀납적 가정에 따라 Bk-1 >= Fib(k-1) 이고 bk >= Fib(k)이다. 앞에서 밝힌 주장과 피보나치 수열의 정의에 따라 Bk+1 >= Bk + Bk-1 >= Fib(k) + Fib(k-1) = Fib(k+1) 이므로 이 정리는 옳다.