점화식
1. 개요
recurrence relation · 漸化式
어떤 수열의 각각의 항들의 관계를 나타낸 식이다. 점화식을 만족하는 수열을 점화식의 '''해'''라 하고, 이 해를 찾는 것을 '''점화식을 푼다'''고 말한다. 예로 점화식 $$a_{n+1} = a_n + d$$은 $$a_n = a_0 + nd$$ (혹은 $$a_1 + (n-1)d$$)로 초항에 따라 유일한 해가 결정되고, 공차가 $$d$$인 등차수열을 의미한다. 벡터, 행렬 등 다른 수학적 대상의 열을 묘사하는 점화식들도 생각할 수 있고, 마치 파스칼의 삼각형 항등식처럼 2개 이상의 변수를 갖는 수열에 대해서 생각할 수도 있다.
보통 점화식은 $$n$$번째의 항을 이전에 나온 항들로 나타내는 공식으로 나타나고, 이 점화식을 만족하는 수열은 초깃값에 따라 유일하게 결정된다. 이렇게 수열을 정의하는 것을 '''수열의 귀납적 정의(recursive definition)'''라 한다. 이 방법을 사용하면 일반항으로 수열을 나타내는 것보다 훨씬 다양한 수열을 나타낼 수 있다. 다만 모든 점화식이 $$n$$번째 항을 명확한 형태로 묘사하는 것은 아니고, 이런 경우에는 둘 이상의 해가 존재할 수 있으며 만족하는 수열을 모두 구하는 것이 목표가 될 수도 있다. 물론 명시적인 점화식의 경우에도 항을 찾을 수 있을 뿐이지 수열의 일반항을 정리해서 점화식을 푸는 건 쉬운 일이 아니다. 상수 계수 선형점화식을 비롯한 교과서의 몇몇 예외를 제외하면 점화식의 대수적인 일반항(closed form)은 웬만해선 존재하지 않는다고 보아도 좋다.
조합론에서 $$n$$에 따라 변화하는 어떤 대상의 개수를 구하고 싶지만 직접 일반항 계산이 어려울 때, 점화식을 먼저 만들어놓고 그 다음 점화식을 풀어 개수를 구하는 방식이 많이 쓰인다. 피보나치 수열이나 카탈란 수 등등의 예시가 있다. 물론 이런 쉬운 경우를 제외하면 현실적으로는 점화식만을 세우는 것도 컴퓨터 프로그램으로 $$n$$번째 항을 계산할 수 있게 해 주기 때문에 위업이며(동적 계획법과 연관된다), 점근적 성장(asymptotic)을 알아내는 것이 최종목표로 간주된다.
미분방정식이 연속적으로 변하는 대상을 묘사하는 수학적 도구인 것과 비슷하게, 점화식은 이산적으로 변하는 대상을 묘사할 수 있다. 미분방정식이 다루는 연속적 동역학계(continuous dynamical system)와 대비되게 $$a_{n+1} = f(a_n) $$ 류의 식으로 결정되는 시스템을 '''이산 동역학계(discrete dynamical system)'''라는 이름으로 부른다. 비교적 근래에 발생한 이 분야는 미분방정식에 비해 덜 알려져서 여러 분야에서 응용가능한 잠재력이 있지만, 실상을 들여다보면 여기도 미분방정식 이상으로 카오스로 가득찬 혼돈의 세계라서 쉽사리 접근하기는 힘들다. 경우에 따라서는 '''점화식이 미분방정식보다 풀기가 어렵다'''고 말하는 사람들도 많다.
2020년 현재, 고교 과정에서 빠졌으므로 수능을 목표로 한다면 꼭 배울 필요는 없다. 그러나 알아두면 문제 풀 때 매우 도움이 되니 웬만하면 공부하는 게 두고두고 좋을 것이다.
2. 선형 점화식
수열 $$\{a_n\}$$에 대하여 $$\ a_{n+k}+c_1 a_{n+k-1}+c_2 a_{n+k-2}+\cdots+c_k a_n=f(n) $$ 의 형태의 점화식을 선형 점화식이라고 한다. (단, $$ c_1, \cdots,c_k$$는 상수, $$c_k \neq 0 $$)
고교과정 내의 거의 모든 종류의 점화식은 선형점화식의 일부로 간주할 수 있다.
여기서 $$f(n)=0$$이면 동차 선형 점화식이라 하고, $$f(n) \neq 0$$이면 비동차 선형 점화식이라 한다. 비동차 선형 점화식을 동차 선형 점화식으로 바꾸면 일반항을 구하기가 쉬워지는데, 그렇게 만드는 방법은 특수해를 구하는 것이다.
특수해 $$\{b_n\}$$을 구했다고 하자.[1] 그리고 새로운 수열 $$\{x_n\}$$을 $$x_n = a_n -b_n$$으로 정의한다. 그러면 수열$$\{x_n\}$$에 대한 점화식은 $$\ x_{n+k}+c_1 x_{n+k-1}+...+c_k x_n=0 $$이 된다. 이로써 특수해만 구할 수 있다면 비동차 선형 점화식은 동차 선형 점화식으로 바꿀 수 있음을 알 수 있다.
이때, $$r $$에 대한 방정식 $$r^k+c_1r^{k-1}+\cdots+c_k=0 $$을 이 점화식의 특성방정식이라 한다. 결론부터 말하자면, 특성방정식의 근이 $$\alpha_1, \alpha_2, \cdots , \alpha_k $$ 이면 $$x_n $$은 $${\alpha_1}^n, {\alpha_2}^n, \cdots , {\alpha_k}^n $$의 일차결합으로 나타내어진다. 즉, $$x_n $$의 가능한 모든 일반항은 $$x_n=A_1{\alpha_1}^n + A_2{\alpha_2}^n+ \cdots + A_k{\alpha_k}^n $$로 나타내어진다. ($$A_1, A_2, \cdots ,A_k $$는 상수) 따라서 $$a_n=b_n+x_n=b_n+A_1{\alpha_1}^n + A_2{\alpha_2}^n+ \cdots + A_k{\alpha_k}^n $$가 된다.
단, 여기서 $$\alpha_1, \alpha_2, \cdots , \alpha_k $$는 모두 서로 달라야 한다. 만약 이 중 서로 같은 것들이 있다면, 즉 특성방정식이 중근을 갖는다면 일반항은 약간 달라진다. 어떤 근 $$\beta $$가 중복수가 m인 중근이라면 $${\beta}^n, n{\beta}^n, \cdots , n^{m-1}{\beta}^n $$으로 대신해 일차결합을 해야 한다.
2.1. 동차선형방정식의 해집합 증명
분야마다 다른 다양한 방법이 있다.
귀납법과 치환을 이용한 초등적 증명
본래 방정식의 특성방정식이 중근이 없으면 $$a_n$$은 $$ \sum \alpha^{n-m} \beta^m$$과 $$\alpha^n$$ 꼴의 일차결합으로 이루어지므로 증명된다. 중근이 있다면 $$m^{k-1} (\beta/\alpha)^m$$ 꼴의 수열의 합을 구해야 하는 등 조금 더 귀찮다.}}}
생성함수 이용
을 이용한다. 이 전개식의 증명은 $$k$$에 대한 귀납법, 테일러 정리, 생성함수 전문가라면 좌변을 '조합적으로' 중복조합으로 해석하는 등 어떻게 해도 좋다.}}}
행렬의 조르당 형식 이용
$$A$$를 저 안에 주어진 행렬이라고 하면 $$v_n = A^n v_0$$으로 점화식이 풀린다. 이제 조르당 분해를 이용해 $$A^n$$을 구하면 되는데, 한편 $$A$$가 동반 행렬(companion matrix)임을 관찰하면 $$A$$의 조르당 분해는 항상 최대 크기의 블록들로 나뉘어짐을 알 수 있다. 여기까지 왔으면 사실상 끝.}}}
3. 점화식과 이산 동역학계
점화식이 '이산 동역학계'라는 이름으로 간주된 것은 상당히 현대적인 관점으로, 미분방정식으로 변화를 바라보는 사고방식이 무르익을 즈음에 이것이 이산적인 형태에 적용되었다고 볼 수 있다. 상미분방정식으로 형성되는 복잡계가 변화율이 연속적인 시간과 현재상태에 따라 결정되는 $$x'(t) = F(x,t)$$의 식을 하고 있듯이, $$a_{n+1}=f(a_n,n)$$의 식은 $$n$$을 이산적인 시간으로 간주했을 때 어떻게 $$a_n$$의 상태가 바뀌는지를 묘사한다고 볼 수 있기 때문이다. 개념적으로는 미분을 모르더라도 이해할 수 있는 내용이지만, 이런 식의 해석은 마르코프 연쇄(Markov chain)나 아래 얘기할 로지스틱 사상(logistic map) 등을 생각할 19세기 말에야 이루어졌다. 이러한 관점에서 보면 $$a_n$$의 식을 풀지 못해도, 수렴, 발산, 진동과 같은 추이만 파악해도 충분한 성과라 볼 수 있겠지만... 점화식의 경우에는 이것이 불가능해지는 카오스가 정말 간단한 형태에서조차 등장한다.
함수 로지스틱 사상(logistic map)은 복잡계 $$ a_{n+1} = f(a_n) $$을 결정짓는 다음의 함수로
$$ f(x) = rx(1-x), \quad 0
여기서 $$r$$은 $$0<r<4$$ 범위 내의 매개변수이다. 이 식은 생태학에서 생물의 개체수 변화를 설명하는 로지스틱 방정식의 이산적인 형태로, 양변을 $$x$$로 나누면 바로 유사성을 볼 수 있다. 하지만 간단히 초등함수로 풀려서 그래프 개형도 단순한 로지스틱 방정식의 경우와는 다르게, 이 수열이 보이는 패턴은 수렴하거나, 여러 개 값을 오가며 진동하거나, 어느 것도 아니거나 매우 다양하다. 심지어 이 패턴은 초기값 $$a_0$$에 따라 겉잡을 수 없이 변한다. 여기에 매개변수 $$r$$까지 변화시키면 더욱 기가 막힌 일들이 벌어지는데, $$r$$이 늘어날수록 진동하는 값의 궤도 개수가 2, 4, 8, 16, ... 2배로 계속 늘어나다가, 어느 지점에선 순간적으로 사라지는데 또 랜덤하게 주기성을 갖는 수열이 튀어나온다던가... 이런 정줄놓은 행동을 더 자세히 보려면 분기도(bifurcation diagram)를 찾아보면 알 수 있다.하여튼 점화식의 관점에서 보자면 고작 변수 하나짜리 이차식에서 이런 카오스가 나오는 것인데, 이걸 보면 3차원까지 가야[2] 카오스가 나오는 미분방정식에 비해서도 더 어렵다고 느껴질 수 있다. 이 카오스의 존재는 '''일반적인 경우에 점화식을 쉽게 푸는 것이 애시당초 불가능'''했음을 의미하기도 한다. 그렇다고 점화식의 연구가 의미없는 것은 아닌 게, 이산 동역학계에 대한 이러한 관찰들이 카오스 이론을 새로운 방식으로 확장시켰기 때문이다. 예로 상기한 2차 점화식을 복소수로 넓혀 생각한 망델브로 집합(Mandelbrot set)은 점화식
$$ z_{n+1} = z_n^2 + c $$
이 발산하지 않는 초기값 $$z_0 \in \mathbb{C}$$의 집합으로 정의되는 집합으로, 자기닮음 즉 프랙탈의 특성을 갖고 있다. 브누아 망델브로(Benoît B. Mandelbrot, 1924-2010)는 사실상 이 집합을 계기로 프랙탈 이론을 창안하였는데, 이 이론은 다른 점화식들의 분기에 대해서도 프랙탈 현상을 관찰할 수 있음을 증명해냈고 더욱 나아가선 이산 동역학계와 프랙탈과의 근본적 관계성을 시사하기도 했다.