Tuenterによるあるタイプの2項係数の和
この記事では, Tuenterによる2項係数の絶対値付きの和に関する定理を紹介する.
Bruckmanによる絶対値付き2項係数の和の問題と予想
おそそ25年前, Paul S. BruckmanはFQに次の問題を出した.
整数$n \geq0$において,
$\displaystyle \sum_{k=0}^{2n}{2n \choose k}|n-k|^3=n^2{2n \choose n}.$
B-871の問題, The Fibonacci Quarterly 37.1(1999)
B-871の解答, The Fibonacci Quarterly 38.1(2000)
さらに, Bruckmanは以下の予想を残した.
予想 (by Bruckman).
整数$r\geq0$が与えられているとき, すべての整数$n \geq0$に対して以下の等式を満たす次数$r$の$n$の多項式$p_{r}(n)$が存在する.
$\displaystyle \sum_{k=0}^{2n}{2n \choose k}|n-k|^{2r+1}=p_{r+1}(n){2n \choose n}.$
※ 後の話とうまくつなげるため, オリジナルの表現を少し変えている.
Tuenterによる絶対値付き2項係数の和の性質
いま, 整数$r \geq 0$に対して$\displaystyle S_{r}(n)$を以下のように定義する. ここで, $0^0=1$と約束する.
$\displaystyle S_{r}(n):=\sum_{k=0}^{2n}{2n \choose k}|n-k|^{r}.$
また, $S_{r}(n)$は次のように書き換えられることに注意する.
$\displaystyle S_{r}(n)=2\sum_{k=0}^{n}{2n \choose n-k}k^r-{2n \choose n} \delta _{r0}$ ($\delta _{ij}$はクロネッカーのデルタ).
このとき, [1]でTuenterは以下の主張をした.
整数$r \geq 0$に対して,
(i) $ S_{2r+1}(n)=P_{r}(n)n{2n \choose n}$となる次数$r$の$n$の多項式$P_{r}(n)$が存在する.
(ii) $S_{2r}(n)=Q_{r}(n)2^{2n-r}$となる次数$r$の$n$の多項式$Q_{r}(n)$が存在する.
この定理の(i)においてBruckmanの予想を解決していることになる.
この記事の目的は可能な限り丁寧にこの定理を証明することである. オリジナルでは分かりにくい部分が多いため, 高校生でも理解できるように努めた. (そのため, 証明が長くなってしまった...).
まず, 以下の補題を証明しよう.
整数$r \geq 0$に対して,
$S_{0}(n)=2^{2n},\; S_{1}(n)=n{2n \choose n},$
$S_{r+2}(n)=n^2S_{r}(n)-2n(2n-1)S_{r}(n-1).$
・$\displaystyle S_{0}(n)=\sum_{k=0}^{2n}{2n \choose k}=2^{2n}.$
・$\displaystyle S_{1}(n)=\sum_{k=0}^{n}2k{2n \choose n-k}=\sum_{k=0}^{n}\left[(n+k){2n \choose n+k}-(n-k){2n \choose n-k}\right]$
$\displaystyle =\sum_{k=0}^{n}\left[2n{2n-1 \choose n+k-1}-2n{2n-1 \choose n-k-1}\right]=\sum_{k=0}^{n}\left[2n{2n-1 \choose n+k-1}-2n{2n-1 \choose n+k}\right]$
$\displaystyle =2n{2n-1 \choose n-1}-2n{2n-1 \choose 2n}=n{2n \choose n}.$
・ $\displaystyle n^2S_{r}(n)+n^2{2n \choose n} \delta _{r0}-S_{r+2}(n)=2n^2\sum_{k=0}^{n}{2n \choose n-k}k^r-2\sum_{k=0}^{n}{2n \choose n-k}k^{r+2}$
$\displaystyle =2\sum_{k=0}^{n}\frac{(2n)!}{(n-k)!(n+k)!} \cdot k^r(n+k)(n-k)=2\sum_{k=0}^{n}\frac{2n(2n-1)(2n-2)!}{(n-k-1)!(n+k-1)!} \cdot k^r$
$\displaystyle =2n(2n-1) \cdot 2\sum_{k=0}^{n-1}{2(n-1) \choose (n-1)-k}k^r=2n(2n-1)\left[S_{r}(n-1)+{2n-2 \choose n-1}\delta _{r0}\right]$
$\displaystyle =2n(2n-1)S_{r}(n-1)+2n(2n-1) \cdot \frac{(2n-2)!}{((n-1)!)^2}\delta _{r0}$
$\displaystyle =2n(2n-1)S_{r}(n-1)+n^2\frac{(2n)!}{(n!)^2}\delta _{r0}=2n(2n-1)S_{r}(n-1)+n^2{2n \choose n}\delta _{r0}.$
したがって,
$S_{r+2}(n)=n^2S_{r}(n)-2n(2n-1)S_{r}(n-1).$ $\blacksquare$
この補題を使って目的の定理を証明する.
帰納法で証明する.
(i) $r=0$のとき, $S_{1}=1 \cdot n{2n \choose n}$となり, $P_{0}=1$($n$の0次式)として存在する.
$ S_{2r+1}(n)=P_{r}(n)n{2n \choose n}$となる次数$r$の$n$の多項式$P_{r}(n)$が存在すると仮定すると
$S_{2r+3}(n)=n^2S_{2r+1}(n)-2n(2n-1)S_{2r+1}(n-1)$
$=n^2P_{r}(n)n{2n \choose n}-2n(2n-1)P_{r}(n-1)(n-1){2n-2 \choose n-1}$
$=n^3P_{r}(n){2n \choose n}-n^2(n-1)P_{r}(n-1){2n \choose n}$
$=\left[ n^2(P_{r}(n)-P_{r}(n-1))+nP_{r}(n-1)\right]n{2n \choose n}.$
よって, $S_{2r+3}(n)=P_{r+1}(n)n{2n \choose n}$となる次数$r+1$の$n$の多項式$P_{r+1}(n)$が存在する.
(ii) $r=0$のとき, $S_{0}=1 \cdot 2^{2n-0}$となり, $Q_{0}=1$($n$の0次式)として存在する.
$ S_{2r}(n)=Q_{r}(n)2^{2n-r}$となる次数$r$の$n$の多項式$Q_{r}(n)$が存在すると仮定すると
$S_{2r+2}(n)=n^2S_{2r}(n)-2n(2n-1)S_{2r}(n-1)$
$=n^2Q_{r}(n)2^{2n-r}-2n(2n-1)Q_{r}(n-1)2^{2n-2-r}$
$=\left[ 2n^2(Q_{r}(n)-Q_{r}(n-1))+nQ_{r}(n-1)\right]2^{2n-r-1}.$
よって, $S_{2r+2}(n)=Q_{r+1}(n)2^{2n-(r+1)}$となる次数$r+1$の$n$の多項式$Q_{r+1}(n)$が存在する. $\blacksquare$
具体例
定理2の証明の中で$P_{r}(n)$と$Q_{r}(n)$の$r$についての漸化式を得ているのであらためて整理しておこう.
$P_{r+1}(n)=n^2(P_{r}(n)-P_{r}(n-1))+nP_{r}(n-1);$
$Q_{r+1}(n)=2n^2(Q_{r}(n)-Q_{r}(n-1))+nQ_{r}(n-1).$
これを使えば具体的に$P_{r}(n)$や$Q_{r}(n)$を次々に計算することができる.
$P_{0}(n)=1,\ P_{1}(n)=n,\ P_{2}(n)=2n^2-n,\ P_{3}(n)=6n^3-8n^2+3n,\cdots ;$
$Q_{0}(n)=1,\ Q_{1}(n)=n,\ Q_{2}(n)=3n^2-n,\ Q_{3}(n)=15n^3-15n^2+4n,\cdots.$
すなわち,
$\displaystyle \sum_{k=0}^{2n}{2n \choose k}|n-k|=n{2n \choose n},$
$\displaystyle \sum_{k=0}^{2n}{2n \choose k}|n-k|^2=n \cdot 2^{2n-1},$
$\displaystyle \sum_{k=0}^{2n}{2n \choose k}|n-k|^3=n^2{2n \choose n},$
$\displaystyle \sum_{k=0}^{2n}{2n \choose k}|n-k|^4=(3n^2-n)2^{2n-2},$
$\displaystyle \sum_{k=0}^{2n}{2n \choose k}|n-k|^5=(2n^3-n^2){2n \choose n},$
$\displaystyle \sum_{k=0}^{2n}{2n \choose k}|n-k|^6=(15n^3-15n^2+4n)2^{2n-3},$
$\displaystyle \sum_{k=0}^{2n}{2n \choose k}|n-k|^7=(6n^4-8n^3+3n^2){2n \choose n}$
$ \cdots .$.
(参考文献)
[1] H.J.H.Tuenter, Walking into an absolute sum, The Fibonacci Quarterly 40.2(2002)
