General Linear Recurrence Relations
수열 \(\left \{ a_n \right \} \)에 대해 \(a_{n+2} = a_{n+1} + a_{n} \)과 같은 형태를 일반화시킨 점화식이다.
\[ c_0 a_n +c_1 a_{n+1} + \cdots + c_k a_{n+k} = f(n) \quad (c_i \text{ is constant})\]
1. Linear Homogeneous Recurrence Relation
\(f(n)=0 \)일 경우
\[ c_0 a_n +c_1 a_{n+1} + \cdots + c_k a_{n+k} = 0 \]
이런 형태를 homogeneous하다고 하며, characteristic equation을 다음과 같이 정의한다.
\[ c_k x^k + c_{k-1} x^{k-1} + \cdots c_1 k + c_0 = 0 \]
characteristic equation의 근은 characteristic root라고 부른다.
뒤에 쓰여진 것들은 지금 정의한 것을 토대로 확장해간다는 느낌으로 읽으면 좋을 것이다.
1.1 nth power
\(\lambda \)가 characteristic root이면 \(a_n = \lambda ^n \)이고, 그 역도 성립한다.
\[a_n = \lambda ^n \]
\[ c_0 \lambda ^n + c_1 \lambda ^{n+1} + \cdots + c_k \lambda ^{n+k} =0 \]
\[ \lambda^n ( c_0 + c_1 \lambda + \cdots + c_k \lambda ^k = 0\]
\[ c_0 + c_1 \lambda + \cdots + c_k \lambda ^k = 0\]
■
1.2 addition
\(a_n = f_n \), \(a_n = g_n \) , \(\cdots\) , \(a_n = h_n \)이면 모든 상수 \(\alpha \), \(\beta\), \(\cdots\)에 대해 \(F(n) = \alpha f_n + \beta g_n + \cdots + \gamma h_n \), \(a_n = F(n) \)도 성립한다.
\[ c_0 f_n + c_1 f_{n+1} + \cdots + c_k f_{n+k} = 0\]
\[ c_0 g_n + c_1 g_{n+1} + \cdots + c_k g_{n+k} = 0\]
\[\vdots\]
\[ c_0 h_n + c_1 h_{n+1} + \cdots + c_k h_{n+k} = 0\]
맨 처음 식에 \(\alpha\), 두번째 식에 \(\beta\), ... , 마지막 식에 \(\gamma\)를 곱했을 때
\[ c_0 F(n) + c_1 F(n+1) + \cdots + c_k F(n+k ) \]
■
1.3 addition of nth power
characteristic root \(\lambda_1 , \lambda_2 , \cdots \lambda _k \)에 대해 \(a_n = \alpha _1 \lambda_1 ^n + \alpha _2 \lambda_2 ^n + \cdots + \alpha _n \lambda _n ^n \)이다.
(by 1.2, 1.3) ■
1.4 multiplicity 2
\[ f(x) = c_k x^k + c_{k-1} x^{k-1} + \cdots + c_1 x + c_0 \]
\(\lambda\)가 \(f(x) = 0 \)의 multiplicity 2짜리 characteristic root이라면 \(a_n = n \lambda ^n \)도 점화식을 만족한다.
\[ g(x) = x^n f(x) = c_k x^{n+k} + c_{k-1} x^{n+k-1} + \cdots + c_1 x^{n+1} + c_0 x^n \]
\[ g'(x) = (n+k) c_k x^{n+k-1} + (n+k-1) c_{k-1} x^{n+k-2} + \cdots + (n+1) c_1 x^n + n c_0 x^{n-1} \]
\[ x g'(x) = (n+k) c_k x^{n+k} + (n+k-1) c_{k-1} x^{n+k-1} + \cdots + (n+1) c_1 x^{n+1} + n c_0 x^n \]
\[ (x - \lambda )^2 | f(x) \]
\[ (x-\lambda )^2 | g(x) = x^n f(x) \]
\[ x- \lambda | g'(x), \quad \text{thus } x-\lambda|xg'(x) \]
\[ n c_0 \lambda ^n + (n+1) c_1 \lambda ^{n+1} + \cdots + (n+k-1) c_{k-1} \lambda^{n+k-1} + (n+k) c_k \lambda ^{n+k} = 0\]
\[ a_n = n\lambda ^n \]
■
1.5 Final Generalization, multiplicity p
\(\lambda\)가 \(f(x) = 0\)의 multiplicity \(p\)짜리 characteristic root이면
\[ a_n = \lambda ^n , n \lambda^n , \cdots , n^{p-1} \lambda ^n \]
가 모두 점화식을 만족한다.
1.4를 연장해서 증명할 수 있다. 간단하게 \(p=3\)을 보자.
\[x g'(x) = (n+k) c_k x^{n+k} + (n+k-1) c_{k-1} x^{n+k-1} + \cdots + (n+1) c_1 x^{n+1} + n c_0 x^n\]
\[ x( xg'(x))' = (n+k)^2 c_k x^{n+k} + (n+k-1)^2 c_{k-1} x^{n+k-1} + \cdots + (n+1)^2 c_1 x^{n+1} + n^2 c_0 x^n\]
\[ (x-\lambda)^3 |g(x) = x^n f(x) , \; (x-\lambda)^2 | xg'(x) , \; x-\lambda | x(xg'(x))' \]
\[ \therefore n^2 c_0 \lambda ^n + (n+1)^2 c_1 \lambda^{n+1} + \cdots + (n+k-1)^2 c_{k-1} \lambda^{n+k-1} + (n+k) ^2 c_k \lambda^{n+k} = 0 \]
\[ a_n = n^2 \lambda ^n \]
이런 식으로 계속 나아갈 수 있기 때문에 증명된다.
□
2. Linear non-Homogeneous Recurrence Relation
\(f(n) != 0\)인 homogeneous하지 않은 일반적인 관계이다.
\[c_0 a_n +c_1 a_{n+1} + c_2 a_{n+2} + \cdots + c_k a_{n+k} = f(n) \]
2.1 과정
일반적인 풀이는 없으므로 f(n) 의 형태에 따라 particular solution, p(n) 을 결정하는 방법이 있다.
1. 먼저 f(n)=0으로 놓아서 linear homogeneous recurrence relation의 결과 \(a_n = g(n) \)을 얻는다.
2. f(n) 의 특수한 꼴에 따라 p(n) 을 결정한다.
3. F(n) = g(n) + p(n)
2.2 \(f(n) = \sum _{i=0} ^t p_i n^i \)
1이 characteristic root이 아닐 때 : \( p(n) = \sum _{i=0} ^t q_i n^i \)
1이 multiplicity m짜리 characteristic root일 때 : \( p(n) = n^m \sum _{i=0} ^t q_i n^i \)
2.3 \(f(n) = Ak^n \)
k가 characteristic root이 아닐 때 : \(p(n) = Bk^n \)
k가 multiplicity m짜리 characteristic root일 때 : \(p(n) = Bn^m k^n \)
2.4 \(f(n) = An^t k^n\)
k가 characteristic root이 아닐 때 : \(p(n) = (\sum _{i=0} ^t q_i n^i )k^n\)
k가 multiplicity m짜리 characteristic root일 때 : \( p(n) = (n^m \sum _{i=0} ^t q_i n^i ) k^n \)