2020年(令和2年)東京大学-数学(理科)[4] - [別館]球面倶楽部零八式markIISR

2020.10.14記

[4] $n$ ， $k$ を， $1 \leqq k \leqq n$ を満たす整数とする． $n$ 個の整数
$2^m (m=0, \, 1, \, 2, \, \cdots\cdots, \, n-1)$
から異なる $k$ 個を選んでそれらの積をとる． $k$ 個の整数の選び方すべてに対しこのように積をとることにより得られる ${}_n\mbox{C}_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$
を考える． $\displaystyle\frac{f_{n+1}(x)}{f_n(x)}$ と $\displaystyle\frac{f_{n+1}(x)}{f_n(2x)}$ を $x$ についての整式として表せ．

(3) $\displaystyle\frac{a_{n+1,k+1}}{a_{n,k}}$ を $n$ ， $k$ で表せ．

本問のテーマ

母関数

2020.02.26記

[解答]
$f_n(x)=(2^0x+1)(2^1x+1)\cdots(2^{n-1}x+1)$ である。

(1) $a_{n,2}$ $=2^0(2^n-2)+2^1(2^n-4)+\cdots+2^{n-2}(2^n-2^{n-1})$
$=(2^{n-1}-1)2^n-(2^1+2^3+\cdots+2^{2n-3})$
$=2^{2n-1}-2^n-\dfrac{2^{2n-1}-2}{3}=\dfrac{2^{2n}}{3}-2^n+\dfrac{2}{3}$

(2) $\dfrac{f_{n+1}(x)}{f_n(x)}=2^n x+1$ であり， $\dfrac{f_{n+1}(x)}{f_n(2x)}=x+1$ である．

(3) 以下 $a_{p,q}$ は $p\lt q$ のとき 0 であるとする．

$a_{n+1,k+1}$ は $f_{n+1}(x)$ の $x^{k+1}$ の係数であり， $a_{n,k}$ は $f_{n}(x)$ の $x^{k}$ の係数である．
$f_{n+1}(x)=f_n(x)(2^n x+1)=f_n(2x)(x+1)$ だから，
$a_{n+1,k+1}=2^n a_{n,k}+a_{n,k+1}=2^k a_{n,k}+2^{k+1}a_{n,k+1}$
が成立する． $a_{n,k+1}$ を消去して
$(2^{k+1}-1)a_{n+1,k+1}=(2^{n+k+1}-2^k) a_{n,k}$
となり
$\dfrac{a_{n+1,k+1}}{a_{n,k}}=\dfrac{2^{n+k+1}-2^k}{2^{k+1}-1}$
となる．

(3)は $k=n$ のときの場合分けが面倒なので
「以下 $a_{p,q}$ は $p\lt q$ のとき 0 であるとする．」
と書いておいた．

2020.02.26追記

先に(3)を求めてしまえば、(1)は

$a_{n,2}=\dfrac{2^{n+1}-2}{3}a_{n-1,1}$ $=\dfrac{2^{n+1}-2}{3}(2^{n-1}-1)$ $=\dfrac{2(2^n-1)(2^{n-1}-1)}{3}$

として求まる。また、異なる2つの積の和を求める方法として

$\dfrac{(1+2+\cdots+2^{n-1})^2-(1+2^2+\cdots+2^{2n-2})}{2}$ $=\dfrac{(2^n-1)^2-\dfrac{2^{2n}-1}{3}}{2}$ $=(2^n-1)\cdot\dfrac{(2^n-1)-\dfrac{2^{n}+1}{3}}{2}$ $=(2^n-1)\cdot\dfrac{2^n-2}{3}=\dfrac{2(2^n-1)(2^{n-1}-1)}{3}$

というのもある。

2020.08.08記
雲Tがnote書いていたので見るがよろし。
https://note.com/kumotaka/n/nd829ddf02e29note.com
（消えてしまった）