멱급수 전개(Power series expansion)로 피보나치 수열 풀기

멱급수 전개(Power series expansion)으로 피보나치 수열 풀기

 

결국 피보나치 수열 풀다가 멱급수까지 왔네요...

1. 계차의 등비수열로 풀기

2. 특성방정식으로 풀기

 

1. 멱급수로 피보나치 수열 풀기?

전 포스팅에서 왜 특성방정식으로 풀 수 있지?하면서 파보다가, 어느 Quora글에서 "멱급수로 풀다보면 자연스럽게 나와~"라는 걸 보고 멱급수로 풀어보았네요. 얼추 비슷한 형태가 나오기는 하지만 엄밀하게 멱급수에서 도출 가능한 생성함수는 특성방정식으로 유도하는 것과는 -부호의 차이가 있습니다. 이를 감안하면 사실상 멱급수에서 도출하는 생성함수가 1.번으로 풀때 사용되는 근과 계수의 관계에서의 변환($ a_{n+2} = x^2 $)에서도 사용되고, 2.번으로 풀때 놓게 되는 $ a_{n} = x^n $과도 연관이 생기니 어떻게보자면 근원을 잘 판 것 같습니다.

 

2. 어떻게 풀건데?

2-1. 일단 멱급수가 뭔데?

멱급수는 영어로 Power series, 혹은 한자로 冪級數라고 쓰입니다.

네이버 지식백과의 설명을 보자면

일반적으로 $ \sum a_ń(x-a)^ń $인 꼴로 나타낼 수 있는 급수를 말한다. 정급수(整級數)라고도 한다. $ a_0, a_1, …, a_ń $이 상수, $ x $가 변수인 다항식 $ a_0+a_1 x+a_2 x^2+…+ a_ń x^ń $을 무한히 연장한 식

      $ a_0+a_1 x+a_2 x^2+…+a_ń x^ń+… $

을 말한다. (후략)
[네이버 지식백과] 멱급수 [power series, 冪級數] (두산백과 두피디아, 두산백과)

라네요. 결국 특정 상수와 변수를 무한히 더한 급수를 말합니다.

그리고 이 멱급수는 등비급수의 성질을 띄기 때문에 공비라고 볼 수 있는 x의 값에 따라 수렴/발산이 정해지게 되는데, 이번에 저희는 이 멱급수의 특성을 가지고 상수항을 만들어내는 생성함수를 찾아낼 것이기 때문에 사실상 변수의 상태가 크게 중요하지 않게됩니다. 그래서 저희는 여기서 Formal power series(굳이 한국어로 번역하자면 형식적 멱급수?)를 사용할 것입니다. Formal의 뜻은 말그대로 '형식적'이라는 말로 공비 x의 범위를 따지지 않을 것이야요~ 하는 말입니다.

2-2. 시작은 어떻게 할건데?

자, 일단 처음 식을 놓는 것 부터가 아주 중요할 것 같네요. 천릿길도 한걸음부터!

일단 생성함수를 정의해보죠. 아까 보았던 멱급수를 그대로 대입해 줄 겁니다.

생성함수라고 해서 별거 없습니다. 그냥 '어떤 수를 생성하는 규칙을 가진 함수'라고 보면 됩니다.

Generating function(생성함수)의 이름을 따서 $ g(x) $라고 정의해봅시다!

그리고 피보나치 수열을 멱급수의 상수로 놓아봅시다.(피보나치 수열=$ F_n $, $ F_n = F_{n-1} + F_{n-2} $)

$ g(x) = \sum\limits_0^\infty F_n x^n $

$ g(x) = F_0 x^0 + F_1 x^1 + F_2 x^2 + F_3 x^3 + ... $

이런 식이 나올겁니다. 시작이 반입니다. 이미 반 했습니다!

여기서 $ x^0 = 1,\ x^1 = x $이고, 피보나치 수열의 특성상 $ F_0 = 1,\ F_1 = 1 $이므로 식을 다시 정리해보면,

