점화식의 일반항 구하기
수학과 복수전공을 위해 졸업 시험 과목으로 “이산수학”을 선택하였습니다. 학부 2학년 때 컴공과 수업으로 들었던 기억이 있는데… 감각만을 믿을 수는 없으니! 다시 도전 해봅시다! 전체 포스트는 “Discrete Mathematics“에서 확인할 수 있습니다.
Fibonacci Sequence
\[a_{n+2} = a_{n+1} + a_n \quad n \ge 0\]이런 관계를 만족하는, 수열이 있습니다. 이것의 일반항을 “특성 다항식”을 사용해 구해봅시다.
위의 점화식의 특성 방정식은
\[x^{n+2} - x^{n+1} - x^n = 0\]이고 이것을 $x^n$으로 묶으면,
\[x^n \cdot (x^2 - x - 1) = 0\]이 됩니다. 이때, $x^n \ne 0$이므로, $x^2 - x - 1 = 0$이 되어야 하고, 이것이 피보나치 수열의 특성 다항식 입니다.
이 특성 방정식의 근을 구해봅시다. 그러면, 아래의 근이 나옵니다.
\[r = \frac{1 \pm \sqrt{5}}{2}\]이제 점화식의 해를 아래와 같이 구성 됩니다.
\[a_n = c_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n + c_2 \left(\frac{1 - \sqrt{5}}{2}\right)^n\]이제 초기조건을 대입하여 상수 $c_1$, $c_2$를 구합니다. 만약 초기조건이 없다면! 점화식의 일반항 $a_n$는 무한히 많은 솔루션이 가능합니다!
$a_0 = 0$ 따라서,
\[a_0 = c_1 + c_2 = 0 \therefore c_1 = - c_2\]$a_n1 = 1$
\[a_1 = c_1 \left(\frac{1 + \sqrt{5}}{2}\right) + c_2 \left(\frac{1 - \sqrt{5}}{2}\right) = c_1 \left(\frac{1 + \sqrt{5}}{2}\right) - c_1 \left(\frac{1 - \sqrt{5}}{2}\right) = c_1 \left( \sqrt{5} \right) = 1\]따라서, $c_1 = \frac{1}{\sqrt{5}}$가 됩니다. 마찬가지로 $c_2$도 쉽게 구할 수 있습니다.
최종 정리하면,
\[a_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1 + \sqrt{5}}{2}\right) - \left(\frac{1 - \sqrt{5}}{2}\right) \right]\]Non-homogeneous Case
\[a_{n+2} = a_{n+1} + a_n + f(n)\]이번에는 $f(n)$이 추가 되었습니다! 처음에 살펴본 것은 $f(n) = 0$으로 동차식에 대한 일반해 였습니다. 이번에는 $f(n) \ne 0$인 좀더 많은 경우를 커버 합니다. 이런 비동차식에서의 일반해를 구해봅시다!
미분방정식에서도 비슷하게 하는데, 이렇게 비동차식이 나오면,
- $f(n) = 0$인 경우의 동차식에서의 솔루션과
- $f(n) \ne 0$인 경우의 특수해(particular solution)을 구합니다.
그리고 최종 솔루션은 “(동차해 + 특수해)”의 형태로 마무리 합니다.
피보나치 수열에서 비동차식 경우를 다뤄봅시다. $f(n) = 1$로 가장 쉽게 세팅 했습니다!
\[a_{n+2} = a_{n+1} + a_n + 1\]동차식의 해는 처음에 구했습니다!
\[a_n^{(h)} = \frac{1}{\sqrt{5}} \left[ \left(\frac{1 + \sqrt{5}}{2}\right) - \left(\frac{1 - \sqrt{5}}{2}\right) \right]\]이제 특수해를 구해야 합니다! 이건 “미정계수법(Method of Undetermined Coefficient)“으로 풀면 됩니다! (오우… 이것까지 2차 미방을 푸는 방식이랑 똑같네요 ㅋㅋ)
일단 지금 주어진 식은 $f(n) = 1$로 상수형이기 때문에, 특수해도 상수형일 것으로 추측 합니다.
\[a_n^{(p)} = C\]그리고 점화식에 특수해를 대입합니다.
\[\begin{aligned} a_{n+2}^{(p)} &= a_{n+1}^{(p)} + a_n^{(p)} + 1 \\ \cancel{C} &= \cancel{C} + C + 1 \end{aligned}\]그러면, $C = -1$로 구해집니다!
이제 최종해를 구해봅시다!
\[a_n = a_n^{(h)} + a_n^{(p)} = \frac{1}{\sqrt{5}} \left[ \left(\frac{1 + \sqrt{5}}{2}\right) - \left(\frac{1 - \sqrt{5}}{2}\right) \right] - 1\]완료! $\blacksquare$
Method of Undetermined Coefficient
미정계수법은 주어진 $f(n)$의 형태에 따라서 다르게 적용해야 합니다. 이번 경우는 $f(n) = 1$로 상수형이라서 $C$라는 상수로 두고 풀었지만, $f(n) = 2 n^2 + n + 1$과 같은 다항식으로 나온다면, 특수해 $a_n^{(p)}$도 이에 맞춰 다항식으로 잡아줘야 합니다.
연습 삼아, $f(n) = n^2 + 1$로 주어진 경우를 풀어봅시다. 동차해는 이미 알고 있으니 특수해만 구해보겠습니다.
먼저 특수해를 아래와 같이 설정 합니다.
\[a_n^{(p)} = p_2 n^2 + p_1 n + p_0\]이제 이걸 점화식에 대입합니다.
\[\begin{aligned} a_{n+2}^{(p)} &= a_{n+1}^{(p)} + a_n^{(p)} + 1 \\ (p_2 (n+2)^2 + p_1 (n+2) + p_0) &= (p_2 (n+1)^2 + p_1 (n+1) + p_0) + (p_2 n^2 + p_1 n + p_0) + (n^2 + 1) \\ p_2 n^2 + (4 p_2 + p_1) n + (4p_2 + 2p_1 + p_0) &= (p_2 n^2 + (2 p_2 + p_1) n + (p_2 + p_1 + p_0)) + (p_2 n^2 + p_1 n + p_0) + (n^2 + 1) \end{aligned}\]아이고 길다… 이제 각 차수의 계수만 정리하겠습니다.
\[\begin{aligned} \cancel{p_2} &= \cancel{p_2} + p_2 + 1 \\ (4p_2 + \cancel{p_1}) &= (2p_2 + \cancel{p_1}) + p_1 + 0 \\ (4p_2 + 2 p_1 + \cancel{p_0}) &= (p_2 + p_1 + \cancel{p_0}) + p_0 + 1 \end{aligned}\]미지수가 3개, 다항식이 3개 나왔습니다. 그리고 $p_2 = -1$로 바로 구했습니다!
차근차근 대입해서 해를 구하면, $p_1 = -2$, $p_0 = -6$ 입니다. 따라서, 특수해는
\[a_n^{(p)} = - n^2 - 2 n - 6\]이 됩니다.
Repeated Root
특성 다항식을 푼다는 건, 결국 다항식의 해를 구한다는 것 입니다. 그런데, 다항식의 해에는 “중근(repeated root)”가 발생할 수 있습니다! 이런 경우는 어떻게 해야 할까요??
예를 들어, 점화식
\[a_{n+2} = 4 a_{n+1} - 4 a_{n}\]으로 두면, 특성다항식은 중근이 나옵니다!
\[(r - 2)^2 = 0\]이런 경우는 어떻게 해야 할까요? 동차해가 이렇게 나올까요?
\[a_n \overset{?}{=} c_1 \cdot 2^n\]아닙니다! 이런 경우는 동차해를 이렇게 세팅해줘야 합니다! (놀랍게도 이 부분도 2차 미방을 푸는 것과 완전 동일… ㅋㅋ)
\[a_n = (c_1 + c_2 n) \cdot 2^n\]이렇게 하고, 초기값을 대입해서 $c_1, c_2$를 결정하면 됩니다~~