정답
특성다항식은 \(r^2-4r+4=0\) 이고, 수열 \(\{a_n\}\)의 일반항은 \(a_n = n2^{n}\)이다.
생성함수는 \(f(x)=\dfrac{2x}{(1-2x)^2}\) 이며, \(\displaystyle \sum_{n=0}^\infty b_nx^n = x\bigl(f(x/2)\bigr)^3\) 를 만족하는 수열 \(\{b_n\}\)의 일반항은
\[ b_n= \begin{cases} 0, & n=0,1,2,3,\\[4pt] \displaystyle \binom{n+1}{5}, & n\ge 4 \end{cases} \]
출제 의도
선형 점화식의 특성다항식과 일반해를 구하는 방법, 그리고 생성함수를 이용해 새로운 수열의 생성함수를 조작하여 계수를 조합론적으로 해석할 수 있는지를 평가하는 문제이다.
풀이 과정
점화식은 다음과 같다.
\[ a_0=0,\quad a_1=2,\quad a_n=4a_{n-1}-4a_{n-2}\quad (n\ge 2) \]
이 점화식의 특성다항식은
\[ r^2-4r+4=0 \]
이고, 이를 풀면
\[ (r-2)^2=0\quad\Rightarrow\quad r=2\ (\text{중근}) \]
중근 \(2\)이므로 일반해는
\[ a_n = (c_1+c_2n)2^n \]
이다. 초기 조건을 대입하면
\[ a_0=0=(c_1+0)2^0=c_1 \quad\Rightarrow\quad c_1=0, \] \[ a_1=2=(c_1+c_2)2=(0+c_2)2 \quad\Rightarrow\quad c_2=1 \]
따라서
\[ a_n = n2^n \]
을 얻는다.
이제 생성함수 \(f(x)=\sum_{n=0}^\infty a_nx^n\)을 구하자.
\[ f(x)=\sum_{n=0}^\infty n2^n x^n = \sum_{n=0}^\infty n(2x)^n \]
기본 공식 \(\sum_{n=0}^\infty nr^n = \dfrac{r}{(1-r)^2}\) (\(|r|<1\))을 사용하면, \(r=2x\) 에 대해
\[ f(x) = \frac{2x}{(1-2x)^2} \]
이다.
다음으로 수열 \(\{b_n\}\)는 생성함수 관계
\[ \sum_{n=0}^\infty b_nx^n = x\left(f\!\left(\frac{x}{2}\right)\right)^3 \]
를 만족한다. 먼저 \(f(x/2)\)를 구하면
\[ f\!\left(\frac{x}{2}\right) = \frac{2\cdot(x/2)}{\bigl(1-2\cdot(x/2)\bigr)^2} = \frac{x}{(1-x)^2} \]
따라서
\[ \left(f\!\left(\frac{x}{2}\right)\right)^3 = \frac{x^3}{(1-x)^6} \]
이고,
\[ \sum_{n=0}^\infty b_nx^n = x\cdot \frac{x^3}{(1-x)^6} = \frac{x^4}{(1-x)^6} \]
이제 \((1-x)^{-6}\)를 전개한다. 이항정리를 사용하면
\[ (1-x)^{-6} = \sum_{k=0}^\infty \binom{k+5}{5}x^k \]
이므로
\[ \sum_{n=0}^\infty b_nx^n = x^4\sum_{k=0}^\infty \binom{k+5}{5}x^k = \sum_{k=0}^\infty \binom{k+5}{5}x^{k+4} \]
지수 \(n=k+4\)로 두면 \(k=n-4\) 이고, 계수는
\[ b_n= \begin{cases} 0, & n=0,1,2,3,\\[4pt] \displaystyle \binom{(n-4)+5}{5}=\binom{n+1}{5}, & n\ge 4 \end{cases} \]
가 된다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>