동차 점화식(Homogeneous Recurrence Relation)은 항들이 동일한 점화식을 따르며, 특정한 항들이 이전 항들의 선형 결합으로 표현되는 점화식을 의미한다.
정의
동차 점화식은 일반적으로 다음과 같이 표현된다.
- an + c1an-1 + c2an-2 + ... + ckan-k = 0
여기서,
- an은 점화식의 n번째 항
- c1, c2, ..., ck는 상수 계수
- k는 점화식의 차수
동차 점화식의 해법
동차 점화식은 특성 방정식을 이용하여 일반해를 구할 수 있다.
특성 방정식
점화식의 특성 방정식은 다음과 같다.
- rk + c1rk-1 + c2rk-2 + ... + ck = 0
특성 방정식의 근을 구한 후, 다음과 같이 해를 결정한다.
특성 방정식의 근에 따른 해
- 서로 다른 실근 r1, r2, ..., rk이 존재할 경우
- an = A1r1n + A2r2n + ... + Akrkn
- A1, A2, ..., Ak는 초기 조건에 의해 결정됨.
- 중복된 근 r이 m번 존재할 경우
- an = (A1 + A2n + ... + Amnm-1)rn
예제
피보나치 수열
피보나치 수열은 다음과 같은 점화식을 만족한다.
- an = an-1 + an-2
특성 방정식은 다음과 같다.
- r2 - r - 1 = 0
이를 풀면, 근은 다음과 같다.
- r = (1 ± sqrt(5)) / 2
따라서, 일반해는 다음과 같다.
- an = A( (1+sqrt(5))/2 )n + B( (1-sqrt(5))/2 )n
등비수열
등비수열의 점화식은 다음과 같다.
- an = r an-1
특성 방정식은 다음과 같다.
- r - r = 0
이를 풀면, 근은 r이 된다.
따라서, 일반해는 다음과 같다.
- an = A rn
동차 점화식의 응용
- 알고리즘 분석
- 분할 정복 알고리즘의 시간 복잡도 분석에 활용됨.
- 이산 수학
- 수열 및 수학적 귀납법 증명에서 사용됨.
- 물리학 및 공학
- 물리적 시스템의 동역학을 분석하는 데 적용됨.
같이 보기
참고 문헌
- Rosen, K. H. (2019). Discrete Mathematics and Its Applications. McGraw-Hill.