안녕하세요, 예전에 다음에서 오유출처 재밌는 글들이 종종 화제글로 올라오길래 몇번 눈팅하다가 바빠져서 한동안 못왔는데 최근 이런저런 사건사고들 내용을 좀 보다가 다시 오게됬네요. 그러다 우연찮게 과학 게시판을 봤는데 좋더군요. 네이버에서 지식인/블로그로 활동을 했는데 해킹당하고(외국이라 본인인증도 안되고...) 한동안 접었는데 여기에 오니 좋은 글도 많고 질문들도 흥미로운게 많아서 한번 활동해볼까 합니다. 네이버 계정도 해외계정으로 하나 다시파서 여기 올리는 글은 블로그에도 올릴 예정이고.. 블로그에는 수학/과학 말고도 음악/영어 등 다른 글들도 올릴 예정이니 한번 오세요(<a target="_blank" href="http://blog.naver.com/shimj060">http://blog.naver.com/shimj060</a> 이것은 흥보인가...아닌가...) <div><br></div> <div>*대부분의 내용은 기초 recurrence relation 혹은 combinatorics 서적에서 찾아보실수 있을 겁니다.</div> <div><br></div> <div>*여기에 올라오는 대부분의 수식은 Tex언어로 쓰여질 예정입니다. (원하신다면 Tex에 관한 기본사용 관련글들을 올릴수도...?)</div> <div><br></div> <div>*필자는 외국에서 공부를 한 관계로 수학적 용어들을 대부분 한국어로 모릅니다. 따라서 대부분의 용어는 네이버등에서 영어 단어를 쳐서 찾은 것이므로 오역이 있을수도 있는관게로 영어/한국어를 둘다 기재토록 하겠습니다.</div> <div><br></div> <div><br></div> <div>첫글이다보니 서문이 좀 길었네요.. 그럼 점화식(Recurrence relation)에 관한 첫번째 글을 시작하겠습니다.(본문에선 말을 내려놓겠습니다.)</div> <div><br></div> <p><b><font color="#ff0000">목차:<br></font></b><b><font color="#ff0000">I. 점화식(Recurrence relation)이란?<br></font></b><b><font color="#ff0000">II. 특성 다항식(Characteristic polynomial)</font></b></p> <div><br></div> <h4><font size="2">I. 점화식(Recurrence relation)이란?</font></h4> <div><font size="2">점화식의 한국어 정의는 위키백과에 아주 잘 정리되어있다:</font></div> <div><p style="margin:.5em 0px;line-height:17.9200000762939px;font-family:sans-serif;"><font size="2" color="#0070c0">수학에서 <b>점화식</b>(또는 <b>재귀식</b>)(Recurrence relation)이란 수열의 항 사이에서 성립하는 관계식을 말한다. 즉, 수열 {<span><img class="mwe-math-fallback-image-inline tex" alt="a_n" src="http://upload.wikimedia.org/math/9/d/e/9ded7825070b255e7bc092cdc2c8e98a.png" style="border:none;vertical-align:middle;margin:0px;display:inline-block;"></span>} 의 각 항 <span><img class="mwe-math-fallback-image-inline tex" alt="a_n" src="http://upload.wikimedia.org/math/9/d/e/9ded7825070b255e7bc092cdc2c8e98a.png" style="border:none;vertical-align:middle;margin:0px;display:inline-block;"></span> 이 함수 <i>f</i> 를 이용해서</font></p><dl style="margin-top:.2em;margin-bottom:.5em;font-family:sans-serif;line-height:17.9200000762939px;"><dd style="line-height:1.5em;margin-left:1.6em;margin-bottom:.1em;margin-right:0px;"><font size="2" color="#0070c0"><img class="mwe-math-fallback-image-inline tex" alt="a_{n+1} = f(a_1 , a_2 , .... , a_n )" src="http://upload.wikimedia.org/math/0/9/7/097305936c27b7a65c71af1c8baf7cf0.png" style="border:none;vertical-align:middle;display:inline-block;"></font></dd></dl><p style="margin:.5em 0px;line-height:17.9200000762939px;font-family:sans-serif;"><font size="2" color="#0070c0">처럼 귀납적으로 정해져 있을 때, 함수 <i>f</i> 를 수열 {<span><img class="mwe-math-fallback-image-inline tex" alt="a_n" src="http://upload.wikimedia.org/math/9/d/e/9ded7825070b255e7bc092cdc2c8e98a.png" style="border:none;vertical-align:middle;margin:0px;display:inline-block;"></span>} 의 점화식이라고 하며, 또한, 수열 {<span><img class="mwe-math-fallback-image-inline tex" alt="a_n" src="http://upload.wikimedia.org/math/9/d/e/9ded7825070b255e7bc092cdc2c8e98a.png" style="border:none;vertical-align:middle;margin:0px;display:inline-block;"></span>} 은 점화식 <i>f</i> 로 정의된다고 한다.</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font size="2">(출처:<a target="_blank" href="http://ko.wikipedia.org/wiki/%EC%A0%90%ED%99%94%EC%8B%9D">http://ko.wikipedia.org/wiki/%EC%A0%90%ED%99%94%EC%8B%9D</a>)</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;color:#252525;"><font size="2">*이 정의에 사족을 좀 붙이자면 대부분의 전문서적에선 점화식을 f 혹은 F로 정의하지 않는다. 그 이유는 f, F는 대표적 점화식인 피보나치 수열을 정의할때 통상적으로 쓰이기 때문이다. 따라서 피보나치 수열을 말하는게 아니라면 대부분 h 혹은 g등을 쓰는 편이다.</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;color:#252525;"><font size="2"><br></font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;color:#252525;"><font size="2">점화식이란 정의가 정확히 언제부터 시작되었는지는 알수 없겠지만 점화식이란 수학적 개념은 상당히 오래된 개념이다. 또한 근래에 많은 점화식들이 정수론(number theory)이나 조합이론(combinatorics)등의 문제들에 대한 답을 제시하면서 1800~1900년대에 점화식들과 이 문제들 사이의 관계가 많이 공부되어왔다. 그러다 최근에 들어서는 많은 수학자들이 흥미를 잃고 그다지 활동이 활발하지 못한 분야이긴 하지만 최근들어 점화식을 이용한 새로운 암호작성이론(Cryptography)이 조금 눈길을 끌고 있다 (필자도 현재 이 분야에 대한 연구를 약간 하고 있는 중이다.)</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;color:#252525;"><font size="2"><br></font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;color:#252525;"><font size="2">보통 "점화식"이라고 하면 어려운 수학적 용어라고 생각할수도 있는데 수학/과학을 공부한 사람이라면 알게 모르게 한번쯤은 점화식의 예를 접해봤을 것이다.</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;color:#252525;"><font size="2"><br></font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;color:#252525;"><font size="2">F_n=F_{n-1}+F_{n-2} </font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;color:#252525;"><font size="2">F_0=0, F_1=1.</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;color:#252525;"><font size="2"><br></font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font size="2" style="color:#252525;">이 점화식이 주는 수열은 </font><span style="font-size:small;line-height:17.9200000762939px;"><font color="#252525">{0, 1, 1, 2, 3, 5, 8, 13...} 이다. 어라? 어디서 많이 봤는데? 이 수열이 바로 그 유명한 </font><font color="#ff0000">피보나치 수열(Fibonacci sequence)</font><font color="#252525">이다. 피보나치 수열은 조합이론에 있는 다양한 문제에 대한 답을 주기때문에 아주 흥미로운 수열로 보여지며, 1차 점화식(First order recurrence relation)을 제외한 점화식중 가장 간단한 점화식이기에 점화식을 연구하는 사람들이 가장 먼저 보는 예시이기도 하다. 하지만 어떻게 보면 피보나치 수열보다 훨씬 더 유명한 점화식이 있다.</font></span></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><span style="font-size:small;line-height:17.9200000762939px;"><font color="#252525"><br></font></span></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><span style="font-size:small;line-height:17.9200000762939px;"><font color="#252525">H_n=m*H_{n-1}</font></span></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><span style="font-size:small;line-height:17.9200000762939px;"><font color="#252525">H_0=0, H_1=1, m=양의 정수.</font></span></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><span style="font-size:small;line-height:17.9200000762939px;"><font color="#252525"><br></font></span></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><span style="font-size:small;line-height:17.9200000762939px;"><font color="#252525">예를들어 m을 2라고 하면, 이 점화식이 주는 수열은 {0, 1, 2, 4, 8, 16...} 이 된다. 당연히 각 수는 a_n=2^n 으로 표현될수 있다. 따라서 각 m에 따라 이 수열은 m의 곱을 표현하게된다. 즉 이 수열은 m진수의 숫자들을 모두 나열하게 되므로 이 점화식은 m진수를 만들어내는 점화식인 셈이다. 하지만 보통 1차 점화식의 경우 너무 간단하다라는 이유로 거의 언급조차 되지 않는다.</font></span></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><br></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2">*정확한 용어로는 1차/2차 점화식이 아니라 1항간/2항간 점화식이라고 명칭되는 것으로 알고있다.</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><span style="font-size:small;line-height:17.9200000762939px;"><font color="#252525"><br></font></span></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><span style="font-size:small;line-height:17.9200000762939px;"><font color="#252525"><br></font></span></p> <h4 style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2">II. 특정 다항식(Characteristic polynomial).</font></h4> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2">수학 혹은 과학을 공부한 사람이라면 특정 다항식이란 단어를 한번쯤은 들어봤을 것이다. 바로 선형대수학에서 행렬(matrix)의 고유치(Eigenvalue)를 근(root)으로 갖는 식을 그 행렬의 특정 다항식, p(x), 라고 지칭한다. 헌데 점화식에도 특정 다항식이 있다. 위에서 예를 든 피보나치 수열으르 보자.</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2"><br></font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2">F_n=F_{n-1}+F_{n-2}</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2"><br></font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2">만약에 내가 백만번째 피보나치 숫자를 알고싶다면 어떻게 할까? 그냥 Python이나 Mathematica 같은 소프트웨어에 4줄짜리 코드를 집어넣으면 된다.. 가 답일수도 있다. 가장 단순무식한 4줄짜리 코드라해도 요즘 컴퓨터들은 30초안에 백만번째 피보나치 숫자를 찾을수 있다. 점화식의 결과물중 하나인 루카스 수(Lucas numbers)를 이용한다면 약 10줄의 코드로 0.1초안에 백만번째 피보나치 숫자를 찾을수도 있다.(물론 이 코드는 오차가 있기 때문에 특정숫자 이상의 피보나치 숫자를 찾을때만 쓰일수있다. 하지만 백만번째 피보나치 숫자는 충분히 크기 때문에 오차를 감안하더라도 맞는 숫자를 준다.)</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2"><br></font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2">자, 여기서 4줄짜리 코드에 집중해보자. 4줄짜리 코드란 단순하게 첫 두개의 피보나치 숫자(0과 1)를 집어넣고 컴퓨터에게 2번부터 100만번째까지의 모든 피보나치 숫자를 구하라고 하는 것이다. 백만개의 숫자를 30초안에 찾아낼수 있다는것은 놀라운 결과라고 볼수 있지만 피보나치 수열이 얼마나 친절한 수열인지를 감안한다면 그다지 감탄할 결과는 아니다. 보다 효과적으로 피보나치 숫자를 찾는 방법은 바로 특정다항식을 이용하는 것이다. 다음 다항식을 살펴보자.</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2"><br></font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2">x^2=x+1 -> p(x)=x^2-x-1.</font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><font color="#252525" size="2"><br></font></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;">근의 공식을 이용한다면 이 다항식의 근이 [1+/-sqrt(5)]/2 라는걸 금방 알수 있다. 자 그럼 이제 다음 식을 살펴보자</p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><br></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;">H(m)=[(1+sqrt(5)/2)^m-(1-sqrt(5)/2)^m]/sqrt(5)</p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><br></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;">이 식에 m=0, 1, 2, 3...을 대입하면 {0, 1, 1, 2, 3, 5...}의 피보나치 수열을 얻게된다. 과연 우연의 일치일까? 아니다. 만약에 점화식이 주어진다면 그 점화식을 위에 방법대로 바꿔서 특성 다항식을 얻을수 있다(이에 대한 증명은 선형대수학과 약간의 귀납법을 사용하면 쉽게 증명할수 있다. 혹은 왠만한 기본 서적에서 찾아볼수 있다). 그러면 그 특성다항식은 n차 다항식이므로 총 n개의 근을 준다. n개의 근을 a_1, a_2, ..., a_n 이라고 칭하면 점화식이 주는 수열은 다음과 같이 표시될수 있다(여기서는 두번 이상 반복되는 근은 반복되는 만큼 표시한다. 하지만 이후로 반복되는 근은 한번만 표기하도록 하겠다).</p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><br></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;">H(m)=(p_1(x)*a_1)^m+(p_2(x)*a_2)^m+...+(p_n(x)*a_n)^m</p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><br></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;">여기서 각 p_m(x)는 다음과 같은 성질을 갖는다.</p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><br></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><span class="Apple-tab-span" style="white-space:pre;"> </span>1. 만약 a_m 이 특성 다항식에서 b번 반복되는 근이라면 p_m(x) 는 b차 다항식이다.</p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><span class="Apple-tab-span" style="white-space:pre;"> </span>2. 다항식 p_m(x)의 계수(coefficient)는 점화식의 초기 조건(initial condition)에 의해 결정된다. </p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><br></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;">물론 이 방법이 쉬운 방법은 아니다. 그 이유는 다항식의 근을 찾는것이 굉장히 어렵기 때문이다. 다항식의 근을 찾는 것은 선형대수학에서 행렬의 고유치를 찾는 것과 똑같은데 선형대수학의 가장큰 문제가 "행렬의 고유치를 어떻게하면 잘 찾을 수 있는가?"이며 이 문제가 지난 400여년간 조금씩 발전해왔지만 아직도 선형대수학에서 가장 어려운 문제라는걸 감안한다면 이 방법도 그다지 효율적이진 않다. 하지만 2차 점화식에 관해서만큼은 쉽게 특성 다항식의 근을 찾을 수 있으므로 적절한 방법이라고 할수 있다.</p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><br></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;"><br></p> <p style="margin:.5em 0px;line-height:17.9200000762939px;">시간이 된다면 다음 내용은 2부에서 계속...</p></div>