現代数学解説

Tuenterによるあるタイプの2項係数の和

二項係数,絶対値

122

この記事では, Tuenterによる2項係数の絶対値付きの和に関する定理を紹介する.

Bruckmanによる絶対値付き2項係数の和の問題と予想

おそそ25年前, Paul S. BruckmanはFQに次の問題を出した.

Elementary problem B-871 by Bruckman

整数 $n \geq 0$ において,
　 $\sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k |^{3} = n^{2} (\binom{2 n}{n}) .$

B-871の問題, The Fibonacci Quarterly 37.1(1999)
　B-871の解答, The Fibonacci Quarterly 38.1(2000)

さらに, Bruckmanは以下の予想を残した.

予想 (by Bruckman).
　整数 $r \geq 0$ が与えられているとき, すべての整数 $n \geq 0$ に対して以下の等式を満たす次数 $r$ の $n$ の多項式 $p_{r} (n)$ が存在する.
　 $\sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k |^{2 r + 1} = p_{r + 1} (n) (\binom{2 n}{n}) .$

※ 後の話とうまくつなげるため, オリジナルの表現を少し変えている.

Tuenterによる絶対値付き2項係数の和の性質

いま, 整数 $r \geq 0$ に対して $S_{r} (n)$ を以下のように定義する. ここで, $0^{0} = 1$ と約束する.
　　 $S_{r} (n) := \sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k |^{r} .$
また, $S_{r} (n)$ は次のように書き換えられることに注意する.
　　 $S_{r} (n) = 2 \sum_{k = 0}^{n} (\binom{2 n}{n - k}) k^{r} - (\binom{2 n}{n}) δ_{r 0}$ 　( $δ_{i j}$ はクロネッカーのデルタ).
このとき, [1]でTuenterは以下の主張をした.

by Tuenter

整数 $r \geq 0$ に対して,
(i) $S_{2 r + 1} (n) = P_{r} (n) n (\binom{2 n}{n})$ となる次数 $r$ の $n$ の多項式 $P_{r} (n)$ が存在する.
(ii) $S_{2 r} (n) = Q_{r} (n) 2^{2 n - r}$ となる次数 $r$ の $n$ の多項式 $Q_{r} (n)$ が存在する.

この定理の(i)においてBruckmanの予想を解決していることになる.
この記事の目的は可能な限り丁寧にこの定理を証明することである. オリジナルでは分かりにくい部分が多いため, 高校生でも理解できるように努めた. (そのため, 証明が長くなってしまった...).
まず, 以下の補題を証明しよう.

整数 $r \geq 0$ に対して,
　 $S_{0} (n) = 2^{2 n}, S_{1} (n) = n (\binom{2 n}{n}),$
　 $S_{r + 2} (n) = n^{2} S_{r} (n) - 2 n (2 n - 1) S_{r} (n - 1) .$

補題3に対する証明

・ $S_{0} (n) = \sum_{k = 0}^{2 n} (\binom{2 n}{k}) = 2^{2 n} .$
　・ $S_{1} (n) = \sum_{k = 0}^{n} 2 k (\binom{2 n}{n - k}) = \sum_{k = 0}^{n} [(n + k) (\binom{2 n}{n + k}) - (n - k) (\binom{2 n}{n - k})]$
　　　　　 $= \sum_{k = 0}^{n} [2 n (\binom{2 n - 1}{n + k - 1}) - 2 n (\binom{2 n - 1}{n - k - 1})] = \sum_{k = 0}^{n} [2 n (\binom{2 n - 1}{n + k - 1}) - 2 n (\binom{2 n - 1}{n + k})]$
　　　　　 $= 2 n (\binom{2 n - 1}{n - 1}) - 2 n (\binom{2 n - 1}{2 n}) = n (\binom{2 n}{n}) .$
　・　 $n^{2} S_{r} (n) + n^{2} (\binom{2 n}{n}) δ_{r 0} - S_{r + 2} (n) = 2 n^{2} \sum_{k = 0}^{n} (\binom{2 n}{n - k}) k^{r} - 2 \sum_{k = 0}^{n} (\binom{2 n}{n - k}) k^{r + 2}$
　　 $= 2 \sum_{k = 0}^{n} \frac{(2 n)!}{(n - k)! (n + k)!} \cdot k^{r} (n + k) (n - k) = 2 \sum_{k = 0}^{n} \frac{2 n (2 n - 1) (2 n - 2)!}{(n - k - 1)! (n + k - 1)!} \cdot k^{r}$
　　 $= 2 n (2 n - 1) \cdot 2 \sum_{k = 0}^{n - 1} (\binom{2 (n - 1)}{(n - 1) - k}) k^{r} = 2 n (2 n - 1) [S_{r} (n - 1) + (\binom{2 n - 2}{n - 1}) δ_{r 0}]$
　　 $= 2 n (2 n - 1) S_{r} (n - 1) + 2 n (2 n - 1) \cdot \frac{(2 n - 2)!}{((n - 1)!)^{2}} δ_{r 0}$
　　 $= 2 n (2 n - 1) S_{r} (n - 1) + n^{2} \frac{(2 n)!}{(n!)^{2}} δ_{r 0} = 2 n (2 n - 1) S_{r} (n - 1) + n^{2} (\binom{2 n}{n}) δ_{r 0} .$
　したがって,
　　 $S_{r + 2} (n) = n^{2} S_{r} (n) - 2 n (2 n - 1) S_{r} (n - 1) .$ 　 $◼$

