자연계열 1번

[문제 1-1] 1) $\displaystyle n$개의 자리에 0 또는 1이 들어갈 수 있으므로 $\displaystyle a_n=2^n$이다.

2) $\displaystyle b_1=2$이다. $\displaystyle n\ge2$일 때 $\displaystyle b_n$을 다음 두 가지 경우로 나누어 계산해 보자:- 첫 자리에 1이 오는 경우: 1이 연달아서 나타날 수 없으므로 두 번째 자리에는 반드시 0이 와야 한다. 세 번째부터는 1이 연달아 나타나지 않는 길이 $\displaystyle n-2$인 0과 1의 나열이면 되므로 이 경우 가능한 개수는 $\displaystyle b_{n-2}$이다.- 첫 자리에 0이 오는 경우: 두 번째 자리부터의 나열이 1이 연달아 나타나지 않는 길이 $\displaystyle n-1$인 0과 1의 나열이면 되므로 $\displaystyle b_{n-1}$개의 나열이 가능하다.따라서 $\displaystyle b_n=b_{n-1}+b_{n-2}$이다. 이는 예제 1의 수열 $\displaystyle \{d_n\}$의 점화식과 동일하며 $\displaystyle b_0=d_1$, $\displaystyle b_1=d_2$이므로 $\displaystyle \{b_n\}$의 생성함수 $\displaystyle B(x)=d_1+d_2x+d_3x^2+\cdots=\frac1x(d_1x+d_2x^2+d_3x^3+\cdots)$이다. 즉 $\displaystyle B(x)=\frac1x(D(x)-1)$. 이를 정리하면 $\displaystyle B(x)=\frac{1+x}{1-x-x^2}$이다.

[문제 1-2] $\displaystyle x_0=x_1=x_2=\cdots=1$이라 하면 $\displaystyle w_n=d_0+d_1+\cdots+d_n=d_0x_n+d_1x_{n-1}+\cdots+d_nx_0$이므로 $\displaystyle \{w_n\}$의 생성함수는 $\displaystyle D(x)X(x)=\frac1{(1-x-x^2)(1-x)}$이다.

[문제 1-3]$\displaystyle \begin{aligned}E(x)&=e_0+e_1x+e_2x^2+e_3x^3+\cdots\\&=0+x+(e_0e_0)+(e_0e_1+e_1e_0)x+(e_0e_2+e_1e_1+e_2e_0)x^2+(e_0e_3+e_1e_2+e_2e_1+e_3e_0)x^3+\cdots\\&=x+E(x)E(x)\end{aligned}$이므로 $\displaystyle E(x)$는 $\displaystyle E(x)E(x)-E(x)+x=0$을 만족한다.(따라서 $\displaystyle E(x)=\frac{1\pm\sqrt{1-4x}}2$가 되며 이 중 $\displaystyle x=0$일 때 0이 되는 함수는 $\displaystyle \frac{1-\sqrt{1-4x}}2$이므로 $\displaystyle E(x)=\frac{1-\sqrt{1-4x}}2$이다.)