생성함수(Generating Function)란?(feat. 멱급수(power series))

생성함수(Generating Function)란?(feat. 멱급수(power series))

 

0. 서론

생성함수(Generating function)에 대해 그 의미가 생소한 분들이 많은 것 같아 추가로 이 포스팅을 기획하였습니다.

이전까지 글들이 좀 더 수학적으로 엄밀하고, 수식을 통해서 논지가 진행되었던 것에서 이번 포스팅은 조금 탈피해보려고 합니다.

아무래도 개념적인 부분을 다루고, 심지어 생소한 개념이다보니 최대한 쉽게 써보려고 하는데요.

여기서 예시로 들거나 대화를 하는 듯한 부분은 하나의 과장이자 허구이니 진지하게 받아들이시지는 마시고, '아~ 그냥 이래서 이렇게 되었던 거구나~'정도로만 이해해주시면 감사하겠습니다.(진짜 저런 대담이 오갔다거나 저게 진짜 기원이라고 믿으시면 안됩니다... 흐름만 봐주세요..)

그럼 시작해보겠습니다.

 

 

1. '등비수열의 합' 공식을 아시나요?

혹시 '등비수열의 합' 혹은 '등비급수' 공식을 알고 계신가요?

고등학교에서 처음 나오는 부분이라, 고등학교 교육을 지나쳐 오신 분들은 조금 친숙하시거나 적어도 '아.. 그런것도 있긴했었다...' 하실테고 아직 고등학교 교육을 이수하지 못하신 분들이라면 '엥?'이라고 하실수도 있으실 겁니다.

결론적으로 공식만 써보면 다음과 같습니다.

$ \sum \limits _{n=0}^{\infty} ar^n = \frac{a}{1-r} $

여기서 a는 초항(제일 처음 항), r은 공비 죠.

그리고 여기서 r은 $ | r | < 1 $입니다. 이래야만 수렴하거든요.(간단히 쓰기로 했으니까 자세한 내용은 생략하겠습니다만, 부분합 공식에서 극한을 취해보면 $ | r | < 1 $인 경우에만 수렴한답니다.)

 

1-1. 등비급수 공식을 직접 유도해보자~

이 공식은 고등학교에서 두가지 방식으로 유도합니다.

1) 등비 수열의 부분합 공식에서 n에 극한을 취해서 구한다.

2) r을 하나 곱해서 빼서 구한다.

여기서 두번째 구하는 방법을 한번 볼까요?

먼저 어떤 등비수열의 무한급수가 있다고 해 봅시다. 그리고 이 친구를 그냥 $ S $라고 놓을께요.

편의상 초항 a는 1로 놓겠습니다.

$ \sum \limits _{n=0}^{\infty} r^n = \sum \limits _{n=0}^{\infty} r^n = 1 + r + r^2 + \cdots = S $

그리고 여기서 $ S $에 $ r $을 하나 곱해봅시다.

$ r+r^2+r^3+\cdots = rS $

오 근데 위 식과 아래 식을 잘 보면 항이 서로 뺄 수 있을 것 같이 생기지 않았나요? 바로 빼봅시다

$ 1 + r + r^2 + \cdots - (r+r^2+r^3+\cdots) = 1 = S - rS $

$ 1= S-rS \Leftrightarrow 1 = (1-r)S $

다시정리하면,

$ \frac{1}{1-r} = S \Leftrightarrow \frac{1}{1-r} = 1 + r + r^2 + \cdots $

여기서 초항 a를 편의상 1로 놓고 계산했지만, 다시 살려줘서 양변에 곱해주면

$ \frac{a}{1-r} = a(1 + r + r^2 + \cdots) = a \sum \limits _{n=0}^{\infty} r^n = \sum \limits _{n=0}^{\infty} ar^n $

바로 우리가 처음 보았던 바로 등비수열의 합 공식이 짜란 하고 펼쳐집니다.

 

1-2. 근데 이걸 다시 곱해보면?

근데, 이 수식에서 분모를 다시 양변 곱해볼 생각 해보신분 계신가요?

$ \frac{1}{1-r} = 1 + r + r^2 + \cdots $

바로 이부분에서요.

'무한한데 어떻게 분배하냐~~~'라고 하실수도 있지만, 잘 보면 분배는 (1-r)에서 1곱한 급수 - r곱한 급수가 된답니다.

$ (1+r+r^2+\cdots)(1-r) = (1+r+r^2+\cdots) - r(1+r+r^2+\cdots) = (1+r+r^2+\cdots) - (r+r^2+r^3+\cdots) $