$ g(x) = 1 + x + \sum\limits_2^\infty F_n x^n $
$ g(x) = 1 + x + \sum\limits_2^\infty (F_{n-1} + F_{n-2}) x^n\ \ \because F_n = F_{n-1}+F_{n-2} $
$ g(x) = 1 + x + \sum\limits_2^\infty F_{n-1} x^n + \sum\limits_2^\infty F_{n-2} x^n $
$ g(x) = 1 + x + x\sum\limits_2^\infty F_{n-1} x^{n-1} + x^2\sum\limits_2^\infty F_{n-2} x^{n-2} $
$ g(x) = 1 + x + x\sum\limits_1^\infty F_{n} x^{n} + x^2\sum\limits_0^\infty F_{n} x^{n} $

로 정리됩니다. 여기서 $ \sum\limits_0^\infty F_{n} x^{n} $은 정의에 따라 $ g(x) $와 같고,

피보나치 수열의 정의를 따라 $ F_0 x^0 = 1 $ 이므로

$ \sum\limits_0^\infty F_n x^n = \sum\limits_1^\infty F_n x^n +1  $
$ \sum\limits_0^\infty F_n x^n -1 = \sum\limits_1^\infty F_n x^n $
$ g(x)-1 = \sum\limits_1^\infty F_n x^n $

입니다. 따라서 식을 $ g(x) $로 정리하면,

$ g(x) = 1 + x + x\sum\limits_1^\infty F_{n} x^{n} + x^2\sum\limits_0^\infty F_{n} x^{n} $
$ g(x) = 1 + x + x(g(x)-1) + x^2g(x) $
$ g(x) = 1 + x + xg(x)-x + x^2g(x) $
$ g(x) = 1 + xg(x)+ x^2g(x) $
$ g(x) - xg(x) - x^2g(x) = 1 $
$ (1 - x - x^2)g(x) = 1 $
$ g(x) = \frac{1}{1-x-x^2} $

이로써 생성함수식이 나왔습니다. 미지의 x값이 들어가면 어떤 숫자를 내보내 주는 함수입니다. 근데 여기서 어떤 x값이 들어가야 어떤수가 생성이 되는지 알 수 없기 때문에 바로 x의 값을 알아내러 출동하죠!

2-3. x 값 찾으러 출발!

2차 식이니까 x의 값도 2개가 나올 것입니다.

다만, 여기서 재밌는 점은 생성함수의 꼴이 2차 다항함수의 꼴이라는 점 입니다.

결국 분수의 꼴로 나타내어졌지만, 2차 다항함수의 선형결합으로 이루어진 것이 피보나치 수열의 생성함수이고 이를 토대로 특성방정식을 사용할 수 있는게 아닌가 생각이 듭니다.

여튼 각설하고, 다시 x의 해를 구하러 가봅시다!

2차 다항식의 분수꼴은 뭔가 해를 구하기 껄쩍지근하니, 부분분수로 쪼개봅시다.

부분분수로 쪼개려면 분모가 곱셈으로 연결되어있어야하는데, 까짓것 이차 다항식이니까 임의의 해를 놓고 인수분해해버리죠 뭐

$ g(x) = \frac{1}{1-x-x^2} $

$ g(x) = -\left(\frac{1}{x^2+x-1}\right) $

여기서 임의의 해를 $ r_1, r_2 $라 하겠습니다.

