[수학의 기초] 생성함수에 대하여 (1) [더플러스수학]

수학1의 수열에서 수학적 귀납법 단원 중 수열의 점화식이 나오는 문제를 풀 때, 점화식 마다 풀이 방법을 외워야 해서 학생들이 많이 힘들어 합니다. 물론 이 과정은 교과에 빠졌지만 상위권학생은 풀이 과정을 이해하고 외워야 합니다.

이 문제를 다른 관점에서 해결하고자 "생성함수"(generating function)에 대해 가볍게 알아보고 이를 이용하여 점화식을 한번 풀어 보겠습니다.

 

---

일반적으로 수열 $\displaystyle \left\{ a_n \right\}~(n=0,~1,~2,~\cdots)$에 대하여 $$\displaystyle g(x)=a_0 +a_1 x+a_2 x^2 + \cdots+a_n x^n +\cdots =\sum_{\textcolor{red}{n=0}}^{\infty}a_n x^n$$ 을  수열 $\displaystyle a_n$의 생성함수(generating function)라고 한다.

---

참고 여기서 멱급수-무한차수의 다항식-이 수렴하느냐 아니냐는 중요하지 않고 단지 생성함수를 이용하여 생성함수 $g(x)$의 $n$차항 $a_n x^n$의 계수인 수열의 일반항이나 계수들의 관계인 점화식을 구하는데 쓴다.

또, 고등학교에서 수열을 정의할 때, 항이 $n=1,~2,~3,~\cdots$인 자연수에서 정의하지만 생성함수에서는 $n \geq 0$인 정수에서 정의한다는 사실에 주의해야 한다. 

수열 $\displaystyle \left\{a_n \right \}$이 정해지면 $x^n$의 계수가 $a_n$인 생성함수가 정해진다. 이제 간단한 생성함수에 대해 알아보자.

 

생성함수의 종류

 

1) $\displaystyle a_n =1 ~(n=0,~1,~2,~\cdots)$인 수열 $$\displaystyle 1,~1,~1,~\cdots$$ 의 생성함수 $\displaystyle g(x)=\frac{1}{1-x}$이다.

왜냐하면 공비가 $x$인 등비급수의 합은 $\displaystyle \frac{1}{1-x}$이기 때문이다. 즉 $$\displaystyle \sum_{n=0}^{\infty} x^n = 1+x+x^2+\cdots+x^n+\cdots=  \frac{1}{1-x}$$

여기서 $x^n$의 계수 $a_n =1$이다. 물론 여기서 등비급수가 수렴할 조건을 굳이 따질 필요가 없다. 형식적인 표현이 필요하기 때문에.

예를 들어 점화식 $\displaystyle a_1 =1,~a_{n+1}=2a_n$의 일반항을 구해보자.

수열 $a_n$의 생성함수를 $g(x)$라 하자.

먼저 점화식 $a_{n+1}=2a_n$의 양변에 $x^{n+1}$을 곱하여 $\displaystyle \sum_{n=0}^{\infty}$를 취하면

$$\displaystyle   \sum_{n=0}^{\infty} a_{n+1}x^{n+1} =2 \sum_{n=0}^{\infty} a_n x^{n+1} =2x \sum_{n=0}^{\infty} a_n x^n  =2x g(x)$$

또, 좌변은

$$\displaystyle \begin{align}  \sum_{n=0}^{\infty} a_{n+1}x^{n+1} &= \sum_{n=1}^{\infty} a_n x^{n} =\sum_{n=0}^{\infty} a_n x^n  -a_0 \\&= g(x)- \frac{1}{2} \end{align}$$

이 두식은 서로 같으므로

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

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

$\displaystyle \frac{1}{1-x}= 1+x+x^2+\cdots+x^n+\cdots= \sum_{n=0}^{\infty} x^n$이므로 $g(x)$는

