[조합론] 5. 점화식(2: 선형점화식)

[조합론] 5. 점화식(2: 선형점화식)

상수 \(c_{i}\,(c_{r}\neq0)\)와 자연수 \(n\)에 대한 함수 \(g(n)\)에 대하여$$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots+c_{r}a_{n-r}+g(n)$$형태의 점화식을 선형점화식(linear recurrence)이라고 한다.

\(g(n)=0\)이면, 선형 동차점화식(linear homogeneous recurrence),

\(g(n)\neq0\)이면, 선형 비동차점화식(linear homogeneous recurrence)이라고 하고, \(r\)을 이 점화식의 차수(order)라고 한다.

차수가 \(r\)인 선형 동차점화식$$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots+c_{r}a_{n-r}$$에 \(a_{k}=\alpha^{k}\,(1\leq k\leq n,\,\alpha\neq0)\)을 대입하면$$\alpha^{n}=c_{1}\alpha^{n-1}+c_{2}\alpha^{n-2}+\cdots+c_{r}\alpha^{n-r}$$이고$$\alpha^{r}=c_{1}\alpha^{r-1}+c_{2}\alpha^{r-2}+\cdots+c_{r}$$이며 다음과 같이 방정식 형태로 나타낼 수 있다.$$x^{r}-c_{1}x^{r-1}-c_{2}x^{r-2}-\cdots-c_{r}=0$$이 위의 방정식을 선형 동차점화식의 특성방정식(characteristic equation)이라고 한다.

이 방정식은 \(r\)차 방정식이므로 \(r\)개의 근을 가지며 \(c_{r}\neq0\)이므로 그 근은 \(0\)이 아니다. 만약 \(\alpha_{1},\,\alpha_{2},\,\cdots,\,\alpha_{r}\)이 방정식의 근이면, 모든 \(i\)에 대해 \(a_{n}=\alpha_{i}^{n}\)은 점화식의 해가 되고, 이것들을 점화식의 기본해(fundamental solution)라고 한다. 

위의 선형 동차점화식의 해 \(h_{1}(n),\,\cdots,\,h_{r}(n)\)에 대하여 임의의 상수 \(k_{1},\,\cdots,\,k_{r}\)에 대해$$H(n)=\sum_{i=1}^{r}{k_{i}h_{i}(n)}$$도 선형 동차점화식의 해가 된다. 따라서 위 특성방정식의 서로 다른 \(n\)개의 근 \(\alpha_{1},\,\cdots,\,\alpha_{n}\)에 대하여$$a_{n}=k_{1}\alpha_{1}^{n}+k_{2}\alpha_{2}^{n}+\cdots+k_{n}\alpha_{n}^{n}$$는 점화식의 해가 된다.

예: 점화식 \(a_{n}=2a_{n-1}+3a_{n-2}\,(a_{0}=a_{1}=1)\)의 해는?

풀이: 이 점화식의 특성방정식은 \(x^{2}-2x-3=(x-3)(x+1)=0\)이고, 그 해는 \(x=3\), \(x=-1\)이다. 그러면$$a_{n}=k_{1}3^{n}+k_{2}(-1)^{n}$$이고, 초기조건 \(a_{0}=a_{1}=1\)을 이용하면$$\begin{align*}1&=a_{0}=k_{1}+k_{2}\\1&=a_{1}=3k_{1}-k_{2}=3k_{1}-k_{2}\end{align*}$$이고 \(\displaystyle k_{1}=\frac{1}{2},\,k_{2}=\frac{1}{2}\)이므로 따라서 \(\displaystyle a_{n}=\frac{3^{n}+(-1)^{n}}{2}\)이다.

예: 피보나치 수열(Fibonacci sequence) \(F_{n}=F_{n-1}+F_{n-2},\,F_{0}=0,\,F_{1}=1\)의 해는?

