on
First order recurrence relation
Definition
수열 $ {a_n} $ 이 어떤 고정된 수 $ s $와 $ t $에 대하여 다음과 같은 조건을 만족한다고 가정하자. \(\begin{align} a_n = sa_{n-1} + t, \text{ for } n \ge 1 \end{align}\) 이 때, 이를 first order recurrence relation이라 한다.
Proposition 1
초기조건 $ a_n $ 이 주어진 first order recurrence relation $ a_n = sa_{n-1} + t, \text{ for } n \ge 1 $에 대하여, 일반항 $ a_n $은 다음과 같이 주어진다. \(\begin{align} a_n = s^na_0 + (s^{n-1} + s^{n-2} + \dots + s + 1)t \end{align}\)
이는 다음과 같이 축약할 수 있다. \(\begin{align} a_n = \begin{cases} s^na_0+\frac{s^n+1}{s-1}t,& \text{ if }s\ne1\\ a_0+nt,&\text{ if }s=1 \end{cases} \end{align}\)
Second order recurrence relation
Definition
수열 $ { a_n } $이 어떤 고정된 수 $ s_1 $과 $ s_2 $에 대하여 다음과 같은 조건을 만족한다고 가정하자.
\(\begin{align}
a_n = s_1a_{n-1}+s_2a_{n-2}, \text{ for } n \ge 2
\end{align}\)
이 때, 이를 second order recurrence relation이라 한다.
어떤 second order recurrence relation $ a_n = s_1a_{n-1} + s_2a_{n-2}, \text{ for } n \ge 2 $ 를 가지고 있다고 가정하자.
이 때, 다음과 같은 2차 방정식을 생각할수 있다.
\(\begin{align}
x^2 = s_1x + s_2
\end{align}\)
Proposition 1
$ r $이 (5)의 한 근이라 가정하자.
그러면 $ a_n = r^n $은 second order recurrence relation을 만족한다.
Proposition 2
이 때, $ r_1, r_2 $가 (5)의 서로 다른 두 근이라 가정하자.
그러면 $ a_n = c_1{r_1}^n + c_2{r_2}^n $ 는 second order recurrence relation을 만족한다.
Proposition 3
$ r $이 (5)의 중근이라 가정하자.
그러면 $ a_n = nr^n $ 은 second order recurrence relation을 만족한다.
Proposition 2에 의하여, 주어진 방정식이 중근을 가질 경우 $ a_n = c_1r^n + c_2nr^n $ 는 second order recurrence relation을 만족한다.
일반적으로 k-th order recurrence relation $ a_n = s_1+a_{n-1} + \dots + s_k \text{ for } n \ge k $ 가 주어졌을 때, $ x^k = s_1x^{k-1} + \dots + s_k $의 해를 구하여 유사한 방법으로 일반항 $ a_n $을 구할 수 있다.