정수 계수 선형 점화식 U_n = PU_(n-1) + QU_(n-2) 의 특성 방정식을 x^2 - Px - Q = f(x) 이라고 합시다.
여기에서 하나의 보조정리를 얻을 수 있는데, f(x) 의 두 근을 x, y 라고 두면 U_n = ax^n + bx^n 꼴로 나타낼 수 있다는 겁니다. 이 증명은 U_n = x^n 으로 둬서 수학적 귀납법으로 할 수 있고 생략합니다.
아까 말씀하신 방정식 x^2 -6x + 4=0 를 특성 방정식으로 두면
x = 3 + sqrt(5)
y = 3 - sqrt(5) 가 됩니다. 근데 y < 1 이고 U_n = ax^n + by^n 에서 구하고자 하는 문제를 치환하기 위해서 a = 1, b = 1 를 선택합니다. 그러면 U_n = ceil(x^n) 이라고 볼 수 있습니다. (U_n 은 항상 자연수 값을 가진다는 것을 우리는 이미 알고 있습니다)
근데 아까 U_n=PU_(n-1)+QU_(n-2) 로부터 P=6, Q=-4 입니다.
이 점화식만 계산하면 됩니다. 행렬 거듭제곱 등의 방법을 쓰면 시간복잡도는 O(logn) 입니다.