이렇게 분배가 되구요.. 수식을 잘 보고 뺄셈을 해보시면... 1만 남는걸 알 수 있습니다.

(여기서 '빼는 항 개수가 안맞잖아요~'라고 하신 당신은 엄청난 재능러! 그러나 무한의 공간에서는 말 그대로 '무한'하기 때문에 항 수에 대한 1:1 매칭이 의미가 없답니다! 관심있는 분들은 '힐베르트 호텔'을 한번 찾아보세요!)

그럼 수식을 다시 써보면

$ \frac{1}{1-r} = 1+r+r^2+\cdots \Leftrightarrow 1 = (1+r+r^2+\cdots)(1-r) = 1 $

엥? $ 1 = 1 $이라는 너무나도 기묘한? 이상한? 결과가 나왔네요?

뭐 별거 없습니다. 그냥 '당연하다~'이소립니다.

"좌변이 1이고, 우변도 계산하면 1이니까 둘은 같잖아! 그러니까 너의 식변형은 맞아~"

라고 알려주는거나 마찬가지지요.

결국 저 무한한 등비 수열이 더하기로 연결되어있는 걸 '단 하나의 수식'으로 표현할 수 있다는 거죠!

그럼 이 당연한걸 왜 해봤냐면요...

 

 

2. r을 확장해보자~

이제 수학자들이 이런 생각을 하기 시작합니다.

 

"오호 신기한지고... 어떻게 무한한 더하기를 이 단 하나의 공식으로 표현할 수 있는겐가..."

"오호오호 너무나 신기한지고... 아니 그러면 '값'을 넣으면 '값'이 나오는 r이라는 '공비' 대신에 의문스러운 '무언가'를 나타내는 문자 x를 써보면 어떠할까?"

 

그렇게 문자 x로 확장을 해봤는데? 어머어머 이게 x라도 딱 맞는거에요~~ 1=1이 나와버렸다니까요~~ (궁금하시면 직접 x로 바꿔서 풀어보셔도 됩니다만.. 어차피 r이나 x나... 글자만 바뀐거니까 결과도 동일하겠죠...?)

 

 

3. x에다가 무슨 장난을 칠 수 있을까... 계수?

거기다 이게 "아니 공비(r)라고 하는 틀에 갖혀서는 무조건 공비의 조건을 만족해야만 수식이 수렴하면서 값이 나왔기에 그냥 그런갑다~~ 했는데, 이걸 x라고 놔버리고보니 우항이 x의 거듭제곱꼴이되면서 x의 계수가 다시 또 어떤 등비수열을 나타낼 수 있잖아!? 오마나 세상에나 만상에나!!"

"봐봐, 봐봐, x라고 하는 자리에 2x를 넣으면, x의 계수가 바로 공비가 2인 수열이 만들어진다니까!?"

아주 난리가 납니다. 완전히 새로운 접근이 되어버린거죠.

이제 무한한 수열을 단 하나의 수식으로 '압축'해서 표현할 수 있는 방법이 생긴겁니다. 혁신이었죠.

그리고 여기서 다시 잘 살펴보면 x는 '어떤 미지의 수'를 뜻하는게 아니라 진짜 말그대로 '그냥 무언가'를 뜻하는 걸로 출발해서 이와같은 결실을 맺었기에, 그리고 그 '그냥 무언가'를 몇 제곱 했는지가 바로 그 계수를 몇제곱했는지랑 같은 의미가 되며, 그냥 'n번째'를 나타내는 '$ x^n $'으로의 의미가 생기게 됩니다.

 

 

4. 계수가 할말이 있대~~ 집중~~

근데 여기서 수학자들이 또 아주 재밌는 사실을 발견합니다.

 

"근데, 꼭 등비수열만 이렇게 나타낼 수 있는걸까?"

 

그러면서 계수를 이제부터 (등비수열의 정의 $ a_n = ar^n $에서)

$ ar^n $으로 보지 않고 $ a_n $으로 봐버리는 겁니다. 발상의 전환! 집중과 선택!

그러면 바로 이 급수 비스므리한 수식은! 안타깝게도 등식이 깨져버립니다.

좌변의 수식이 바로 '등비급수'를 나타내는 수식이었기 때문이죠...

그러나 하늘이 무너져도 솟아날 구멍은 있다! 어떤 수학자가 발상의 전환을 해버립니다

 

