7.2 점화식의 일반항 구하기

점화식의 유형별로 일반항을 구하는 방식에 대해 논한다. 점화식의 일반항을 구하는 이론적인 절차는 보통 '선형점화식'과 '비선형점화식'으로 구분하여 진행된다. 그리고 특성방정식과 같은 생소한 용어들을 접하게 된다. 이 글에서는 일반 독자들이 쉽게 이해할 수 있도록 다음과 같은 대표적인 4가지 유형에 대해 배운다. 여기서 배운 내용들을 활용하면 이와 유사한 여러 점화식에 응용이 가능하다. 

   

(1) $a(n+1) - a(n) = f(n)$

(2) $a(n+1) = f(n) \times a(n)$

(3) $a(n+1) = k\cdot a(n) + f(n)$ (단, $f(n)$이 $k^n$꼴을 포함하지 않은 경우)

(4) $a(n+2) = p\cdot a(n+1) + q\cdot a(n)$

 

(1)의 경우 :

(1)-1. $a(1)=3, a(n+1) = a(n) + 2 \ (n\geq1)$

(1)-2. $\displaystyle a(1)=2, \frac{1}{a(n+1)} = \frac{1}{a(n)} + 3 \ (n\geq1)$

(1)-3. $a(1)=7, a(n+1) = a(n) + 4n \ (n\geq1)$

(1)-4. $a(1)=3, a(n+1) = a(n) + 2^n \ (n\geq1)$ 

 

위와 같은 유형의 문제들은 모두

   $a(n+1) - a(n) = f(n)$

꼴이다. 이러한 경우는 다음과 같이 해결 가능하다.

   $a(2)-a(1)=f(1)$

   $a(3)-a(2)=f(2)$

   $\cdots\cdots$

   $a(n)-a(n-1)=f(n-1)$

이므로 변변을 더하면 다음을 얻는다.

   $a(n) = a(1)+f(1)+f(2)+\cdots+f(n-1)$

 

(2)의 경우 : 
(2)-1. $a(1)=2, a(n+1) = 3a(n) \ (n\geq1)$

(2)-2. $\displaystyle a(1)=2, a(n+1) = \frac{n}{n+1}\cdot a(n) \ (n\geq1)$

(2)-3. $a(1)=2, a(n+1) = 3^n \cdot a(n) \ (n\geq1)$

 

위와 같은 유형의 문제들은 모두

   $a(n+1) = f(n)\times a(n)$

꼴이다. 이러한 경우는 다음과 같이 해결 가능하다.

   $a(2) = f(1)\times a(1)$

   $a(3) = f(2)\times a(2)$

   $\cdots\cdots$

   $a(n) = f(n-1)\times a(n-1)$

이므로 변변을 곱하면 다음을 얻는다.

   $a(n) = a(1)\times f(1)\times f(2)\times \cdots \times f(n-1)$

(3)의 경우 :
(3)-1. $a(1)=1, a(n+1) = 2a(n) + 3 \ (n\geq1)$
(3)-2. $a(0)=1, a(n) = 3a(n-1) + n^2 - 3 \ (n\geq1)$
(3)-3. $a(1)=8, a(n) = 3a(n-1) - 4n + 3\cdot 2^n \ (n\geq2)$

(3)-1 : 이 경우 부수적인 항 $f(n)$의 형태를 고려하여
   $a(n+1)+p = 2(a(n)+p)$
꼴로 고칠 수 있는지 생각해 보자. 그것이 가능하다면, 수열 $\left\{a(n)+p\right\}$는 공비 $k$인 등비수열이다. 그러므로 문제는 간단히 해결된다. 또한, 다음과 같은 방식도 가능하다. 
    $a(n+1)+p = k(a(n)+p) = k^2\cdot (a(n-1)+p) = \cdots = k^n\cdot (a(1)+p)$  

이 방식은 꼭 기억해 두자. (4)의 경우에서 활용된다.

(3)-2 : 이 경우 또한 부수적인 항 $f(n)$의 형태를 고려하여 
   $a(n)+A\cdot n^2+B\cdot n+C = 3(a(n)+A\cdot (n-1)^2+B\cdot (n-1)+C)$