그리고 이 식에 근과 계수와의 공식(Vieta's formulas)을 적용하면 $ r_1 r_2 = \frac{c}{a} = \frac{-1}{1} = -1 $이 되고, 여기서 $ r_1 $과 $ r_2 $의 관계식이 도출됩니다. $ r_1=-\frac{1}{r_2} $

자, 그러면 분모를 인수분해하시오

$ g(x) = -\left(\frac{1}{(x-r_1)(x-r_2)}\right) $

부분분수로 짜갤때는 일정한 계수가 짜개진 분수 앞에 하나씩 붙습니다. 이 계수를 $ A, B $라고 하죠.

흔히 아는 부분분수 공식 $ \frac{1}{AB} = \frac{1}{B-A}\left(\frac{1}{A}-\frac{1}{B}\right) $과 완전히 같은 공식이에요. 앞에 붙는 $ \frac{1}{B-A} $를 계수처럼 놓았을 뿐입니다.

$ g(x) = -\left(\frac{A}{x-r_1}+\frac{B}{x-r_2}\right) $
$ -\left(\frac{1}{(x-r_1)(x-r_2)}\right) = -\left(\frac{A}{x-r_1}+\frac{B}{x-r_2}\right) $
$ \frac{1}{(x-r_1)(x-r_2)} = \frac{A}{x-r_1}+\frac{B}{x-r_2} $
$ 1 = A(x-r_2)+B(x-r_1) $

이 때, $ x = r_1 $이면,

$ 1 = A(r_1-r_2)+B(r_1-r_1)  \Leftrightarrow A = \frac{1}{r_1-r_2} $

또한, $ x = r_2 $이면,

$ 1 = A(r_2-r_2)+B(r_2-r_1)  \Leftrightarrow B = \frac{1}{r_2-r_1} $

즉 $ A = -B $임을 알 수 있습니다.

그리고 실제 x를 풀어보자면 이 두 근을 각각 $r_1,\ r_2$로 놓았기 때문에

$ x^2 + x - 1 \Rightarrow a=1,\ b=1,\ c=-1 $

근의 공식에서

$ x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} $
$ x = \frac{-1 \pm \sqrt{1+4}}{2} \Leftarrow a=1,\ b=1,\ c=-1 $
$ x = \frac{-1 + \sqrt{5}}{2}\ or\ \frac{-1 - \sqrt{5}}{2} $
$ r_1 = -\frac{1 - \sqrt{5}}{2},\ r_2= - \frac{1 + \sqrt{5}}{2} $

이며, $ A $ 값도 직접 찾아보자면,

$ A = \frac{1}{r_1-r_2} = \frac{1}{-\frac{1 - \sqrt{5}}{2} - (-\frac{1 + \sqrt{5}}{2})} = \frac{1}{\sqrt5} $

입니다.

본격적으로 수식을 정리하기 전, 미지수와 그 관계들을 모두 찾아보았는데요, 다시한번 정리해보겠습니다.

$ x = r_1\ or\ r_2 $

$ r_1 r_2 = -1 \Leftrightarrow r_1 = -\frac{1}{r_2} \Leftrightarrow r_2 = -\frac{1}{r_2} $

$ A = \frac{1}{r_1-r_2} $

$ A = -B $

$ r_1 = -\frac{1 - \sqrt{5}}{2},\ r_2= - \frac{1 + \sqrt{5}}{2} $

$ A = \frac{1}{\sqrt5} $

자, 본격적으로 식을 풀어봅시다!

2-4. 본격적으로 멱급수 해체!

다시 정리했던 식으로 돌아가 봅시다.

$ g(x) = -\left(\frac{A}{x-r_1}+\frac{B}{x-r_2}\right) $
$ g(x) = -\frac{A}{x-r_1}-\frac{B}{x-r_2} $
$ g(x) = \frac{A}{r_1-x}+\frac{B}{r_2-x} $
$ g(x) = \frac{1}{r_1}\frac{A}{1-\frac{x}{r_1}}+\frac{1}{r_2}\frac{B}{1-\frac{x}{r_2}} $
$ g(x) = \frac{A}{r_1}\frac{1}{1-\frac{x}{r_1}}+\frac{B}{r_2}\frac{1}{1-\frac{x}{r_2}} $
$ g(x) = \frac{A}{r_1}\frac{1}{1+r_2 x}+\frac{B}{r_2}\frac{1}{1+r_1 x} \Leftarrow r_1 = -\frac{1}{r_2},\ r_2 = -\frac{1}{r_2}$