"어? 그럼 그냥 좌변을 '나도 모르는 수식 무언가😵‍💫'라고 놓아버리면 우변도 바꿔도 되지 않을까?

아니 그러면... 반대로 생각해보면...

우변의 계수가 등비수열이었으니까 -> 좌변의 수식이 등비수열을 나타내는 수식

그렇다면

우변의 계수가 'ㅁㄴㅇㄹ'수열이면 -> 좌변의 수식이 'ㅁㄴㅇㄹ'수열을 나타내는 수식(일명 '나도 모르는 수식 무언가😵‍💫')

이 되어버리는 거네!?

그러면 이번엔 좌변이 '수식 무언가'니까 대애충 '수식이에요'하는 모냥으로 함수처럼 A(x) 이런식으로 써놓고, 우변의 계수에 내가 알고싶은 수식의 일반항 넣고 계산해서 계산이 되어버리면, 그 계산된게 '수식무언가'겠네!?!?!?!?

오 마이 갓!!"

 

이렇게 깨달음을 얻은 그들... 다시한번 심호흡하며 그동안 깨달은걸 다시한번 검토해봅니다.

 

1) 등비급수를 구하는 공식을 찾았다!

2) 거기에다가 공비대신에 문자 써도 성립하던데?

3) 어? 근데 문자 옆에 계수 쓰면 그 계수를 공비로 가지는 등비수열이 나와

4) 지금 이건 등비급수 공식을 가지고 계수가 등비수열을 나타내는걸 만들어낸거나 마찬가지네?

5) 여기서 등비수열을 또 일반항 $ a_n $으로도 표현할 수 있잖아?

6) 그렇다면 일반항 $ a_n $에 대해서 표시가 된다면, 아무 수열이나 다 쓸수있는거아냐?

7) 어? 그럼 '나도모르는 공식' 무언가는 계수가 'ㅁㄴㅇㄹ'수열을 나타낼 수도 있지 않을까?

8) 6번 7번을 섞어서 생각해보면, 'ㅁㄴㅇㄹ'수열을 넣고 계산해서 어떤 특정한 공식이 나온다면 그게 바로 그 수열의 '공식'이네!?

9) 반대로 이 공식을 $ a_n $으로 표시할 수 있으면, 이게 바로 그 수열의 일반항이 되는건가아아아아아아!!!!

 

한번 더 검토하고는 '유레카!'를 외치며, 그들은 자신들이 맞았음을 확신하고는 이내 계수에 온갖 수열을 다 넣어봅니다.

 

가장 간단한 등차수열도 넣어봅니다.

 

등차수열의 일반항은 다음과 같습니다.

$ a_n = a + (n-1)d \quad (n \ge 1) $

보통은 수열의 첫 항을 1항이라고 표시해서 이런 식이 나오는데, 그냥 첫 항을 0이라고 놔버리면 수식은 좀 더 간단해집니다.

$ a_n = a + nd \quad (n \ge 0) $

 

아까 우항을 아래와 같이 표기할 수 있다고 그랬습니다.

$ \sum\limits_{n=0}^{\infty} a_n x^n $

여기다 등차수열의 일반항을 대입해보면

$ \sum\limits_{n=0}^{\infty} \left(a + nd\right) x^n $

이렇게 될 겁니다.

근데 여기서 이 친구는 우항이었죠?

 

좌항은 '분명히 무슨 공식이 있을텐데...?'수준입니다. 그래서 그냥 '수식 비스므리한 무언가'라고 $ A(x) $라고 써주겠습니다.

그렇다면 완성된 수식은

$ A(x) = \sum\limits_{n=0}^{\infty} \left(a + nd\right) x^n $

사실상 급수수식

$ \frac{1}{1-rx} = \sum\limits_{n=0}^{\infty} r^n x^n $

과 다를바가 없습니다.(수식의 비슷한 정도를 위해 문자 x로 바꾼 버전으로 썼습니다)

다른점이라면 등비수열 수식은 이미 우리가 등비급수 수식을 통해 유도해 내려오면서 좌변을 알 뿐이고, 등차수열은 좌변을 모르니까 A(x)라고 놨을 뿐이죠.

 

개념 포스팅이니 자세한 유도는 생략하겠습니다만, 결국 풀어보면

$ A(x) = \frac{a}{1 - x} + \frac{d\,x}{(1 - x)^2} $

