비동차 점화식(Non-Homogeneous Recurrence Relation)은 동차 점화식과 달리, 점화식의 오른쪽에 상수항 또는 독립적인 함수가 포함되는 점화식을 의미한다. 즉, 항들이 이전 항들의 선형 결합뿐만 아니라 추가적인 항을 포함하는 경우이다.

정의

비동차 점화식은 일반적으로 다음과 같이 표현된다.

• a_n + c₁a_n-1 + c₂a_n-2 + ... + c_ka_n-k = f(n)

여기서,

• a_n은 점화식의 n번째 항
• c₁, c₂, ..., c_k는 상수 계수
• f(n)은 0이 아닌 독립적인 함수 (예: 다항식, 지수 함수, 삼각 함수 등)

비동차 점화식의 해법

비동차 점화식의 해는 일반해 = 동차해 + 특수해의 형태로 구할 수 있다.

1. 동차해 (Homogeneous Solution)

• f(n) = 0일 때의 해를 먼저 구한다.
• 동차 점화식의 특성 방정식을 이용하여 일반해를 구한다.

2. 특수해 (Particular Solution)

• f(n)의 형태에 따라 특정한 해를 찾는다.
• 일반적으로 f(n)의 형태에 따라 다음과 같은 가정이 사용된다.

특수해의 유형

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_n - 3a_n-1 = 5

1단계: 동차해 구하기 특성 방정식:

• r - 3 = 0
• r = 3

따라서, 동차해는 다음과 같다.

• a_n^(h) = A 3ⁿ

2단계: 특수해 구하기 f(n) = 5이므로, 특수해를 다음과 같이 가정한다.

• a_n^(p) = C

이를 점화식에 대입하면,

• C - 3C = 5 → C = -5/2

따라서, 최종 해는 다음과 같다.

• a_n = A 3ⁿ - 5/2

2. f(n)이 다항식인 경우

점화식:

• a_n - a_n-1 = n

1단계: 동차해 구하기 특성 방정식:

• r - 1 = 0
• r = 1

따라서, 동차해는 다음과 같다.

• a_n^(h) = A 1ⁿ = A

2단계: 특수해 구하기 f(n) = n이므로, 특수해를 다음과 같이 가정한다.

• a_n^(p) = Cn + D

이를 점화식에 대입하면,

• (Cn + D) - (C(n-1) + D) = n
• Cn + D - Cn + C - D = n
• C = 1

따라서, 최종 해는 다음과 같다.

• a_n = A + n

비동차 점화식의 응용

• 알고리즘 분석
  • 분할 정복 알고리즘의 시간 복잡도 분석 (예: 마스터 정리).

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

• 물리학 및 공학
  • 차분 방정식을 이용한 동역학 모델링.

같이 보기

• 동차 점화식
• 재귀 함수
• 특성 방정식
• 분할 정복 알고리즘
• 차분 방정식

참고 문헌

• Rosen, K. H. (2019). Discrete Mathematics and Its Applications. McGraw-Hill.