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

与えられた多項式 $f(x)$ に対し、多項式の値 $(f(0),)f(1),f(2),\ldots$ は数列をなす。 たとえば等差数列は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}{\binom {k+1}{i}}x^{k+1}$

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

$x^{k+1}-\left(x^{k+1}-(k+1)x^{k}+{\frac {k(k+1)}{2}}x^{k-1}-+\cdots \right)=(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}\left(k-{\frac {1}{3}}\right)={\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}}$

が成り立つ。

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

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

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

$f_{m}(n)={\frac {(n+1)(n+1)(n+2)\cdots (n+m)}{m!}}={\binom {n+m}{m}}$

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

$f_{m+1}(n)={\binom {n+m+1}{m+1}}=\sum _{k=0}^{n}{\binom {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}{\binom {k+1}{2}}={\binom {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, ... となる。