[이산수학] (1) Recurrence Relation

Sequence와 Recurrence Relation은 우리말로 각각 수열과 점화식이다. 수열은 수의 나열을 뜻하는데, 나열된 수들간의 일관된 관계가 존재하지 않아도 괜찮다. 그러나 점화식은 이러한 수열의 항간의 일률적인 관계를 나타낸다. 

곰곰히 생각해보면 점화(recurrence)는 재발한다는 뜻인데, 점화식의 일반적인 구조를 살피면 좌변에는 다음 순번의 항이 위치하고 우변은 그 전번의 항이 위치한다. 그럼 좌변의 항은 다시 그 다음 항을 나타내기 위한 우변의 전번항이 된다. 

 

우선 First order Recurrence relation은 말그대로 1차 점화식이다. 수열 {an}을 an=s*an-1 + t 와 같은 일차식을 충족하는 항들의 나열이라고 가정할때, 이 관계식을 1차 점화식이라 부른다. 

 

위 그림은 1차 점화식의 예시다.

ex1) an=10, n>=1은 모든 n에 대해 an=10임을 나타낸다. s=0이고 t=10인 1차 점화식으로 해석된다.

ex2) an=an-1, n>=1 또한 모든 n에 대해 항들이 같은 수를 지닌다. s=1, t=0인 경우

ex3) s=3, t=-5

ex4) s=-root(2), t=pi

 

특정 수열이 주어졌을 때, 이들간의 일반항을 찾아내는 것이 우리의 목적이다. 

가령 3번째 예시는 Recurrence relation이 an=3*an-1-5로 형성되어있다. 이 때 우리는 귀납적으로 an = 3^n*an ... 의 일반항을 유도해낼 수 있다. 

 

first order recurrence relation에 해당하는 모든 수열은 결국 위와 같은 일반항 공식을 따를 수 밖에 없다. 이 때 특수한 경우가 s=1인 경우다. s!=1일때는 상수항은 일반적으로 상수항*등비수열의합이 되는데, 그럼 분모가 0이 되는 s=1에 대해선 정의될 수 없다. 따라서 s=1은 따로 분리하여 재정의한다. 이 때 an=a0+n*t가 된다. 

 

일반항 공식을 활용하여 first order recurrence relation의 일반항을 도출해낸 예시들이다. 

 

다음은 second order recurrence relation이다. 말그대로 이전 2개의 항이 현재 항의 값에 영향을 미치는 재발적인 식이다. an = s1 * an-1 + s2 * an-1 (n>=2)로 표현된다. 

세번째 예시는 second order recurrence relation의 대표적인 사례인 피보나치 수열이다. 

 

2차 점화식도 마찬가지로 점화식을 기반으로 일반항 식을 도출해내는 것이 목적이다. 

우선 second order recurrence relation과 관련된 4가지 proposition이 존재한다. 

1) an = s1*an-1 + s2*an-2, n>=2가 주어진 상황에서

2) 이차방정식 x^2 = s1*x + s2를 푼다.

3) 중근이 존재하는 특수한 상황이기에 해 r이 도출된다. 이 경우 일반항은 an = n* r^n이 된다.

 

두번째는 일반적인 상황에서의 일반항 도출법이다. 

1) an = s1*an-1 + s2*an-2, n>=2가 주어진 상황에서

2) 이차방정식 x^2 = s1*x + s2를 푼다.

3) 일반적 상황이기에 r1, r2 해가 도출된다. 이를 any constant c1, c2와 결합한 일반항을 만든다. 

an = c1*r1^n + c2*r2^n이 그 일반항이며 이는 second order relation을 충족한다. 

4) a0, a1에 대한 정보는 미리 주어질테니 n=0, n=1을 대입하여 c1, c2값을 찾아낸다.

 

이러한 특성들을 활용했을 때 우리는 일반항 an을 쉽게 찾아낼 수 있다.

n=0, n=1일때 a0 = c1 + c2, a1 = c1*r1 + c2*r2로 표현된다. 

 

예시1. a0=1, a1=2가 주어졌고 s1=-2, s2=3이다. 그럼 x^2 = -2x + 3의 해는 x=-3, 1이다. 

an = c1 * (-3)^n + c2 * (1)^n이다. a0=1=c1+c2, a1=2=-3c1+c2 이기 때문에 c1=-1/4, c2=5/4다. 이를 일반항에 대입할 경우 an = -1/4 * (-3)^n + 5/4 가 도출된다. 

예시2. a0=5, a1=3일때 s1=-3, s2=-2이다. x^2 = -3x - 2의 해는 x=-1,-2다. 

이는 an= c1 * (-1)^n  + c2 * (-2)^n으로 정리된다. a0=c1+c2=5, a1=-c1-2c2=3 이기에 이를 연립방정식으로 풀면 c2=-8, c1=13이 도출된다. an = -8 * (-2)^n + 13*(-1)^n이 답이다.

 

계산이 더 복잡하지만 과정은 똑같다. 생략.

 

중근의 경우는 아래 예시를 통해 일반항을 구하는 방법을 알아보자. 

 

예시4. 

1) an = 6an-1 -9an-2, a0=1, a1=6으로 주어졌다.

2) s1=6, s2=-9이기에 x^2 = 6x -9 를 풀면 해는 중근 x=3이 도출된다.

3) 그럼 일반항은 an = c1 * 3^n + c2 * n * 3^n이 된다. 

4) a0=c1=1, a1=c1*3+c2*3=6 이기에 c1=1, c2=1이 도출된다. 

5) 이를 일반항에 대입시 an=3^n + n*3^n = (n+1)*3^n이 도출된다.

 

사실 recurrence relation의 더욱 일반적인 형태는 뒤에 상수항이 붙는 것이다. 그러나 이해를 쉽게 하기 위해 상수항을 생략했다. 그러나 상수항이 붙는다고 방법이 크게 달라지는 것은 아니다. 

 

k가 고정된 양의 정수일 때 1^k + 2^k + ...의 일반항을 찾아보자.

k=1이라면 1+2+...+n이다. 이를 S라고 설정하면, S+S=2S=(n+1) * n이 된다. 따라서 S = n(n+1)/2로 풀이된다.

 

k=2일때도 method of difference를 사용하면 된다.

우리가 구하고 싶은 것은 sigma sum of r^2이다. 이를 위해 재료를 준비해보자. 

r(r+1)에 대해 sigma sum을 구하고, r(r-1)에 대한 sigma sum을 구해 서로를 빼보자.

끝에서 두번째 항과 앞에서 두번째 항만 남게되고, 이는 n*(n+1)이다. 

 

이번엔 sigma sum of r(r+1)(r+2)에 sigma sum of (r-1)r(r+1)을 차감해보자. 마찬가지로 앞뒤 두번째 항이 남게되는데, n(n+1)(n+2)다. 이를 정리해보면 sigma sum of (3r^2 + 3r) = n(n+1)(n+2)가 된다. 

 

자 그러면 우리가 원하는 것은 sigma sum of r^2이니 이미 알고 있는 sigma sum of r을 우변으로 넘긴 뒤 1/3만 곱해주면 된다. 그 값은 1/6*n(n+1)(2n+1)이다. 

 

k와 상관없이 하면 된다.