도쿄대 2020-4(문과,이과)

 

 

 

 

$n, k$는 $1 \leq k \leq n$을 만족하는 정수이다. $n$개의 정수 $$2^m \qquad (m = 0,1,2,\cdots , n-1)$$ 중 서로 다른 $k$개를 고르고 그것들을 곱하자. $k$개를 고르는 모든 경우의 수에 대해 같은 방법으로 얻은 $_nC_k$개의 정수들의 합을 $a_{n,k}$라 하자. 예를 들어, $$a_{4,3} = 2^0 \cdot 2^1 \cdot 2^2 + 2^0 \cdot 2^1 \cdot 2^3+ 2^0 \cdot 2^2 \cdot 2^3+ 2^1 \cdot 2^2 \cdot 2^3 = 120$$이다.

 

1) 2 이상의 정수 $n$에 대해, $a_{n,2}$를 구하시오.

 

2) 1 이상의 정수 $n$에 대해, $f_n(x)$를 $$f_n(x) = 1+a_{n,1}x +a_{n,2}x^2 + \cdots + a_{n,n}x^n$$라고 하자. $\cfrac{f_{n+1}(x)}{f_n(x)}$와 $\cfrac{f_{n+1}(x)}{f_n(2x)}$를 간단히 하여라.

 

3) $\cfrac{a_{n+1,k+1}}{a_{n,k}}$를 $n,k$로 나타내어라. 

 

 

 

---

 

 

생각해보기)

 

1)은 $a_{n,k}$의 정의를 이용하는 계산문제, 3)은 2)의 결과를 이용하는 문제이기 때문에 가장 어려운 파트는 2)라 할 수 있다. 막연하고 어려운 문제이지만, $f_{n+1}(x)$는 $n+1$차 다항식, $f_{n}(x)$는 $n$차 다항식이므로 몫의 차수는 1차이고 상수항은 1일 수 밖에 없다. 즉, 몫은 $ax+1$의 꼴이다. 그러면 이제 문제는 $f_n+1(x)$의 $x^k$항과, $f_n(x)$의 $x^{k-1}, x^k$항의 관계를 찾는 걸로 귀결된다. (물론 직관적으로 풀기는 어려운 문제이다.)

 

 

 

 

풀이)

 

 

 

1) $2^m (m = 0, 1, 2, \cdots , n-1)$ 중 서로 다른 2개를 곱하고 모두 더한 값이 $a_{n,2}$이다. 다시 말해 $2^i \cdot 2^j$ 를 전부 더한 뒤 $i=j$인 경우를 빼고, 2로 나눈 값이 바로 $a_{n,2}$가 된다.

$$\begin{align} 2a_{n,2} &= \sum_{i=0}^{n-1}\sum_{i=0}^{n-1}2^i \cdot 2^j - \sum_{i=0}^{n-1}2^i \cdot 2^j\\&=\sum_{i=0}^{n-1}2^i \sum_{j=0}^{n-1}2^j -\sum_{i=0}^{n-1}4^i\\&=(2^n-1)(2^n-1)-\cfrac{4^n-1}{3}\\&=\cfrac{2}{3}4^n -2^{n+1}+\cfrac{4}{3} \end{align}$$

이므로, $$a_{n,2}=\cfrac{4^n}{3}-2^n +\cfrac{2}{3}$$이다.

 

 

 

 

2) $a_{n+1,k}$는 $2^m ( m=0, 1, 2, \cdots , n)$ 중 서로 다른 $k$개의 곱의 합이다. 여기서 서로 다른 $k$개가 '$2^n$'을 포함하는 경우와 그렇지 않은 경우로 나누어서 생각해보자.

 

만약 서로 다른 $k$개 중 $2^n$이 포함되어 있지 않다면, 그냥 $2^m (m = 0, 1, 2, \cdots , n-1)$ 중에서 서로 다른 $k$개의 곱의 합과 동일 하기 때문에 그 값은 $a_{n,k}$가 된다.

 

또 서로 다른 $k$개 중 $2^n$이 포함되어 있을 때에는, $2^m (m = 0, 1, 2, \cdots , n-1)$ 중에서 서로 다른 $k-1$개의 곱의 합 전체에 $2^n$을 곱한 것과 동일 하기 때문에 그 값은 $2^n a_{n,k-1}$이 된다.

따라서, $$a_{n+1,k}=2^n a_{n,k-1} + a_{n,k}$$ 인 관계식이 성립한다. 이제 $f_{n+1}(x)$에 대입하고 정리해보면, $$ \begin{align} &f_{n+1}(x)\\=&1+a_{n+1,1}x +a_{n+1,2}x^2 + \cdots + a_{n+1,n+1}x^{n+1}\\=&1+(2^na_{n,0}+a_{n,1})x+(2^na_{n,1}+a_{n,2})x^2 + \cdots + (2^n a_{n,n-1}+a_{n,n})x^n+(2^n a_{n,n}+a_{n,n+1})x^{n+1} \\=&1+a_{n,1}x+ \cdots + a_{n,n}x^n + 2^nx(1+a_{n,1}x+\cdots + a_{n,n}x^n)\\=&(1+2^nx)(1+a_{n,1}x+\cdots + a_{n,n}x^n)\\=&(1+2^nx)f_n(x) \end{align}$$이 되므로 $\cfrac{f_{n+1}(x)}{f_n(x)}=1+2^nx$이다.

 

$n=1$일 때, $f_1(x)=1+a_{1,1}x=1+x$이고, $f_{n+1}(x)=(1+2^nx)f_n(x)$를 이용해서 계속 대입해 나가면 $$f_n(x)=(1+2^{n-1}x)(1+2^{n-2}x)\cdots (1+2^1x)(1+x)$$가 된다. 이제 $x$자리에 $2x$를 대입하면, $$f_n(2x)=(1+2^nx)\cdots (1+2^2x)(1+2x)$$이다. 따라서 $$ \cfrac{f_{n+1}(x)}{f_n(2x)}=1+x$$이다.

 

 

 

 

3) 먼저 2)에서 얻은 점화식으로부터 $$a_{n+1,k+1} = 2^n a_{n,k}+a_{n,k+1}$$ 이 성립한다. 또, 2)의 마지막에 구한 관계식으로부터, $$f_{n+1}(x)=(1+x)f_n(2x)=(1+x)(1+a_{n,1}2x+a_{n,2}2^2x^2+ \cdots + a_{n,n}2^nx^n)$$ 이고, $x^{k+1}$의 계수를 비교하면 $$ a_{n+1,k+1}=2^{k+1}a_{n,k+1}+2^ka_{n,k}$$ 이다. 따라서, $$ \begin{align} 2^na_{n,k} + a_{n,k+1} &= 2^{k+1}a_{n,k+1}+2^ka_{n,k}\\(1-2^{k+1})a_{n,k+1}&=(2^k-2^n)a_{n,k}\\a_{n,k+1}&=\cfrac{2^n-2^k}{2^{k+1}-1}a_{n,k} \end{align}$$ 이다. 최종적으로, $$\begin{align} \cfrac{a_{n+1,k+1}}{a_{n,k}}&=\cfrac{2^na_{n,k}+a_{n,k+1}}{a_{n,k}}\\&=2^n +\cfrac{2^n-2^k}{2^{k+1}-1}\\&=\cfrac{2^{n+k+1}-2^k}{2^{k+1}-1} \end{align}$$ 이다.