안녕하세요, 아주대학교 컴공과 학생입니다.

알고리즘 수업시간에 F[n] = F[n-1] + F[n-2], F[1]=0, F[2]=1 점화식이 있을 때, [[0, 1], [1, 1]] ^ n = [[F[n-1], F[n]], [F[n], F[n+1]] 라고 배웠습니다.

그래서 궁금증이 생겼는데요,

임의의 Homogeneous linear recurrence가 주어졌을 때, 저렇게 오른쪽처럼 생긴, 행렬의 거듭제곱 = ? 꼴의 등식을 항상 구할 수 있을까요?

그러면 DP 문제 풀때 O(lg n) 만에 풀 수 있을 것 같아요.