$$\displaystyle   \begin{align} g(x)&=\frac{1}{2} \frac{1}{1-2x}= \frac{1}{2} + \frac{1}{2}(2x)+ \frac{1}{2} (2x)^2 + \cdots+ \frac{1}{2} (2x)^n +\cdots \\&= \sum_{n=0}^{\infty} \frac{1}{2} (2x)^n =\sum_{n=0}^{\infty}  2^{n-1} x^n \end{align}$$

따라서 생성함수 $g(x)$의 $x^n$의 계수 $a_n$은 $2^{n-1}$이므로 $a_n = 2^{n-1}$이다.

 

2) $\displaystyle a_n =n ~(n=0,~1,~2,~\cdots)$인 수열 $$\displaystyle 0,~1,~2,~\cdots,~n,~\cdots$$ 의 생성함수 $\displaystyle g(x)=\frac{x}{(1-x)^2}$이다.

$\displaystyle \sum_{n=0}^{\infty} x^n = 1+x+x^2+\cdots+x^n+\cdots=  \frac{1}{1-x}$

이 식의 양변을 형식적으로 미분하면 (미분가능성은 생각하지 말고)

$$\displaystyle \begin{align} \sum_{n=1}^{\infty} nx^{n-1} =  1+2x+3x^2+\cdots+nx^{n-1}+(n+1)x^n+\cdots=  \frac{1}{(1-x)^2}\end{align}$$

여기서 양변에 $x$를 곱하면 

$$\displaystyle \begin{align} \sum_{n=1}^{\infty} (n+1)x^{n+1} =  1x+2x^2+3x^3+\cdots+nx^n+\cdots=  \frac{x}{(1-x)^2}\end{align}$$

여기서 $n=0$일 때는 $0 x^0$이므로

$$\displaystyle \begin{align} \sum_{n=0}^{\infty} nx^{n} = 0x^0+ 1x+2x^2+3x^3+\cdots+nx^n+\cdots=  \frac{x}{(1-x)^2}\end{align}$$

이다. 따라서 $x^n$의 계수는 $n$이므로 $\displaystyle a_n =n ~(n=0,~1,~2,~\cdots)$, 즉 생성함수는 $\displaystyle  \frac{x}{(1-x)^2}$ 이다.

 

이제 생성함수를 이용하여 $\displaystyle a_1 ,~ a_{n+1}=a_n +d$인 등차수열의 일반항이 $a_n =a +(n-1)d$임을 보여보자.

먼저 $a_0 = a_1 -d$이고 이 수열의 생성함수를 $g(x)$라 하면 $a_{n+1}=a_n +d$의 양변에 $x^{n+1}$을 곱하고 $\displaystyle \sum_{k=0}^{\infty}$를 취하자. 그러면 좌변은

$$\displaystyle \begin{align} \sum_{k=0}^{\infty} a_{n+1}x^{n+1} &=\sum_{k=0}^{\infty} a_n x^n -a_0 \\&=g(x)-a_1 +d \end{align}$$

또 우변은

$$\displaystyle \begin{align} \sum_{k=0}^{\infty} \left\{a_{n}x^{n+1} +d\right \} &=x \sum_{k=0}^{\infty} a_n x^n +d \sum_{k=0}^{\infty} x^{n+1} \\&=xg(x)+\frac{dx}{1-x} \end{align}$$

위의 두 식에 서로 같으므로

$$g(x)-a_1 +d =  x g(x) + \frac{dx}{1-x},~~\therefore ~g(x)= \frac{a_1 -d}{1-x}+ d \frac{x}{(1-x)^2}$$

따라서 $g(x)$는

$$\begin{align} g(x)&= \frac{a_1 -d} {1-x}+ d \frac{x}{(1-x)^2}\\&= (a_1 -d) \left\{ 1+x+x^2 +\cdots+ x^n +\cdots\right\}\\&+ d \left(x+2x^2 +3x^3 + \cdots+ nx^n + \cdots\right) \end{align}$$

여기서 $g(x)$의 $x^n$의 계수 $a_n$은

$$a_n = (a_1 -d)+ d n =a_1 + (n-d)d$$

이다.

2021.08.06 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 생성함수(4)

[더플러스수학] 카탈란 수 - 생성함수(4)