무한서고

카탈란 수열의 일반항을 생성함수로 구해보자(2)

1. 서론

네, 불가피하게? 카탈란 수열의 일반항을 생성함수로 구해보자 두번째 시간입니다...!

저번 포스팅까지 카탈란 수열의 생성함수를 구해보았는데요, 이번 포스팅에서는 이렇게 구한 생성함수로 일반항을 끌어내 보도록 하겠습니다.

이번 포스팅은 제발 길어지지 않기를...

2. 생성함수에서 어떻게 일반항을 끌어내는데?

자 여기서 제일 중요한 부분입니다.

생성함수를 왜 사용하는지는 저번 포스팅에서 깔끔하게 정리했습니다.

자, 그러면 이 생성함수를 써서 압축한 정보를 어떻게 다시 변형하여 unzip할거냐!

바로 '멱급수를 써서 압축했으니, 멱급수 형태로 다시 표현되면 unzip이겠네?'입니다.

큰 맥락은 다음과 같습니다.

1) 무한한 수열을 무한한 멱급수의 계수에 대응시킵니다.

2) 그리고 이걸 '너는 이제부터 생성함수여'하면서 생성함수를 한줄의 수식으로 이쁘게 정리합니다.

3) 이렇게 정리된 수식은 이제부터 씹고 뜯고 맛보고 즐길 수 있는 형태가 된 것입니다. 그러니 열심히 조작을 가합니다.

4) 이렇게 조작이 가해져 이젠 형체조차 알아볼 수 없게 된 친구를 다시 멱급수의 형태로 바꿉니다.

5) 오잉? 멱급수의 $ \sum $와 $ x^n $사이에 전혀 새로운 형태가 생성됩니다

6) 오호 이 수열을 나타내는 다른 방식(= 일반항)이 바로 너구나!

이렇게 진행되는 겁니다.

그리고 저번 포스팅까지 우리는 3번까지 한겁니다.

조작을 가하던 중간에 일단 한숨 돌린셈이죠. 일단 명시적인 생성함수를 찾았으니까요.

이번의 포스팅은 4번부터 시작입니다.

이렇게 조작된 생성함수를 다시 멱급수의 형태로 바꿀겁니다.

그러면 일반항의 모양이 나오겠죠?

그러면 계수만 따로 떼서 이 수열의 일반항은 너여! 이러면 끝나는 겁니다

3. 생성함수를 이항급수로 나타내기

일단 저번 포스팅의 결과를 다시 끌어오죠

$ C(x) = \frac{1-\sqrt{1-4x}}{2x} $

자 여기서 어떻게 하면 다시 '무한급수'형태로 다시 바꿀 수 있을까요?