꼴로 고칠수 있는지 생각해 보자. 그것이 가능하다면, 수열 $\left\{a(n)+A\cdot n^2+B\cdot n+C\right\}$는 공비 $k$인 등비수열이다. 문제는 간단히 해결된다. 

(3)-3 : 이 경우도 부수적인 항 $f(n)$의 형태를 고려하여
   $a(n)+A(n)+B+C\cdot 2^n = 3(a(n-1)+A\cdot(n-1)+B+C\cdot 2^{n-1})$
꼴로 고칠 수 있는지 생각해 보자. 그것이 가능하다면, 수열 $\left\{a(n)+A\cdot n+B+C \cdot 2^n \right\}$는 공비 $k$인 등비수열이다. 문제는 간단히 해결된다. 

다행스럽게도(?), (3)-1, (3)-2, (3)-3 모두 각각의 꼴로 바꿀수 있다.

 

(3)-3을 풀어본다.

나머지는 스스로 해보기 바란다. (3)-3에서 제안한 꼴로 고치기 위해서는 $A, B, C$를 구해야 한다. 우변을 전개하여 식을 정리한 후 주어진 식과 비교하면
   $A = -2, B = -3, C = 6$
이다. 따라서 
  $\displaystyle \begin{align} a(n)-2n-3+6\cdot 2^n &= \frac{3^n}{3} \left(a(1)-2×1-3+6\cdot 2\right) \\ &=  \frac{3^n}{3} \cdot 15 \\ &= 5\cdot 3^n \end{align}$
이므로 구하고자하는 일반항은
   $a(n) = 5\cdot 3^n + 2n + 3 - 6\cdot 2^n$
이다. 
부수적인 항의 형태를 잘 살펴서 꼴을 정하는 것이 중요하다.

 

우리가 가진 주변 환경과 소질, 능력 등을 판단하여 자신에게 중요하게 관련된 일들을 결정해야 한다. 전혀 완전히 다른 생뚱맞은 것들을 시도해 볼 수는 있겠지만 이 경우는 좌절과 시행착오가 더 클 수 있다는 것을 각오해야 한다. 자신 스스로 그 가치를 더 높게 여긴다면 남들의 조롱 따위쯤은 신경꺼야 한다. 그러나 만약 오만이나 만용이라면 인생을 잘 살았다고 말할 수 없다. 노력이나 인내로 모든 것이 다 이룰 수 있는 것은 아니라는 것은 확실하다. 그러나 자신의 원하는 결과를 얻도록 개연성을 높여주는 요소로 작용할 확률은 높은 편이다. 노력에 대해 너무 신화적인 것도 너무 부정적인 것도 이치에 맞지 않다. 때로는 너무 애쓰지 않는 것도 필요하다. 유연하게 살자!

 

마지막으로 (4)의 경우에 대하여 생각해 보자. 

 

(4)의 경우 : 

(4)-1. $a(1)=1, a(2)=4, a(n+2) = 3a(n+1) - 2a(n) \ (n\geq1)$

(4)-2. $a(1)=1, a(2)=1, a(n+2) = a(n+1) + a(n) \ (n\geq1)$

(4)-3. $a(1)=1, a(2)=2, a(n+2) = 6a(n+1) - 9a(n) \ (n\geq1)$  

 

(4)의 경우, 서로 다른 두 실수(복소수인 경우는 이 글에서 다루지 않는다.) $u$와 $v$에 대하여 $p=u+v, q=-uv$인 경우

   $a(n+2)-u\cdot a(n+1) = v\cdot (a(n+1)-u\cdot a(n))$

   $a(n+2)-v\cdot a(n+1) = u\cdot (a(n+1)-v\cdot a(n))$

꼴들로 고칠수 있다. 이 두 식을 이용하여 일반항 $a(n)$을 구할 수 있다. 

 

(4)-1과 (4)-2 중에서 (4)-2를 풀어본다. 이것은 '피보나치 수열'의 점화식으로 잘 알려져 있다. (4)-1은 쉬우므로 연습문제로 남겨둔다. 

 

      $a(1)=1, a(2)=1, a(n+2) = a(n+1)+a(n) \ (n\geq1)$

