$n$，$k$を，$1 \leqq k \leqq n$を満たす整数とする。$n$個の整数
\[2^m \quad (m=0, \, 1, \, 2, \, \ldots, 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$に対し，$x$についての整式
\[f_n(x)=1+a_{n,1}x+a_{n,2}x^2+\cdots\cdots+a_{n,n}x^n\]を考える。 $\dfrac{f_{n+1}(x)}{f_n(x)}$と $\dfrac{f_{n+1}(x)}{f_n(2x)}$を $x$についての整式として表せ。
(3)$\dfrac{a_{n+1,k+1}}{a_{n,k}}$を$n,k$で表せ。
\[\begin{align*} a_{n,2} &=\sum_{0 \le i \lt j \le n-1} 2^i2^j \\ &= \sum_{j=1}^{n-1} (2^j-1)2^j \\ &= \sum_{j=1}^{n-1} (4^j-2^j) \\ &= \dfrac{4^n-4}{3} - (2^n-2) \\ &= \dfrac{4^n-3 \cdot 2^n + 2}{3} \end{align*}\]言われた通りにできますか? という問題。ただ文科と共通で文科の人には難しめかもしれない。
漸化式を立てる。最終的には $f_{n+1}(x)/f _ n(x) = 1+2^nx, f _ {n+1}(x) / f _ {n}(2x) = 1+x$ となる。
(2) で2種類の漸化式を立てたので、それらから $a _ {n,k+1}$ を消去すれば良い。
(2) で
\[\begin{align} a _ {n+1,k+1} = a_{n,k} \cdot 2^n + a _ {n,k+1} \tag{1} \\ a _ {n+1,k+1} = a_{n,k} \cdot 2^k + a _ {n,k+1} \cdot 2^{k+1} \tag{2} \\ \end{align}\]が言える。 $2^{k+1}(1) - (2)$ を計算すると、
\[(2^{k+1}-1)a _ {n+1,k+1} = a _ {n,k} \cdot 2^k \cdot (2^{n+1}-1)\]となるため、
\[\dfrac{a _ {n+1,k+1}}{a _ {n,k}} = \dfrac{2^k (2^{n+1}-1)}{2^{k+1}-1}\]が答えである。
Tweet