7.1 점화식 만들기

다음의 셈하기 문제에 대해 생각해 보자.

계단을 한 칸이나 두 칸 올라 $n$개의 계단을 오르는 방법의 수를 생각한다.

이 문제는 생각보다 그리 단순하지 않다.

이 글의 이전 부분에서 배운 방법들이 크게 도움이 되지 않는다. 그래서 이 문제는 다른 방법으로 접근할 필요가 있다. 

 

$n=1$인 경우, 분명히 1가지 방법만이 존재한다. $n=2$인 경우, 한 칸씩 두번 오르는 방법과 두 칸을 한 번에 오르는 2가지 방법 밖에 없다. $n=3$인 경우는 어떨까? 이 경우도 직접 일일이 세어보면 3가지 경우가 있다. 

 

일반적으로, $a(n)$을 $n$개의 계단을 오르는 방법의 수라고 하자. 직접 좀 더 세어 보면 다음과 같은 연속적인 수들을 찾을수 있다.

   $a(n) = 5, a(n) = 8, \cdots$

그러나 이렇게 해서 다 풀었다고 하기엔 뭔가 석연치 않다. 

 

🙄 뭔가 찜찜하다. 

 

$n=3$인 경우를 다시 분석해 본다. 계단을 오르기 위해 첫 발을 내딛을 때 두 가지 가능성이 있다.

 

   "한 칸이냐, 두 칸이냐 이것이 문제로다"

 

⑴ 첫 발의 디딤이 한 칸인 경우, 그 이후의 방법의 수는

  $a(1)$ 

이다.

⑵ 첫 발의 디딤이 두 칸인 경우, 그 이후의 방법의 수는

  $a(2)$ 

이다. 따라서 '합의 법칙'에 의해 $a(3) = a(1) + a(2)$ 이다. 

 

이것은 '일반항'이라고 불리는 $a(n)$을 위한 공식을 찾아 준것은 아니지만  $a(n-1)$과 $a(n-2)$으로부터 간접적으로 $a(n)$을 계산할 수 있도록 해 준다. 즉,
   $a(n) = a(n-1) + a(n-2) \ (n\geq3)$

이고 이것을 수열  $a(n)$의 '점화식'이라 한다. 

 

일반적으로 수열 $a(n)$에 대한 점화식은 $n$번째 항  $a(n)$과 그 이전 항들과의  관계에 대한 식으로 구성된다.

이 장의 주된 내용은 이 점화식으로부터 일반항을 구하는 방법에 관한 것이다. 점화식의 유형에 따른 대표적인 범주 안에서 점화식의 해법을 논의한다. 

---

점화식 만들기

일반적으로 점화식은 어떤 수열에 대한 귀납적 구조다. $n$개의 대상에 대한 방법의 수 $a(n)$을 계산하기 위해 $n$개 미만의 대상에 대한 방법의 수

   $a(1), a(2), \cdots, a(n-1)$

을 이용한다. 즉, 점화식은 $a(n)$과 그 이전 항들 사이의 관계로 표현되는 식이다. 그리고 점화식을 계산하는데, 초깃값 즉, 초기조건은 필수적으로 요구된다. 

 

점화식으로 모형화 할 수 있는 문제인지 어떻게 판단할 수 있을까?

그것은 $a(n)$과 인접한 항들 사이에 관계를 형성할 수 있는지를 확인함으로써 가능하다. 다음 문제를 통해 점화식을 형성하는 방식에 대한 감각을 잠시 경험해 보자.  이 문제는 3장에서 다루었던 '영국인의 모자 문제(3.3 영국인의 모자 문제(교란순열))'와 관련이 있다.

 

   "5개의 숫자 1, 2, 3, 4, 5를 일렬로 나열할 때 $i$번째 자리에 $i$가 오지 않는 경우의 수"

를 점화식을 이용하여 구해보려 한다. 

이 문제를 푸는 초보적인 방법은 다음과 같이 수형도를 그리는 것이다. 
     1  2  3  4  5  
     2  1  4  5  3
             5  3  4 
     2  3  1  5  4
             4  5  1
             5  1  4 
     2  4  1  5  3
             5  1  3
                 3  1
     2  5  1  3  4
             4  1  3
                 3  1
첫째 자리가 2인 경우, 조건에 맞는 것은 $12$가지가 있다. 첫째 자리에 3, 4, 5인 경우도 각각 $11$개씩 있으므로 구하는 경우의 수는 $44$가지이다. 

그 다음으로 '포함과 배제의 원리(3.2 일반화된 포함과 배제의 원리)'를 이용하는 것이다. 
   $\displaystyle D(n) = 5!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\right)= 44$

그리고 '점화식'을 이용할 수도 있다. 

 

실전에서 어떤 것을 선택해서 해결하느냐는 전적으로 자신의 선택에 달려있다. 전투에 참전한 병사는 훈련소에서 배운 내용을 긴급한 전투에서 사용할 때 자신의 판단력을 최대한 활용하여야 한다. 신속하고 정확한 것이 관건이다. 

 