풀이: 피보나치 수열의 특성방정식은 \(x^{2}-x-1=0\)이고, 그 해는 \(\displaystyle x=\frac{1\pm\sqrt{5}}{2}\)이다. 그러면$$F_{n}=k_{1}\left(\frac{1+\sqrt{5}}{2}\right)^{n}+k_{2}\left(\frac{1-\sqrt{5}}{2}\right)^{n}$$이고, 초기조건 \(F_{0}=0,\,F_{1}=1\)을 이용하면$$\begin{align*}0&=F_{0}=k_{1}+k_{2}\\1&=F_{1}=k_{1}\frac{1+\sqrt{5}}{2}+k_{2}\frac{1-\sqrt{5}}{2}\end{align*}$$이고 \(\displaystyle k_{1}=\frac{1}{\sqrt{5}},\,k_{2}=-\frac{1}{\sqrt{5}}\)이므로 따라서 피보나치 수열의 일반항은$$a_{n}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n}\,(n\geq0)$$이다.

특성방정식 \(x^{r}-c_{1}x^{r-1}-c_{2}x^{r-2}-\cdots-c_{r}=0\)이 \(m\)중근 \(\alpha\)를 갖는다고 하자. 그러면 \((x-\alpha)^{m}\)은 특성방정식을 나누고 따라서 특성방정식의 다항식을 미분해도 \((x-\alpha)\)로 나누어 떨어진다. 특성방정식에 \(x^{n-r}\)을 곱하면$$x^{n}-c_{1}x^{n-1}-c_{2}x^{n-2}-\cdots-c_{r}x^{n-r}=0$$이고 이 식을 \(x\)에 대해 미분하면$$nx^{n-1}-(n-1)c_{1}x^{n-2}-(n-2)c_{2}x^{n-3}-\cdots-(n-r)c_{r}x^{n-r-1}=0$$이며, 이 식에 \(x\)를 곱하면$$nx^{n}-(n-1)c_{1}x^{n-1}-(n-2)c_{2}x^{n-2}-\cdots-(n-r)c_{r}x^{n-r}=0$$이다. 따라서 새로 얻은 특성방정식에 \(x=\alpha\)를 대입하고 \(a_{n}=n\alpha^{n}\)이라고 하면,$$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots+c_{r}a_{n-r}$$가 되어 점화식을 만족한다. 위와 같은 방법으로(미분하고 \(x\)를 곱한다) \(a_{n}=n^{2}\alpha^{n},\,\cdots,\,n^{m-1}\alpha^{n}\)도 이 점화식을 만족함을 알 수 있다.

예: 점화식 \(a_{n}=4a_{n-1}-4a_{n-2},\,a_{0}=1,\,a_{1}=8\)의 해는?

풀이: 이 점화식의 특성방정식은 \(x^{2}-4x+4=(x-2)^{2}=0\)이므로 이중근 \(x=2\)을 갖는다. 그러면$$a_{n}=k_{1}2^{n}+k_{2}n2^{n}$$이고, 초기조건 \(a_{0}=1,\,a_{1}=8\)를 이용하면$$\begin{align*}1&=a_{0}=k_{1}\\8&=a_{1}=2k_{1}+2k_{2}\end{align*}$$이고 \(k_{1}=1,\,k_{2}=3\)이므로 따라서 \(a_{n}=2^{n}+3n2^{n}=(3n+1)2^{n}\,(n\geq0)\)이다.

예: 점화식 \(a_{n}=-2a_{n-1}+2a_{n-3}+a_{n-4},\,a_{0}=2,\,a_{1}=-2,\,a_{2}=8,\,a_{3}=-12\)의 해는?

