初等整数論/多項式と数列

与えられた多項式 $f(x)$ に対し、多項式の値 $(f(0),)f(1),f(2),\dots$ は数列をなす。 たとえば等差数列は1次式によってあらわされる数列といえる。また、与えられた整数 $m$ について m角数 を順に並べた数列は、

$a_n=\frac{(m-2)n^2-(m-4)n}{2}$

と多項式によりあらわされる。

数列の総和

多項式で表される数列の総和について、次の基本的な定理が成り立つ。

定理 $a_n=P(n)$ が $d$ 次多項式によって表される数列であるとき、総和 $S_n=P(1)+\cdots +P(n)$ は $d+1$ 次の多項式によってあらわされる。

証明
$P(x)=a_d{x}^d+\cdots +a_{1}x+a_0$ とおく。 $P(x)$ の次数 $d$ に関する帰納法で証明する。

$P(x)=c$ が0次多項式、つまり定数である場合 $P(1)+P(2)+\cdots +P(n)=cn$ は一次式であらわされる。

$k$ より低い次数について証明されたとして、$k$次の多項式 $P(x)$ について証明する。二項定理より

$x^{k+1}-(x-1{)}^{k+1}=x^{k+1}-\sum _{i=0}^{k+1}(-1{)}^i(\genfrac{}{}{0ex}{}{k+1}{i})x^{k+1}$

となるが、この係数を書き出すと

$x^{k+1}-(x^{k+1}-(k+1)x^k+\frac{k(k+1)}{2}{x}^{k-1}-+\cdots )=(k+1)x^k-\frac{k(k+1)}{2}{x}^{k-1}+\cdots$

となり、これは最高次の係数が $k+1$ の $k$ 次多項式であるから

$Q(x)=\frac{a_k{x}^{k+1}}{k+1}-\frac{a_k(x-1{)}^{k+1}}{k+1}$

は最高次の係数が $a_{k+1}$ の $k$ 次多項式である。 したがって $R(x)=P(x)-Q(x)$ は高々 $k-1$ 次の多項式である。よって $U(n)=R(n)+R(n-1)+\cdots +R(1)$ は高々 $k$ 次の多項式であらわされる。 ここで

$Q(n)+Q(n-1)+\cdots +Q(1)=\frac{a_k}{k+1}\sum _{m=1}^n(m^{k+1}-(m-1{)}^{k+1})=\frac{a_m{n}^{k+1}}{k+1}$

より

$P(n)+P(n-1)+\cdots +P(1)=\frac{a_k{n}^{k+1}}{k+1}+U(n)$

と $k+1$ 次の多項式で表される。

となる。

例 $P(x)=x^2$ の和、つまり $1^2+2^2+\cdots +n^2$ を求める。

$\frac{n^3-(n-1{)}^3}{3}=\frac{3n^2-3n+1}{3}=n^2-n+\frac{1}{3}$

より

$\sum _{k=1}^n{k}^2=\frac{n^3}{3}+\sum _{k=1}^n(k-\frac{1}{3})=\frac{n^3}{3}+\frac{n(n+1)}{2}-\frac{n}{3}=\frac{2n^3+3n^2+n}{6}=\frac{n(n+1)(2n+1)}{6}$

が成り立つ。

また、特殊な例として、二項係数 $(\genfrac{}{}{0ex}{}{n}{m})$ は $m$ を一つに決めれば、$n(\ge m)$ の多項式で表される数列となる。ここで

$f_m(x)=\frac{(x+1)(x+2)\cdots (x+m)}{m!}$

とおくと、 各 $f_m(x)$ は $m$ 次多項式で、 $n=0,1,\dots$ に対し、その値は

$f_m(n)=\frac{(n+1)(n+1)(n+2)\cdots (n+m)}{m!}=(\genfrac{}{}{0ex}{}{n+m}{m})$

に一致する。上の関係から

$f_{m+1}(n)=(\genfrac{}{}{0ex}{}{n+m+1}{m+1})=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{m+k}{m})=\sum _{k=0}^n{f}_m(k)$

が成り立つ。

図形数

m角数 について以前触れたが、より一般に高次元の図形と関係づけられる整数列が存在する。

最も単純な例として、立方体状に並べられた点の個数は

$a_n=n^3$

で表される。立方体に関連付けられることから 立方数 という。

次に、正四面体状に並べられた点の個数はどうなるか。そこで次のように正四面体状に球を積んでいくことを考える。まず最上段に1個、それを囲む形で、その次の段に3個の球を三角形状に配置し、それを囲む形で、その次の段には 1+2+3=6個の球を三角形状に配置していく。

同じようにして k 段目には $\frac{k(k+1)}{2}$ 個の球を三角形状に配置すると、右図のような形となる。このようにして n 段積んだときの球の個数は、先程示した二項係数の関係式から、

$\sum _{k=1}^n\frac{k(k+1)}{2}=\sum _{k=1}^n(\genfrac{}{}{0ex}{}{k+1}{2})=(\genfrac{}{}{0ex}{}{n+2}{3})=\frac{n(n+1)(n+2)}{6}$

となる。そこでこの形の数を四面体数あるいは三角錐数という。三角錐数は小さい方から 1, 4, 10, 20, 35, 56, ... となる。

次に、四角錐（ピラミッド）状に並べられた点の個数を考える。

4段の四角錐数は 1²+2²+3²+4²=30

今度は右図のように最上段に1個、その次の段に2²=4個、その次の段に3²=9個、と何段かの正四角錐の形に積んだときの、球の総数を数えることになるが、n 段積んだ時の球の個数は $1^2+2^2+3^2+\cdots +n^2$ 個に一致するから、先程示したように

$\sum _{k=1}^n{k}^2=\frac{n(n+1)(2n+1)}{6}$

に一致する。そこでこの形の数を四角錐数という。四角錐数は小さい方から 1, 5, 14, 30, 55, 91, ... となる。