이렇게 됩니다. 결론은 '우리가 뭔지 몰라서 A(x)로 놨던 수식은 사실은 $ \frac{a}{1 - x} + \frac{d\,x}{(1 - x)^2} $ 였어~'

라는 뜻입니다.

 

그리고 이걸

$ \frac{1}{1-rx} = \sum\limits_{n=0}^{\infty} r^n x^n $

요런식으로 표현해보면

$ \frac{a}{1 - x} + \frac{d\,x}{(1 - x)^2} = \sum\limits_{n=0}^{\infty} \left(a + nd\right) x^n $

 

즉, 등차수열을 계수로 가지는 급수는 좌항과 같은 '단 하나의 수식'으로 표현 가능하대요~ 라는 의미가 되죠.

어머 이게 풀려버렸습니다. 등차수열이 또 단 하나의 수식으로 표현되어버립니다.

 

"와 미쳤다. 우효~ 이거 우리가 어마어마한걸 발견해버린거 아니냐고~~😱🔍"

 

수학자들은 신이났습니다.

그리곤 진짜 별의 별 수열들을 다 넣어보는데.... 어머나.. 모두다 단 하나의 수식으로 압축이 되어버리는거있죠~~~

이렇게 수열을 하나의 수식으로 다 표현할 수 있게 되자, 수학자들은 이 놀라운 방식을 아예 이름을 붙이기로 합니다.

거기다 왠지 '거창한 이름'을 지어주고 싶어졌죠.

 

 

5. 너의 이름은 생성함수니라~

그래서 이름도 아주 거창하게 '생성함수(generating function)'라고 지어버립니다.

처음 듣는 사람 아주 기죽게말이죠..

그러나 실상은 별거없어요.

• '생성' : 아 이걸로 무한한 수열을 만들어 낼 수(생성할 수) 있어~
• '함수' : 아 수식 비스므리한거니까 함수야~ 그리고 우항이 x의 거듭제곱으로 표현되어버려서 미적분이나 덧셈, 뺄셈, 곱셈, 나눗셈 등등 함수처럼 다룰 수 있어~ 그러니까 좌항 너는 이제부터 함수여~

라서 그냥 생성함수입니다.

그리고 좌항에 하나의 수식으로 표현되는 부분은 생성함수라고 이름 붙여줬으니, 우항에 x의 거듭제곱이 덧셈으로 연결되어있는 이 부분을 "그래 너네는 거듭제곱이 계속 더해지니까 '거듭제곱 급수' 혹은 거듭제곱이 계속 나오니까 power(거듭제곱) series(나열)라고 불러주마"라고 해버렸습니다. 한자로 거듭제곱이 '멱'이라서 멱급수라고도 하죠.

 

 

6. 모일 모처에서는...

동시에 다른곳에서는 다른 수학자들이 다른 고민을 하고 있었습니다.

 

"'초월함수(transcendental function)'가 너무 어려워!!! 크악!!!"

 

여기서 초월함수란, '유한한' 다항식의 합으로 표현가능한 대수적 함수를 '초월(transcendental)'했다는 뜻에서 붙인 함수에요. 말 그대로 $ e^x $, sin x, ln x 등을 말하는 거죠.

 

수학자들은 이 초월함수를 어떻게든 대수적 함수(유한 개의 다항식의 합으로 나타낼 수 있는 함수)로 나타내보려했으나 모두 실패했답니다... 그리고는 '초월함수'란 이름을 붙이고 백기를 들...려고 했으나! 일부 수학자가 이를 벅벅 갈면서

"너가 초월함수면 다야? 너가 어디 다항함수로 '근사'까지 할 수 없나 보자!"

라며 이 초월함수를 다항식으로 비슷하게 만들어보려고 애씁니다.

그리고 결국 '무한한' 다항식의 합. 바로 급수로 이 초월함수를 근사해 내는데 마침내 성공합니다.(테일러 급수(Taylor series), 매클로린 급수(Maclaurin series) 등)

정말 집념이 대단합니다.

 

그런데, 이 급수... 잘 보면 '무한한 다항식의 합' 즉, x의 거듭제곱의 합으로 표현이 됩니다. 그래서 이 수학자들은 여기에 '멱급수(power series)'라고 이름을 붙였죠. 영어 그대로 보자면 power 힘!이 아니라 거듭제곱!의 series 연속 이란 뜻이죠.

그런데 이거.... 어디서 본거 같지 않나요?

 

 

7. 대충돌