$ (1+x)^n $을 이산적으로 풀어낸 이항정리에서 이걸 무한급수로 풀어낸 이항급수로의 변환을 기억하고 계실까요?(https://omnil.tistory.com/223)

왠지 이걸로 '무한급수'형태를 만들 수 있을 것 같지 않나요?

마침 저기 식에도 비슷한 꼴이 보입니다. 루트는 $ \frac{1}{2} $승이라고 볼 수도 있으니까,

$ (1+(-4)x)^\frac{1}{2} $

이 친구가 이항급수의 꼴이네요~

그러면 바로 슉슈슉슉 조작을 가해볼까요?

이항급수는 아래와 같은 식으로 정의됩니다.

$ (1+x)^n = \sum \limits _{k=0} ^\infty \frac{1}{k!} \prod_{i=1}^{k} (n - i + 1) x^k = \sum \limits _{k=0} ^\infty \binom{n}{k} x^k $

[ 그리고 여기서 $ k=0 $항과 $ k=1 $항은 독특하게 정의됨을 알 수 있습니다.

애초에 $ k=0 $항은 곱셈구간이 정의되지 않으므로 무조건 1이 나오며, $ k=1 $항은 무조건 계수가 $ n $이 나오는 걸 알 수 있죠. ]

이제 위 식에 대입해보면

$ (1+(-4)x)^\frac{1}{2} = \sum \limits _{k=0} ^\infty \binom{\frac{1}{2}}{k} (-4x)^k = \sum \limits _{k=0} ^\infty \frac{\frac{1}{2}\left(-\frac{1}{2}\right)\cdots\left(\frac{1}{2}-k+1\right)}{k!}(-4x)^k $

가 되고, 풀어쓰면

$ 1 + \frac{1}{2}(-4x) + \frac{\frac{1}{2}\left(-\frac{1}{2}\right)}{2!}(-4x)^2 + \cdots $

부호는 상수항을 빼고는 전부 마이너스 부호가 나옵니다.

- 거듭제곱이 홀수면 거듭제곱의 부호는 음수이지만, 계수에서의 부호가 양수이므로 마이너스

- 거듭제곱이 짝수면 거듭제곰의 부호는 짝수이지만, 계수에서의 부호가 음수이므로 마이너스

이기 때문이죠.

결국 제일 초항인 상수항 만을 제외하고 전부 마이너스로 묶으면 이제 부호는 신경쓸 필요가 없어진단 말이겠군요.

그렇다면 이부분을 부호상관없이 바꿔보겠습니다.

$ \frac{1}{2}-k+1 $ 여기에 절대값을 취하면(부호상관 없어졌으니 다 양수로 갈음합니다)

$ \frac{\vert 1-2k+2 \vert}{2} =  \frac{2k-3}{2} $ ($ k \ge 2 $에서 양수가 나오게 수식 변형합니다. $ k = 1 $은 위에서 봤듯이 무조건 $ n $입니다.)

그러면 주어진 수식은 다음과 같이 변형됩니다.

$ 1 - \frac{\frac{1}{2}}{1!}(4x) - \sum \limits _{k=2} ^\infty \underbrace{ \frac{\frac{1}{2}\frac{3}{2}\cdots\left(\frac{2k-3}{2}\right)}{k!}(4x)^k } $

수식을 다 쓰기가 힘드니까 underbrace한 부분만 따로 떼놓고 봅시다.

$ \frac{\frac{1}{2}\frac{3}{2}\cdots\left(\frac{2k-3}{2}\right)}{k!}(4x)^k $

분모를 따로 빼고, 분자의 모습을 보면

분자에서 분모는 무조건 2인 상태로 k번 반복해서 곱해지고 있으므로 $ 2^k $입니다.

$ \frac{1}{k!}\frac{1\cdot3\cdot\ ... \  \cdot (2k-3)}{2^k} 2^{2k}x^k $

수식 정리하면

$ \frac{1\cdot3\cdot\ ... \  \cdot (2k-3)}{k!} 2^{k}x^k $

분자를 잘 보면 1, 3, 5, ..., 2k-3 으로 홀수로 증가하고 있습니다.

뭔가 조작을 가해주면 아주 깔끔하게 팩토리얼로 표현할 수 있을 것 같은데 말이죠...

바로... 빈 짝수들을 끼워넣어주면 되겠네요!

2, 4, 6, ..., 2k-2을 사이사이에 넣어주면 왠지 (2k-2)!할 수 있겠죠?

짝수들은 다 2가 곱해진 형태이고, 2를 다 나눠주면 자연수랑 같아지잖아요? 그렇다면..

$ 2^{k-1}(1\cdot2\cdot...\cdot (k-1)) $ 요렇게 정리가 되겠고.. 뒷부분은 간단하게 다시 팩토리얼로 정리가능하겠네요

$ 2^{k-1}(k-1)! $

입니다.

자, 이제 끼워넣어 줍시다.

잘 보면 이미 식에 $ 2^k $가 있죠?

분모분자에 같은 식을 곱해줍시다.

$ \frac{1\cdot3\cdot\ ... \  \cdot (2k-3)(k-1)!2^{k-1}}{k!(k-1)!} 2x^k $

$ \frac{(2k-2)!\cdot2}{k!(k-1)!} x^k$

다시 전체 식을 써주면

$ 1 - \underbrace{\frac{\frac{1}{2}}{1!}(4x)}_{1} - \sum \limits _{k=2} ^\infty \underbrace { \frac{2(2k-2)!}{k!(k-1)!} x^k }_{2}$

자, 근데 이제 2번 underbrace를 잘 봐봅시다.

여기서 $ k = 1 $인 상황을 한번 봐볼까요?

$ \frac{2 * 0!}{1!0!}x = 2x $

어? 1번 underbrace와 같군요!

아하~ 아까는 부호문제로 포함하지 못했던 $ k=1 $도, 수식이 정리되고 나니 한꺼번에 합칠 수 있겠네요!

그렇게 다시 쓰면

$ (1+(-4)x)^\frac{1}{2} = 1 - 2\sum \limits _{k=1} ^\infty \frac{(2k-2)!}{k!(k-1)!} x^k $

여기서, $ k $는 1부터 시작하는데, 우리는 처음에 멱급수 0부터 시작했었으니까 index조정해줍시다.

지금까지 따라오시면서 index조정은 이제 일도 아니시잖아요들?



$ (1+(-4)x)^\frac{1}{2} = 1 - 2\sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^{k+1} $


자, 그럼 이제 생성함수 $ C(x) $에 이걸 대입시켜 정리하도록 하죠!



$ C(x) = \frac{1-\sqrt{1-4x}}{2x} = \frac{1}{2x} \left(1- \underline{(1+(-4)x)^\frac{1}{2}}\right) $

$ = \frac{1}{2x}\left(1-\left(1 - 2\sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^{k+1}\right)\right) $

$ = \frac{1}{2x} 2\sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^{k+1} $

$ = \frac{1}{2x} 2x\sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^k $

$ = \sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^k $

와우! 뭔가 엄청 깔끔하게 정리가 되었습니다!

4. 무한급수 형태에서 계수를 꺼내기

그럼 다시 처음에 저희 카탈란 수열의 생성함수를 정의하던 순간으로 돌아가볼까요?

$ C(x) = \sum \limits _{k=0} ^\infty C_k x^k $

오 그렇다면

$  \sum \limits _{k=0} ^\infty C_k x^k = C(x) = \sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^k $

$  \sum \limits _{k=0} ^\infty C_k x^k = \sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^k $

자, 여기서 저희는 수열이 궁금했었어서 멱함수에 대응시켜줬었죠? 그러면 멱함수 부분을 떼버리고 계수만 본다면?

$  C_k = \frac{(2k)!}{(k+1)!k!} $

우와! 일반항을 구했습니다!

5. 일반항을 다시 정리

자 이 일반항을 다시 예쁘게 쓰면

가 되고, 이건 제일 처음 조합적 아이디어로 일반항을 구한 식과 완전히 동일합니다.(진짜 맞나 궁금해요? https://omnil.tistory.com/222)

완전 신기하지 않나요?

6. 미리니름

자, 사실은 앵간하면 점화식으로 정의된 수열의 일반항은 생성함수까지 오면 거의 끝이나 마찬가지인데요,

저는 여기서 한단계 더 나아가서 라그랑주 역함수 정리(Lagrange Inversion Theorem)까지 소개시켜드리도록 하겠습니다!

그리고 이번 포스팅도 엄청 길어졌네요...

다음에 보아요!