풀이: 이 점화식의 특성방정식은 \(x^{4}+2x^{3}-2x-1=(x+1)^{3}(x-1)=0\)이므로 삼중근 \(x=-1\)과 \(x=1\)을 해로 갖는다. 그러면$$a_{n}=(k_{1}+k_{2}n+k_{3}n^{2})(-1)^{n}+k_{4}$$이고, 초기조건 \(a_{0}=2,\,a_{1}=-2,\,a_{2}=8,\,a_{3}=-12\)를 이용하면$$\begin{align*}2&=a_{0}=k_{1}+k_{4}\\-2&=a_{1}=-k_{1}-k_{2}-k_{3}+k_{4}\\8&=a_{2}=k_{1}+2k_{2}+4k_{3}+k_{4}\\-12&=-k_{1}-3k_{2}-9k_{3}+k_{4}\end{align*}$$이고 \(k_{1}=1,\,k_{2}=1,\,k_{3}=1,\,k_{4}=1\)이므로 따라서 \(a_{n}=(1+n+n^{2})(-1)^{n}+1\,(n\geq0)\)이다. 

특성방정식의 근이 허수(복소수)가 나오면 그대로 대입해서 구한다.

예: \(a_{n}=-2a_{n-2}-a_{n-4},\,a_{0}=0,\,a_{1}=1,\,a_{2}=2,\,a_{3}=3\)의 해는?

풀이: 이 점화식의 특성방정식은 \(x^{4}+2x^{2}+1=(x^{2}+1)^{2}=0\)이므로 이중근 \(x=\pm i\,(i=\sqrt{-1})\)을 갖는다. 그러면$$a_{n}=k_{1}i^{n}+k_{2}ni^{n}+k_{3}(-i)^{n}+k_{4}n(-1)^{n}$$이고, 초기조건 \(a_{0}=0,\,a_{1}=1,\,a_{2}=2,\,a_{3}=3\)을 이용하면$$\begin{align*}0&=a_{0}=k_{1}+k_{3}\\1&=a_{1}=i(k_{1}+k_{2}-k_{3}-k_{4})\\2&=a_{2}=-k_{1}-2k_{2}-k_{3}-2k_{4}\\3&=a_{3}=i(-k_{1}-3k_{2}+k_{3}+3k_{4})\end{align*}$$이고 \(\displaystyle k_{1}=-\frac{3}{2}i,\,k_{2}=-\frac{1}{2}+i,\,k_{3}=\frac{3}{2}i,\,k_{4}=-\frac{1}{2}-i\)이므로 따라서$$a_{n}=-\frac{3}{2}i^{n+1}+\left(-\frac{1}{2}+i\right)ni^{n}+\frac{3}{2}i(-i)^{n}-\left(\frac{1}{2}+i\right)n(-i)^{n}\,(n\geq0)$$이다. 

지금까지는 선형 동차점화식에 대해서 다루었고 이제부터 선형 비동차점화식$$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots+c_{r}a_{n-r}+g(n)$$에 대해 다루고자 한다. 비동차점화식의 해를 \(p(n)\)(특수해), 동차점화식의 해를 \(f(n)\)이라고 하면, 이 비동차점화식의 일반해는 \(f(n)+p(n)\)이다. 비동차점화식의 특수해 \(p(n)\)을 구할 때, 다음의 표를 참고해서 구한다.

\(g(n)\)	\(a_{n}\)의 특수해
\(d\)(상수)	\(b\)(상수), 동차해와 중복될 경우는 \(b+cn\)
\(dn\)	\(b+cn\), 동차해와 중복될 경우는 \(a+bn+cn^{2}\)
\(dn^{2}\)	\(a+bn+cn^{2}\), 동차해와 중복될 경우는 \(a+bn+cn^{2}+dn^{3}\)
\(cd^{n}\)	\(bd^{n}\), 동차해와 중복될 경우는 \(bnd^{n}\)

동차해와 중복되는 경우 또는 중복되지 않더라도 원래대로 했을 때 특수해를 구할 수 없는 경우(일반적으로 특수해가 비동차항의 형태와 같지 않다)는 \(n\)을 곱해서 중복되지 않게 한다.