$u+v=1, uv=-1$인 만족하는 실수 $u, v$가 존재한다. 이것은 $x^2-x-1=0$의 두 실근이다. 이 이차방정식의 두 실근은 무리수를 포함하는 다소 복잡한 형태지만 분명히 존재한다. 

 

사실,

   $x² - x - 1 = 0$

을 $a(n+2) - a(n+1) - a(n) = 0$의 '특성방정식'이라고한다. 

 

이제, 다음과 같은 꼴로 고칠수 있다.

   $a(n+2)-u\cdot a(n+1) = v(a(n+1)-u\cdot a(n))$

   $a(n+2)-v\cdot a(n+1) = u(a(n+1)-v\cdot a(n))$  

 

이 두 식으로 부터 다음을 얻는다.

   $a(n+2)-u\cdot a(n+1) = v^n(a(2)-u\cdot a(1))$

   $a(n+2)-v\cdot a(n+1) = u^n(a(2)-v\cdot a(1))$

이 두 식을 서로 연립하면 다음의 일반항을 얻는다.

 

   $(u-v) \cdot a(n) = u^n - v^n$, $\displaystyle u=\frac{1+\sqrt{5}}{2}, v=\frac{1-\sqrt{5}}{2}$

 

   $\displaystyle \therefore a_n = \frac{1}{\sqrt 5} \left(\left(\frac{1+\sqrt 5}{2} \right)^n -  \left(\frac{1-\sqrt 5}{2} \right)^n \right)$

 

일반 독자에게 계산과정를 모두 보여 주지 못한 것에 대해 양해를 구한다. 위의 경우 연립에 의한 최종 결과가 의아할 수 있다. $1-u=v, 1-v=u$라는 사실을 이용했다. 이제서야 무릎을 탁치는 독자가 있을지도 모르겠다. 이것으로 계산의 무한궤도에서 구조되었다면  다행이다. 

 

4)-3 의 경우는 $u=v=3$이다. 이때,

   $a(n+2) = 6a(n+1) - 9a(n)$

은 다음 꼴로 고쳐진다.

   $a(n+2)-3a(n+1) = 3(a(n+1)-3a(n))$

따라서,

  $a(n+2)-3a(n+1) = 3ⁿ(a(2)-3a(1)) = -3^n$ 

이므로 양변을 3^{n+2}으로 나누자. 이때

   $\displaystyle b(n) = \frac{a(n)}{3^n}$

으로 두면,

   $\displaystyle b(n+2)-b(n+1) = - \frac{1}{9}$

이다. 이것은 쉽게 해결된다. $b(n)$은 공차 $\displaystyle -\frac{1}{9}$를 갖는 등차수열이다.

   $\displaystyle b(n) = \frac{4-n}{9}$

이므로

   $\displaystyle a(n) = 3^{n-2}(4-n)$

를 얻는다. 

위의 풀이들을 잘 관찰하면 선형과 비선형으로 순차적인 몇 가지 절차로 나누어 점화식의 문제를 해결할수 있는 방식을 얻게 된다. 그러한 방식을 깊이있게 알기를 원한다면 조합론 책들을 참조하기 바란다. 나는 수열에 대한 지식을 어느정도 알고 있는 일반 독자가 이해 가능하도록 설명한 것이다. 

예제 (3)-3을 약간 수정한  다음 문제를 풀어보자.

     $a(0)=3, a(n) = 3a(n-1) - 4n + 3^n (n\geq1)$

 

위의 문제에서 부가적인 항을 살펴 보면 $3^n$이 등장한다. 이것은 $a(n-1)$의 계수 3과 일치한다. 실은 특성방정식

   $x-3=0$

을 만족하는 해 3과 일치한다는 표현이 더 일반적이다. 이때는 위에서 제시한 꼴처럼 고칠 수 없다. 

 

어떻게 해야할까? 

 

(4)의 경우 또한, 부가적인 항을 추가하여 다음과 같은 문제도 가능하다.

     $a(0)=3, a(1)=8, a(n) - 3a(n-1) + 2a(n-2) = 2^n \ (n\geq2)$  

어떻게 풀어야 할까? 

 

이것을 해결할 수 있는 아이디어는 앞에서 잠시 제시되었다. 한번 도전해 보기 바란다. 제7장의 마지막 절(7.3 생성함수와 점화식)에 이 문제에 대한 풀이를 추가한다.