[include(틀:이산수학)] [목차] == 개요 == {{{+1 [[漸]][[化]][[式]] / Recurrence relation}}} 어떤 [[수열]]의 각각의 항들의 관계를 나타낸 식이다. 점화식을 만족시키는 수열을 점화식의 '''해'''라 하고, 이 해를 찾는 것을 '''점화식을 푼다'''고 말한다. 예로 점화식 [math(a_{n+1} = a_n + d)]은 [math(a_n = a_0 + nd)] (혹은 [math(a_1 + (n-1)d)])로 초항에 따라 유일한 해가 결정되고, 공차가 [math(d)]인 등차수열을 의미한다. [[벡터]], [[행렬(수학)|행렬]] 등 다른 수학적 대상의 열을 묘사하는 점화식들도 생각할 수 있고, 마치 [[파스칼의 삼각형]] 항등식처럼 2개 이상의 변수를 갖는 수열에 대해서 생각할 수도 있다. 보통 점화식은 [math(n)]번째의 항을 이전에 나온 항들로 나타내는 공식으로 나타나고, 이 점화식을 만족시키는 수열은 초깃값에 따라 유일하게 결정된다. 이렇게 수열을 정의하는 것을 '''[[수열의 귀납적 정의]](recursive definition)'''라 한다. 이 방법을 사용하면 일반항으로 수열을 나타내는 것보다 훨씬 다양한 수열을 나타낼 수 있다. 다만 모든 점화식이 [math(n)]번째 항을 명확한 형태로 묘사하는 것은 아니고, 이런 경우에는 둘 이상의 해가 존재할 수 있으며 만족시키는 수열을 모두 구하는 것이 목표가 될 수도 있다. 물론 명시적인 점화식의 경우에도 항을 찾을 수 있을 뿐이지 수열의 일반항을 정리해서 점화식을 푸는 건 쉬운 일이 아니다. 상수 계수 선형점화식을 비롯한 교과서의 몇몇 예외를 제외하면 점화식의 대수적인 일반항(closed form)은 웬만해선 존재하지 않는다고 보아도 좋다. [[조합론]]에서 [math(n)]에 따라 변화하는 어떤 대상의 개수를 구하고 싶지만 직접 일반항 계산이 어려울 때, 점화식을 먼저 만들어놓고 그 다음 점화식을 풀어 개수를 구하는 방식이 많이 쓰인다. [[피보나치 수열]]이나 [[카탈란 수]] 등등의 예시가 있다. 물론 이런 쉬운 경우를 제외하면 현실적으로는 점화식만을 세우는 것도 컴퓨터 프로그램으로 [math(n)]번째 항을 계산할 수 있게 해 주기 때문에 위업이며([[동적 계획법]]과 연관된다), 점근적 성장(asymptotic)을 알아내는 것이 최종목표로 간주된다. [[미분방정식]]이 연속적으로 변하는 대상을 묘사하는 수학적 도구인 것과 비슷하게, 점화식은 이산적으로 변하는 대상을 묘사할 수 있다. 미분방정식이 다루는 연속적 동역학계(continuous dynamical system)와 대비되게 [math(a_{n+1} = f(a_n) )] 류의 식으로 결정되는 시스템을 '''이산 동역학계(discrete dynamical system)'''라는 이름으로 부른다. 비교적 근래에 발생한 이 분야는 미분방정식에 비해 덜 알려져서 여러 분야에서 응용가능한 잠재력이 있지만, 실상을 들여다보면 여기도 미분방정식 이상으로 [[카오스]]로 가득찬 혼돈의 세계라서 쉽사리 접근하기는 힘들다. 경우에 따라서는 '''점화식이 [[미분방정식]]보다 풀기가 어렵다'''고 말하는 사람들도 많다. 2020년 현재, 명목상으로는 고교 과정에서 빠졌으나, 수1의 수열단원에서는 이름만 바꾼 '수열의 귀납적 정의'로 등장한다. 게다가 여전히 몇몇 학원가나 사교육 등지에서는 '발화식'이라는 명칭을 직접적으로 사용하는것이 자연스럽게 여겨질정도니 사실상 안빠지고 계속 교육과정에 남아있다고해도 무방하다. 내신에서는 간단한 명제를 수학적 귀납법으로 증명하는것이 서술형 단골일뿐더러 빈칸을 뚫어놓고 객관식으로도 출제될수있다. 나중에가면 다른 주요과목을 챙기느라 빵꾸가 난부분을 채우기 힘들어지니 진도를 나갈때 꼭꼭 챙겨두자. == 선형 점화식 == 수열 [math(\{a_n\})]에 대하여 [math(\ a_{n+k}+c_1 a_{n+k-1}+c_2 a_{n+k-2}+\cdots+c_k a_n=f(n) )] 의 형태의 점화식을 선형 점화식이라고 한다. (단, [math( c_1, \cdots,c_k)]는 상수, [math(c_k \neq 0 )]) 고교과정 내의 거의 모든 종류의 점화식은 선형점화식의 일부로 간주할 수 있다. 여기서 [math(f(n)=0)]이면 동차 선형 점화식이라 하고, [math(f(n) \neq 0)]이면 비동차 선형 점화식이라 한다. 비동차 선형 점화식을 동차 선형 점화식으로 바꾸면 일반항을 구하기가 쉬워지는데, 그렇게 만드는 방법은 특수해를 구하는 것이다. 특수해 [math(\{b_n\})]을 구했다고 하자.[* 특수해를 구하는 요령은 f(n)이 상수이면 보통 어떤 상수로 특수해를 추측해 보는 것이고, f(n)이 m차식이면 특수해도 m차식으로 추측해 보는 것이다. 하지만 일반적인 방법은 없다.] 그리고 새로운 수열 [math(\{x_n\})]을 [math(x_n = a_n -b_n)]으로 정의한다. 그러면 수열[math(\{x_n\})]에 대한 점화식은 [math(\ x_{n+k}+c_1 x_{n+k-1}+...+c_k x_n=0 )]이 된다. 이로써 특수해만 구할 수 있다면 비동차 선형 점화식은 동차 선형 점화식으로 바꿀 수 있음을 알 수 있다. 이때, [math(r )]에 대한 방정식 [math(r^k+c_1r^{k-1}+\cdots+c_k=0 )]을 이 점화식의 특성방정식이라 한다. 결론부터 말하자면, 특성방정식의 근이 [math(\alpha_1, \alpha_2, \cdots , \alpha_k )] 이면 [math(x_n )]은 [math({\alpha_1}^n, {\alpha_2}^n, \cdots , {\alpha_k}^n )]의 일차결합으로 나타내어진다. 즉, [math(x_n )]의 가능한 모든 일반항은 [math(x_n=A_1{\alpha_1}^n + A_2{\alpha_2}^n+ \cdots + A_k{\alpha_k}^n )]로 나타내어진다. ([math(A_1, A_2, \cdots ,A_k )]는 상수) 따라서 [math(a_n=b_n+x_n=b_n+A_1{\alpha_1}^n + A_2{\alpha_2}^n+ \cdots + A_k{\alpha_k}^n )]이 된다. 단, 여기서 [math(\alpha_1, \alpha_2, \cdots , \alpha_k )]는 모두 서로 달라야 한다(선형 독립). 만약 이 중 서로 같은 것들이 있다면, 즉 특성방정식이 중근을 갖는다면 일반항은 약간 달라진다. 어떤 근 [math(\beta )]가 중복수가 m인 중근이라면 [math({\beta}^n, n{\beta}^n, \cdots , n^{m-1}{\beta}^n )]으로 대신해 일차결합을 해야 한다. === 동차선형방정식의 해집합 증명 === 분야마다 다른 다양한 방법이 있다. {{{#!folding 귀납법과 치환을 이용한 초등적 증명 우선 [math( a_{n+1} = c a_{n} + f(n) (c \neq 0))] 꼴의 비동차 선형 점화식을 푸는 방법을 정리한다. 양변을 [math(c^{n+1})]로 나누면 [math( a_{n+1}c^{-n-1} = a_{n}c^{-n} + f(n)c^{-n-1})] 이므로 계차수열을 이용해 [math( a_n = c^n (a_0 + \sum f(m) c^{-m-1}))]로 풀 수 있다. 이제 본 문제로 돌아가, 차수에 대한 귀납법을 사용한다. 특성방정식이 [math(r^k+c_1r^{k-1}+\cdots+c_k=(r-\alpha)(r^{k-1}+d_1r^{k-2}+\cdots+d_{k-1}=0))]으로 인수분해된다고 하자. 그러면 [math(b_n = a_{n+1} - \alpha a_{n})]으로 정의한 수열은 점화식 [math( b_{n+k-1} + d_1 b_{n+k-2} + \cdots + d_{k-1} b_n = 0 )]을 만족한다! [math(b_n)]에 대해 귀납가설을 적용해 [math(b_n)]을 [math(n^{k-1} \beta^n)] 등의 일차결합으로 나타내고, 이제 위에서 언급한 비동차방정식 [math( a_{n+1} = \alpha a_n + b_n )]을 푼다. 본래 방정식의 특성방정식이 중근이 없으면 [math(a_n)]은 [math( \sum \alpha^{n-m} \beta^m)]과 [math(\alpha^n)] 꼴의 일차결합으로 이루어지므로 증명된다. 중근이 있다면 [math(m^{k-1} (\beta/\alpha)^m)] 꼴의 수열의 합을 구해야 하는 등 조금 더 귀찮다.}}} {{{#!folding 생성함수 이용 수열 [math(a_n)]의 '''[[생성함수]](generating function)'''는 멱급수 [math( \sum_{n=0}^{\infty} a_n x^n)]으로 정의된다. [* 급수가 수렴 안 해도 괜찮냐고 의문을 가질 수 있지만, FM대로라면 생성함수는 이 급수가 수렴하건 안 하건 항상 정의될 수 있다. 동차 선형점화식의 경우는 [math(|a_n| \le K^n )]으로 유계를 주는 것이 가능하므로 급수가 항상 수렴해 통상의 [[테일러 급수]]로 생각해도 상관이 없다.] [math(a_n)]의 생성함수를 [math(A(x))]라 하자. 만약 [math(a_n)]이 점화식 [math( a_{n+k}+c_1 a_{n+k-1}+c_2 a_{n+k-2}+\cdots+c_k a_n=0)]을 만족한다면, [math(C(x) = 1 + c_1 x + c_2 x^2 + \cdots + c_k x^k)]에 대해 식 [math(D(x)=A(x)C(x))]에서 [math(x^{n+k})]의 계수는 [math(a_{n+k}+c_1 a_{n+k-1}+c_2 a_{n+k-2}+\cdots+c_k a_n=0)]이다. 즉 [math(D(x))]는 [math((k-1))]차 이하의 다항식이어야 하고, [math(A(x)=D(x)/C(x))]로 쓸 수 있다. 유리식 [math(A(x)=D(x)/C(x))]의 계수를 다시 전개하기 위해서는 [[부분분수분해]]를 사용한다. 주어진 점화식의 특성근이 [math(\alpha_i)]들이라면 [math(C(x)=\prod (1-\alpha_i x)^{e_i} )]꼴로 인수분해되므로, 부분분수분해를 하면 [math(A(x))]를 [math((1-\alpha x)^{-k})]들의 일차결합으로 나타낼 수 있다. 마지막으로 다음 항등식 [math(\frac{1}{(1-\alpha x)^k}= \sum_{n=0}^{\infty} \binom{n+k-1}{k} \alpha^n x^n )] 을 이용한다. 이 전개식의 증명은 [math(k)]에 대한 귀납법, [[테일러 정리]], 생성함수 전문가라면 좌변을 '조합적으로' [[중복조합]]으로 해석하는 등 어떻게 해도 좋다.}}} {{{#!folding 행렬의 조르당 형식 이용 벡터 [math(v_n=(a_n,a_{n+1},\cdots,a_{n+k-1})^t)]을 생각하고, 이에 대한 점화식을 다음과 같이 구성한다. [math( v_{n+1} = \left( \begin{array}{c} a_{n+1} \\ a_{n+2} \\ \vdots \\ \vdots \\ a_{n+k} \end{array} \right) = \left( \begin{array} {ccccc} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\-c_k & -c_{k-1} & -c_{k-2} & \cdots & - c_{1} \\ \end{array} \right) v_n )] [math(A)]를 저 안에 주어진 행렬이라고 하면 [math(v_n = A^n v_0)]으로 점화식이 풀린다. 이제 [[조르당 분해]]를 이용해 [math(A^n)]을 구하면 되는데, 한편 [math(A)]가 동반 행렬(companion matrix)임을 관찰하면 [math(A)]의 [[조르당 분해]]는 항상 최대 크기의 블록들로 나뉘어짐을 알 수 있다. 여기까지 왔으면 사실상 끝.}}} == 점화식과 이산 동역학계 == 점화식이 '이산 동역학계'라는 이름으로 간주된 것은 상당히 현대적인 관점으로, [[미분방정식]]으로 변화를 바라보는 사고방식이 무르익을 즈음에 이것이 이산적인 형태에 적용되었다고 볼 수 있다. 상미분방정식으로 형성되는 [[복잡계]]가 변화율이 연속적인 시간과 현재상태에 따라 결정되는 [math(x'(t) = F(x,t))]의 식을 하고 있듯이, [math(a_{n+1}=f(a_n,n))]의 식은 [math(n)]을 이산적인 시간으로 간주했을 때 어떻게 [math(a_n)]의 상태가 바뀌는지를 묘사한다고 볼 수 있기 때문이다. 개념적으로는 미분을 모르더라도 이해할 수 있는 내용이지만, 이런 식의 해석은 마르코프 연쇄(Markov chain)나 아래 얘기할 로지스틱 사상(logistic map) 등을 생각할 19세기 말에야 이루어졌다. 이러한 관점에서 보면 [math(a_n)]의 식을 풀지 못해도, 수렴, 발산, 진동과 같은 추이만 파악해도 충분한 성과라 볼 수 있겠지만... 점화식의 경우에는 이것이 불가능해지는 [[카오스 이론|카오스]]가 정말 간단한 형태에서조차 등장한다. 함수 로지스틱 사상(logistic map)은 복잡계 [math( a_{n+1} = f(a_n) )]을 결정짓는 다음의 함수로 [math( f(x) = rx(1-x), \quad 0