예: 점화식 \(a_{n}=a_{n-1}+n,\,a_{1}=2\)의 해는?

풀이: 동차점화식의 해는 \(f(n)=k\)이므로 특수해를 \(p(n)=dn+e\)라고 하자, \(p(n-1)=d(n-1)+e\)이므로$$dn+e=d(n-1)+e+n$$이고 \(d=n\), \(e\)는 임의의 상수이다. 이 상태로는 더이상 해를 구할 수 없다.

특수해를 \(p(n)=dn^{2}+en+f\)라고 하자. \(p(n-1)=d(n-1)^{2}+e(n-1)+f\)이므로$$dn^{2}+en+f=d(n-1)^{2}+e(n-1)+f$$이고 \(\displaystyle d=e=\frac{1}{2}\)이다. \(p(1)=a_{1}=2\)이므로 \(\displaystyle p(1)=\frac{1}{2}+\frac{1}{2}+f=2\)이고 \(f=1\)이다. 그러면 \(\displaystyle a_{n}=k+\frac{n^{2}+n}{2}+1\)이고 \(a_{1}=k+2=2\)이므로 \(k=0\)이고 따라서 \(\displaystyle a_{n}=\frac{n^{2}+n}{2}+1\)이다.

예: 점화식 \(a_{n}=3a_{n-1}+3\cdot2^{n-1},\,a_{1}=0\)의 해는?

풀이: 동차점화식의 해는 \(f(n)=k3^{n}\)이므로 특수해를 \(p(n)=c2^{n}\)이라 하자. \(p(n-1)=c2^{n-1}\)이므로$$c2^{n}=3c2^{n-1}+3\cdot2^{n-1}$$이고$$(2c-3c-3)2^{n-1}=-2(c+3)2^{n-1}=0$$이므로 \(c=-3\)이다. 그러면 \(a_{n}=k3^{n}-3\cdot2^{n}\)이고 \(a_{1}=3k-6=0\)이므로 \(k=2\)이고 따라서 \(a_{n}=2\cdot3^{n}-3\cdot2^{n}\)이다.

점화식이 \(a_{n}^{2}=a_{n-1}^{2}+2a_{n-2}^{2},\,a_{0}=0,\,a_{1}=1\)의 형태로 되어있으면 \(b_{n}=a_{n}^{2}\)로 치환해서 \(b_{n}\)에 대한 점화식을 구한 후, \(a_{n}\)에 대한 점화식을 구한다. 위의 점화식에서 \(b_{n}=a_{n}^{2}\)라고 하면 \(b_{n}=b_{n-1}+2b_{n-2},\,b_{0}=0,\,b_{1}=1\)이고, 이 점화식에 대한 특성방정식은 \(x^{2}-x-2=(x+1)(x-2)=0\)이고 그 해는 \(x=-1\), \(x=2\)이다. 그러면 \(b_{n}=k_{1}2^{n}+k_{2}(-1)^{n}\)이고, 초기조건 \(b_{0}=0,\,b_{1}=1\)을 이용하면$$\begin{align*}0&=b_{0}=k_{1}+k_{2}\\1&=b_{1}=2k_{1}-k_{2}\end{align*}$$이고 \(\displaystyle k_{1}=\frac{1}{3},\,k_{2}=-\frac{1}{3}\)이므로 \(\displaystyle b_{n}=\frac{2^{n}-(-1)^{n}}{3}\)이고 \(a_{1}=1\)이어야 하므로 따라서 \(\displaystyle a_{n}=\sqrt{b_{n}}=\sqrt{\frac{2^{n}-(-1)^{n}}{3}}\)이다.

점화식의 일반항을 구하는 과정은 미분방정식의 일반해를 구하는 과정과 비슷하다.

참고자료:

조합론과 그래프이론, 조성진, 김한두, 경문사

조합 및 그래프이론, 김정진, 교우사