네, '수열의 압축법' 즉, 생성함수를 찾아낸 쪽도 x의 거듭제곱의 합으로 수열을 나타내고, 초월함수를 근사하는 방법을 찾아낸 쪽도 x의 거듭제곱의 합으로 함수를 근사합니다.

이제 이 둘이 옥신각신 싸웁니다.

 

누가 먼저냐...는건 관심도 없고, 이거 용어를 뭐라할지 싸웁니다.

서로 같은 용어를 쓰면 이게 생성함수에서 사용하는건지, 함수근사에서 사용하는건지 헛갈리잖아요?

그래서 결국 우여곡절 끝에 양측이 합의를 합니다.

 

초월함수측: 잘 보니까 우리 x의 사용법에 차이가 있는 것 같다. 우리는 x에 실제 값을 대입해서 함수처럼 쓴다. 그러니까 초월함수를 근사할 수 있지.

생성함수측: 그래 맞아. 우리는 x를 그냥 '문자'이자 그 거듭제곱이 '몇 번째인지'를 알려주는 색인으로만 쓰지 직접 값을 대입하지 않는다. 그러면 너네들이 진짜 값을 대입하니까 '멱급수(power series)'는 니네가 가져라.

초월함수측: 먼저 그렇게 선뜻 내주다니 고마운걸? 그럼 우리는 더 멋있는 이름을 지어주마. 아주 엘레강스하고 포멀하게~ 너네는 x를 실제 값으로 안쓰고 '형식적'으로 쓰니까 형식적 멱급수(formal power series)라고 붙여주마

생성함수측: 오우 왕년에 이름 쫌 지어보셨나봐?

양측: 호호호 오호호

 

뭐 실제로 이랬는지는 알 수 없지만... 어찌됐든 이러한 이유로 생성함수에서 사용하는 멱급수는 형식적 멱급수, 즉 x 자체에 특정 값을 대입하는 해석적 방식이 아닌 그냥 자리만 표기해주는 형식적 방식이 된 것입니다.

 

 

8. 결론

그래서 생성함수란 무엇이냐 하면,

1) 무한한 수열을 단 하나의 수식으로 압축시킨 것
2) 그러나 여기서 x는 형식적(색인같은)일 뿐 어떤 값을 가지진 않는다.

요 두가지로 표현할 수 있겠습니다. 

 

 

9. 더 나아가기

여기서 위에서 살짝 언급이 되었던 부분이 있습니다.

 

"일반항을 넣고 계산해서 생성함수를 알 수 있었으면, 반대로 생성함수를 알면 일반항을 알 수 있겠네?"

 

라는 구절이 있었죠.(뭐 물론 토시하나 안틀리고 저렇게 나오진 않았습니다만..)

네, 바로 이부분이 "계수추출"이라고 불리는 부분인데...

보통 수열은 처음부터 일반항이 정의가 되는데, 처음부터 일반항이 정의되지 않은 수열 이를테면 점화식으로만 정의되는 수열 같은 경우에많이 쓰는 개념입니다.

 

위에서 따라 내려왔던 일반항->생성함수 보다는, 생성함수->일반항(계수추출)을 주로 쓰게 되는데요.

1) 점화식으로 정의된 수열을 멱급수로 나타내고(우항의 형식으로 표현하고) 이를 계산해서 생성함수를 알아냅니다.

2) 그리고 그 생성함수를 가지고 반대로 일반항을 찾아냅니다.

즉, [점화식->멱급수의 계수로 대입(우항 스타일)->생성함수 찾아내기(우항으로 좌항 스타일 찾기)->일반항 찾아내기(계수추출:생성함수에서 일반항 찾기)]의 구조를 가진답니다.

결국 생성함수로 '압축!'했다가 '변형풀기!'한거죠.

 

 

10. 마무리

결국 생성함수는 수학자들이 수열을 다루는 방식에 큰 전환을 가져온 도구입니다.

무한한 수열을 단 하나의 수식으로 압축할 수 있다는 것만으로도 놀랍지만, 그 수식을 조작함으로써 일반항을 찾아내고 점화식을 해석할 수 있다는 점은 더욱 강력하죠.

이제 우리는 단순히 수열을 나열하는 것이 아니라, 수열을 '다룰 수 있는' 시대에 들어선 것입니다.

 

어떻게 최대한 수식사용을 지양하고 개념설명에 충실하려 노력했습니다만... 조금 이해가 되셨을지 모르겠습니다.

 

뭐라고 끝내야하지... 우리존재 화이팅요!💪📚