자연수 $n$에 대하여 위의 조건 - $n$개의 숫자 $1, 2, \cdots, n$을 일렬로 나열할 때 $i$번째 자리에 $i$가 오지 않는 경우 - 에 맞게 나열하는 방법의 수를 $f(n)$이라고 하자. 이제 우리가 해야 할 일은 $f(n)$과 인접한 항 사이에 관계를 살펴보는 것이다. 

$n$번째 자리에 $i$가 올 경우, $n$이 위치할 수 있는 자리는 크게 두 가지로 분류된다.

즉, (1) $i$번째 자리이거나 (2) $i$번째 자리가 아닌 자리이다. 

(1)의  경우 : 각각의  i에 대하여

   $2, 3, \cdots, (i-1), \cdots, (i+1), \cdots, (n-1)$

을 조건을 만족하도록 나열하면 되므로 이때의 경우의 수는 

   $(n-1)\cdot f(n-2)$

이다. 

(2)의 경우 : 각각의 i에 대하여 

  $1, 2, \cdots, i, \cdots, (n-1)$

에 대하여 i자리에 n이 오지 않도록 나열하는 것이므로 이때의 경우의 수는

   $(n-1)\cdot f(n-1)$

이다. 이상에 의해 

   $f(n) = (n-1)\cdot (f(n-1)+f(n-2))$

이다.

 

이때 초기조건 $f(1)=0, f(2)=1$을 이용하여 $f(n)$을 구한다. 따라서 $f(5)=44$이다. 

 

위의 결과를 제3장에서 표기한 '교란순열 $D(n)$'으로 다시 쓰면

   $D(n) = (n-1)\cdot (D(n-1)+D(n-2))$

이다.

---

이것의 일반항은 어떻게 구할 수 있을까? 

산을 하나  넘었다고 생각했는데 또 하나의 산이 있다. 인생은 그런거다. 살아보니 그렇더라. 오르기 힘들면 잠시 쉬면 된다. 올라갈 힘과 마음이 생기면 그때 다시 오르자. 올라가면 아래를 내려다 볼 수 있다. 숲이 보인다. 

 

우선,  다음 사실을 이용한다.

 

   $D(n) - n\cdot D(n-1) = (-1)^n$

 

이 식의 양변을 $n!$로 나누어주고, 

   $\displaystyle b(n) = \frac{D(n)}{n!}$

이라 하면 

   $\displaystyle b(n)-b(n-1) = \frac{(-1)^n}{n!}$

이므로 이것은 가장 쉽게 풀리는 유형의 점화식이 된다. 

 

따라서

   $\displaystyle b(n) - b(1) = \frac{1}{2!}-\frac{1}{3!}+\cdots= 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots$

   $\displaystyle b(1) = \frac{D(1)}{1!}=0$

이다. 이것을 다시 $D(n)$에 관하여 정리하면 

   $\displaystyle D(n) = n!\cdot \left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots\right)$

임을 알 수 있다. 이것은 제3장(3.3 영국인의 모자 문제(교란순열))에서 구한 것과 동일하다. 

 

교란순열의 일반항을 구하기 위해서 우리는 다음 항등식을 사용하였다.

   $D(n)- n\cdot D(n-1) = (-1)^n$

 

우리는 모든 것들을 다 알 수는 없으므로 어떤 사실을 '모른다'는 것에 신경쓰기보다 그것을 알아가는 과정에 즐거움을 얻도록 하자. 이것은 삶에 있어  '신경 끄고/켜기 기술'의 일종이다.

 

이 식을 유도해 보자. 그런데, 약간 고민이다. 설명하고 넘어가야 할지? 독자들에게 연습문제로 남겨야 할지?

사실, 이 내용는 제7장의 2절, '점화식의 일반항 구하기(7.2 점화식의 일반항 구하기)'에서 등장할 내용이기 때문이다. 

 

여기까지 읽은 일반 독자를 위해 설명하기로 한다. 

 

   $\begin{align} D(n) &= (n-1)\cdot\left(D(n-1)+D(n-2)\right) \\ &= n\cdot D(n-1)-D(n-1)+(n-1)\cdot D(n-2)\end{align}$
이므로 다음과 같이 정리하는 것이 중요하다. 

   $D(n)-nD(n-1) = -\left(D(n-1)-(n-1)\cdot D(n-2)\right)$  

삶이란 같은 것을 새롭게 바라보는 마음임을 깨닫는다. 동일한 하루, 동일한 일과, 동일한 햇살, 동일한 사람들, ... 그것들을 날마다 새롭게 인식해 가야 한다. 그래야 지루함이 덜하다.

 

사실 이렇게 정리함으로써 매우 쉽게 해결된다. 편의상 $D(0)=1$로 정의하고,

   $a(n) = D(n) - nD(n-1) \ (n\geq1)$

이라고 하면 

   $a(n) = - a(n-1) \ (n\geq1)$

이 성립한다. 따라서 $a(n) = (-1)^n \ (n\geq1)$이다.

 

Boy! It's fabulous!