비동차 점화식 편집하기

'''비동차 점화식'''(Non-Homogeneous Recurrence Relation)은 동차 점화식과 달리,  점화식의 오른쪽에 상수항 또는 독립적인 함수가 포함되는 점화식을 의미한다.  즉, 항들이 이전 항들의 선형 결합뿐만 아니라 추가적인 항을 포함하는 경우이다.
==정의==
비동차 점화식은 일반적으로 다음과 같이 표현된다.
*a<sub>n</sub> + c<sub>1</sub>a<sub>n-1</sub> + c<sub>2</sub>a<sub>n-2</sub> + ... + c<sub>k</sub>a<sub>n-k</sub> = f(n)
여기서,
*a<sub>n</sub>은 점화식의 n번째 항
*c<sub>1</sub>, c<sub>2</sub>, ..., c<sub>k</sub>는 상수 계수
*f(n)은 0이 아닌 독립적인 함수 (예: 다항식, 지수 함수, 삼각 함수 등)
==비동차 점화식의 해법==
비동차 점화식의 해는 '''일반해 = 동차해 + 특수해'''의 형태로 구할 수 있다.
===1. 동차해 (Homogeneous Solution)===
*f(n) = 0일 때의 해를 먼저 구한다.
*동차 점화식의 특성 방정식을 이용하여 일반해를 구한다.
===2. 특수해 (Particular Solution)===
*f(n)의 형태에 따라 특정한 해를 찾는다.
*일반적으로 f(n)의 형태에 따라 다음과 같은 가정이 사용된다.
{| class="wikitable"
|+특수해의 유형
!f(n)!!특수해의 형태
|-
|C (상수)||A
|-
|Cn||An + B
|-
|Cn²||An² + Bn + C
|-
|C rⁿ||A rⁿ
|-
|C sin(n), C cos(n)||A sin(n) + B cos(n)
|}
==예제==
===1. f(n)이 상수인 경우===
점화식:
*a<sub>n</sub> - 3a<sub>n-1</sub> = 5
'''1단계: 동차해 구하기'''  특성 방정식:
*r - 3 = 0
*r = 3
따라서, 동차해는 다음과 같다.
*a<sub>n</sub><sup>(h)</sup> = A 3<sup>n</sup>
'''2단계: 특수해 구하기'''  f(n) = 5이므로, 특수해를 다음과 같이 가정한다.
*a<sub>n</sub><sup>(p)</sup> = C
이를 점화식에 대입하면,
*C - 3C = 5 → C = -5/2
따라서, 최종 해는 다음과 같다.
*a<sub>n</sub> = A 3<sup>n</sup> - 5/2
===2. f(n)이 다항식인 경우===
점화식:
*a<sub>n</sub> - a<sub>n-1</sub> = n
'''1단계: 동차해 구하기'''  특성 방정식:
*r - 1 = 0
*r = 1
따라서, 동차해는 다음과 같다.
*a<sub>n</sub><sup>(h)</sup> = A 1<sup>n</sup> = A
'''2단계: 특수해 구하기'''  f(n) = n이므로, 특수해를 다음과 같이 가정한다.
*a<sub>n</sub><sup>(p)</sup> = Cn + D
이를 점화식에 대입하면,
*(Cn + D) - (C(n-1) + D) = n
*Cn + D - Cn + C - D = n
*C = 1
따라서, 최종 해는 다음과 같다.
*a<sub>n</sub> = A + n
==비동차 점화식의 응용==
*'''알고리즘 분석'''
**분할 정복 알고리즘의 시간 복잡도 분석 (예: 마스터 정리).

*'''수열 및 조합론'''
**파스칼의 삼각형 및 조합 점화식에서 활용.

*'''물리학 및 공학'''
**차분 방정식을 이용한 동역학 모델링.
==같이 보기==
*[[동차 점화식]]
*[[재귀 함수]]
*[[특성 방정식]]
*[[분할 정복 알고리즘]]
*[[차분 방정식]]
==참고 문헌==
*Rosen, K. H. (2019). ''Discrete Mathematics and Its Applications''. McGraw-Hill.