この補題を使って目的の定理を証明する.

定理2の証明

帰納法で証明する.
(i) $r = 0$ のとき, $S_{1} = 1 \cdot n (\binom{2 n}{n})$ となり, $P_{0} = 1$ ( $n$ の0次式)として存在する.
　 $S_{2 r + 1} (n) = P_{r} (n) n (\binom{2 n}{n})$ となる次数 $r$ の $n$ の多項式 $P_{r} (n)$ が存在すると仮定すると
　 $S_{2 r + 3} (n) = n^{2} S_{2 r + 1} (n) - 2 n (2 n - 1) S_{2 r + 1} (n - 1)$
　　　　　 $= n^{2} P_{r} (n) n (\binom{2 n}{n}) - 2 n (2 n - 1) P_{r} (n - 1) (n - 1) (\binom{2 n - 2}{n - 1})$
　　　　　 $= n^{3} P_{r} (n) (\binom{2 n}{n}) - n^{2} (n - 1) P_{r} (n - 1) (\binom{2 n}{n})$
　　　　　 $= [n^{2} (P_{r} (n) - P_{r} (n - 1)) + n P_{r} (n - 1)] n (\binom{2 n}{n}) .$
よって, $S_{2 r + 3} (n) = P_{r + 1} (n) n (\binom{2 n}{n})$ となる次数 $r + 1$ の $n$ の多項式 $P_{r + 1} (n)$ が存在する.
(ii) $r = 0$ のとき, $S_{0} = 1 \cdot 2^{2 n - 0}$ となり, $Q_{0} = 1$ ( $n$ の0次式)として存在する.
　 $S_{2 r} (n) = Q_{r} (n) 2^{2 n - r}$ となる次数 $r$ の $n$ の多項式 $Q_{r} (n)$ が存在すると仮定すると
　 $S_{2 r + 2} (n) = n^{2} S_{2 r} (n) - 2 n (2 n - 1) S_{2 r} (n - 1)$
　　　　　 $= n^{2} Q_{r} (n) 2^{2 n - r} - 2 n (2 n - 1) Q_{r} (n - 1) 2^{2 n - 2 - r}$
　　　　　 $= [2 n^{2} (Q_{r} (n) - Q_{r} (n - 1)) + n Q_{r} (n - 1)] 2^{2 n - r - 1} .$
よって, $S_{2 r + 2} (n) = Q_{r + 1} (n) 2^{2 n - (r + 1)}$ となる次数 $r + 1$ の $n$ の多項式 $Q_{r + 1} (n)$ が存在する.　　 $◼$

具体例

定理2の証明の中で $P_{r} (n)$ と $Q_{r} (n)$ の $r$ についての漸化式を得ているのであらためて整理しておこう.

$P_{r + 1} (n) = n^{2} (P_{r} (n) - P_{r} (n - 1)) + n P_{r} (n - 1);$
　 $Q_{r + 1} (n) = 2 n^{2} (Q_{r} (n) - Q_{r} (n - 1)) + n Q_{r} (n - 1) .$

これを使えば具体的に $P_{r} (n)$ や $Q_{r} (n)$ を次々に計算することができる.
　 $P_{0} (n) = 1, P_{1} (n) = n, P_{2} (n) = 2 n^{2} - n, P_{3} (n) = 6 n^{3} - 8 n^{2} + 3 n, \dots;$
　 $Q_{0} (n) = 1, Q_{1} (n) = n, Q_{2} (n) = 3 n^{2} - n, Q_{3} (n) = 15 n^{3} - 15 n^{2} + 4 n, \dots .$
すなわち,
　 $\sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k | = n (\binom{2 n}{n}),$
　 $\sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k |^{2} = n \cdot 2^{2 n - 1},$
　 $\sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k |^{3} = n^{2} (\binom{2 n}{n}),$
　 $\sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k |^{4} = (3 n^{2} - n) 2^{2 n - 2},$
　 $\sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k |^{5} = (2 n^{3} - n^{2}) (\binom{2 n}{n}),$
　 $\sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k |^{6} = (15 n^{3} - 15 n^{2} + 4 n) 2^{2 n - 3},$
　 $\sum_{k = 0}^{2 n} (\binom{2 n}{k}) | n - k |^{7} = (6 n^{4} - 8 n^{3} + 3 n^{2}) (\binom{2 n}{n})$
$\dots .$ .