여기서 무한 등비 급수 공식인 $ \sum\limits_0^\infty ar^n = \frac{a}{1-r} $을 적용하면,
$ g(x) = \frac{A}{r_1}\sum\limits_0^\infty(-r_2 x)^n+\frac{B}{r_2}\sum\limits_0^\infty(-r_1 x)^n$
$ g(x) = \frac{A}{r_1}\sum\limits_0^\infty(-r_2 )^n x^n+\frac{B}{r_2}\sum\limits_0^\infty(-r_1 )^n x^n$
$ g(x) = \sum\limits_0^\infty \left(\frac{A}{r_1}(-r_2 )^n+\frac{B}{r_2}(-r_1 )^n\right)x^n$
$ g(x) = \sum\limits_0^\infty \left(A(-r_2)^{n+1}+B(-r_1)^{n+1}\right)x^n \Leftarrow r_1 = -\frac{1}{r_2},\ r_2 = -\frac{1}{r_2} $
$ \sum\limits_0^\infty F_n x^n = \sum\limits_0^\infty \left(A(-r_2)^{n+1}+B(-r_1)^{n+1}\right)x^n $

여기서 양변 무한등비급수를 제거해주면

$ F_n = A(-r_2)^{n+1}+B(-r_1)^{n+1} $

피보나치 수열의 항만 나오게 되었습니다. 그리고 결국 이 식이 피보나치 상수를 만들어내는 생성함수인 격인데요, 결국 특정 상수를 만들어내는 생성함수 = 일반항이겠죠?

본격적으로 수를 대입하기전에 이 식을 좀 더 간단히 만들어보겠습니다.

$ F_n = A(-r_2)^{n+1}-A(-r_1)^{n+1} \because B = -A $
$ F_n = A\left((-r_2)^{n+1}-(-r_1)^{n+1}\right) $

 

3. 답은?

이제 대망의 실제 값 대입만 남았습니다.

원 식은,

$ F_n = A\left((-r_2)^{n+1}-(-r_1)^{n+1}\right) $

실제 값은,

$ r_1 = -\frac{1 - \sqrt{5}}{2},\ r_2= - \frac{1 + \sqrt{5}}{2} $

$ A = \frac{1}{\sqrt5} $

이었죠? 대입해줍시다.

$ F_n = \frac{1}{\sqrt5} \left(( \frac{1 + \sqrt{5}}{2} )^{n+1}-( \frac{1 - \sqrt{5}}{2} )^{n+1}\right) $

짜잔, 피보나치 수열의 일반항이 풀렸습니다.

참고로 여기서는 수열의 첫 항이 1이 아니라 0이므로 일반항에서 지수항이 n이 아니라 n+1인 점을 주목해주세요

진짜 맞는지 직접 값을 대입해봅시다.

$ F_{-1} = \frac{1}{\sqrt5} \left(( \frac{1 + \sqrt{5}}{2} )^{0}-( \frac{1 - \sqrt{5}}{2} )^{0}\right) = 0 $ (실제 피보나치 수열에는 없는 부분이지만 1, 1, 2, 3, 5... 식으로 앞의 두 수를 더해서 다음 수가 나오는 것으로 생각해보면 초항 앞은 0임을 생각해 볼 수 있습니다.)

$ F_0 = \frac{1}{\sqrt5} \left(( \frac{1 + \sqrt{5}}{2} )^{1}-( \frac{1 - \sqrt{5}}{2} )^{1}\right) = 1 $

$ F_1 = \frac{1}{\sqrt5} \left(( \frac{1 + \sqrt{5}}{2} )^{2}-( \frac{1 - \sqrt{5}}{2} )^{2}\right) = \frac{1}{\sqrt5} \left(\frac{1+2\sqrt5+5-(1-2\sqrt5+5)}{4}\right) = \frac{1}{\sqrt5} \left( \frac{1+2\sqrt5+5-1+2\sqrt5-5}{4} \right) = \frac{1}{\sqrt5} \left( \frac{4\sqrt5}{4} \right) =  1 $

네 첫 두항은 1, 1 이고, $ F_2 $부터는 3차식이기때문에 계산이 까다롭지만, wolfram alpha를 돌려보면 제대로 2, 3, 5... 나오는 것을 확인할 수 있습니다.

제대로 구했네요!

실제로 이전 포스팅인 점화식에서의 특성방정식에서 도출한 결과와 같습니다!(참고로 특성방정식에서 도출한 초항은 n이 1입니다.)