二項係数を特定の順序で並べた数列$\{a_n\}$について、以下の問いに答える問題です。 (1) $nC_k$ は数列$\{a_n\}$の第何項になるかを求めます。 (2) $\sum_{k=1}^{2n^2} a_k$ を求めます。ただし、$0C_0=1$とします。

1. 問題の内容

二項係数を特定の順序で並べた数列$\{a_n\}$について、以下の問いに答える問題です。

(1) $nC_k$ は数列$\{a_n\}$の第何項になるかを求めます。

(2) $\sum_{k=1}^{2n^2} a_k$ を求めます。ただし、$0C_0=1$とします。

2. 解き方の手順

(1) $nC_k$が数列の第何項になるかを考える。数列の並び方は、${}^0C_0, {}^1C_0, {}^1C_1, {}^2C_0, {}^2C_1, {}^2C_2, {}^3C_0, {}^3C_1, {}^3C_2, {}^3C_3, ...$ となっている。

これは、${}^pC_q$において$p$が$0$から順に大きくなり、$p$が一定のときは、$q$が$0$から$p$まで変化していることに対応する。

${}^nC_k$の前に並んでいる項の数は、

$\sum_{p=0}^{n-1} (p+1) = \sum_{p=1}^{n} p = \frac{n(n+1)}{2}$ である。

したがって、${}^nC_k$は数列の $\frac{n(n+1)}{2} + (k+1)$ 番目の項である。

(2) $\sum_{k=1}^{2n^2} a_k$を求める。数列$\{a_n\}$は二項係数を並べたものであるから、二項定理を用いることを考える。

二項定理より、$(1+x)^m = \sum_{k=0}^{m} {}^mC_k x^k$である。$x=1$を代入すると、$2^m = \sum_{k=0}^{m} {}^mC_k$となる。

数列$\{a_n\}$の最初のいくつかの項の和を計算してみると、

$a_1 = {}^0C_0 = 1$

$a_1+a_2 = {}^0C_0 + {}^1C_0 = 1+1 = 2$

$a_1+a_2+a_3 = {}^0C_0 + {}^1C_0 + {}^1C_1 = 1+1+1 = 3$

$a_1+a_2+a_3+a_4 = {}^0C_0 + {}^1C_0 + {}^1C_1 + {}^2C_0 = 1+1+1+1 = 4$

$\sum_{k=0}^{m} (k+1) = \sum_{m=0}^{M} {}^mC_k$

となる$M$は、$\frac{M(M+1)}{2} < 2n^2 \leq \frac{(M+1)(M+2)}{2}$ を満たす。

$m(n) = \sum_{k=0}^{n} {}^nC_k = 2^n$

数列$\{a_n\}$を$0$から順番にグループ分けすることを考える。

$1$番目のグループ: ${}^0C_0$ ($1$個)

$2$番目のグループ: ${}^1C_0, {}^1C_1$ ($2$個)

$3$番目のグループ: ${}^2C_0, {}^2C_1, {}^2C_2$ ($3$個)

...

$n$番目のグループ: ${}^{n-1}C_0, {}^{n-1}C_1, ..., {}^{n-1}C_{n-1}$ ($n$個)

$N$番目のグループまで足すと、項数は$\frac{N(N+1)}{2}$個となる。

$\frac{N(N+1)}{2} \le 2n^2$ より、$N(N+1) \le 4n^2$

$N \approx 2n$

$S_N = \sum_{i=1}^N \sum_{k=0}^{i-1} {}^{i-1}C_k = \sum_{i=1}^N 2^{i-1} = \frac{2^N - 1}{2-1} = 2^N - 1$

$\sum_{k=1}^{2n^2} a_k$ の$2n^2$が$\frac{N(N+1)}{2}$と一致するとは限らないので、調整が必要。

$\frac{N(N+1)}{2} \le 2n^2$を満たす最大の$N$について考える。

$N(N+1) \le 4n^2$

$N^2+N-4n^2 \le 0$

$N \approx \frac{-1+\sqrt{1+16n^2}}{2} \approx \frac{-1+4n}{2} \approx 2n$

$\sum_{k=1}^{\frac{N(N+1)}{2}} a_k = \sum_{i=0}^{N-1} \sum_{j=0}^i {}^iC_j = \sum_{i=0}^{N-1} 2^i = 2^N - 1$

残り $2n^2-\frac{N(N+1)}{2}$ 項を足す必要がある。

$\sum_{k=1}^{2n^2} a_k = 2^N-1 + \sum_{j=0}^{2n^2 - \frac{N(N+1)}{2}-1} {}^{N}C_j$

3. 最終的な答え

(1) $\frac{n(n+1)}{2} + k + 1$

(2) $2^N-1 + \sum_{j=0}^{2n^2 - \frac{N(N+1)}{2}-1} {}^{N}C_j$, ただし、$N$は$\frac{N(N+1)}{2} \le 2n^2$を満たす最大の整数。