선형 점화식(Linear Recurrence Relation)은 점화식의 한 유형으로, 각 항이 일정한 수의 이전 항들의 선형 결합으로 표현되는 점화식을 의미한다. 선형 점화식은 수열, 알고리즘 분석, 공학적 모델링 등 다양한 분야에서 활용된다.
정의
일반적인 k차 선형 점화식은 다음과 같이 정의된다.
- an + c1an-1 + c2an-2 + ... + ckan-k = f(n)
여기서,
- an은 점화식의 n번째 항.
- c1, c2, ..., ck는 상수 계수.
- f(n)은 독립 항으로, 특정한 함수가 될 수 있음.
- k는 점화식의 차수.
특히, f(n) = 0이면 동차 선형 점화식, f(n) ≠ 0이면 비동차 선형 점화식이라 한다.
선형 점화식의 해법
선형 점화식의 해는 일반적으로 동차해와 특수해의 합으로 표현된다.
1. 동차 점화식 (Homogeneous Linear Recurrence)
- f(n) = 0인 경우, 점화식은 다음과 같다.
* an + c1an-1 + ... + ckan-k = 0
- 특성 방정식을 이용하여 해를 구할 수 있다.
2. 비동차 점화식 (Non-Homogeneous Linear Recurrence)
- f(n) ≠ 0인 경우, 점화식은 다음과 같다.
* an + c1an-1 + ... + ckan-k = f(n)
- 해는 일반해 = 동차해 + 특수해의 형태로 구할 수 있다.
특성 방정식
동차 선형 점화식의 해를 구하기 위해, 다음과 같은 특성 방정식을 설정한다.
- rk + c1rk-1 + ... + ck = 0
특성 방정식의 근을 구한 후, 다음과 같이 해를 결정한다.
- 서로 다른 실근 r1, r2, ..., rk이 존재할 경우
- an = A1r1n + A2r2n + ... + Akrkn
- A1, A2, ..., Ak는 초기 조건에 의해 결정됨.
- 중복된 근 r이 m번 존재할 경우
- an = (A1 + A2n + ... + Amnm-1)rn
예제
1. 피보나치 수열
피보나치 수열은 다음과 같은 선형 점화식을 만족한다.
- an = an-1 + an-2, a0 = 0, a1 = 1
특성 방정식은 다음과 같다.
- r2 - r - 1 = 0
이를 풀면, 근은 다음과 같다.
- r = (1 ± sqrt(5)) / 2
따라서, 일반해는 다음과 같다.
- an = A( (1+sqrt(5))/2 )n + B( (1-sqrt(5))/2 )n
2. 등비수열
등비수열의 점화식은 다음과 같다.
- an = r an-1, a0 = A
해는 다음과 같다.
- an = A rn
선형 점화식의 응용
- 알고리즘 분석
- 분할 정복 알고리즘의 시간 복잡도 분석 (예: 마스터 정리).
- 수열 및 조합론
- 파스칼의 삼각형 및 조합 점화식에서 활용.
- 동적 계획법
- 점화식을 기반으로 최적화 문제를 해결.
같이 보기
참고 문헌
- Rosen, K. H. (2019). Discrete Mathematics and Its Applications. McGraw-Hill.