初等整数論/数列

数列は文字の通り数の列である。意味のない数の羅列でも数列ということができるが、それでは余りにも面白くないので規則性を持った数列について考えることにしよう。

等差数列

まず簡単に考えつくのは、自然数を小さい方から並べていった数列である。

$1,2,3,4,\cdots$

または、偶数、奇数を並べていった数列

$2,4,6,8,10,\cdots$

$1,3,5,7,9,\cdots$

これらは次の数との差が常に等しいため、等差数列 と呼ばれる。他の等差数列を考えてみよう。

$6,13,20,27,34,\cdots$

$2,7,12,17,\cdots$

このように考えていくと、等差数列の性格は、最初に来る数と差の数で全て決まるということが考えられる。

数列の各数字は項といって、第n項、という。特に第1項を初項という。また等差数列の場合、差の数は公差という。

数列というのは実は数論的関数のことで、$\psi (n)=3n+1$ とように、関数を $a_{n}$ と表すと約束する。

さて、等差数列の一般形を考えてみよう。

$d,d+r,d+2r,d+3r,\cdots$

この数列を ${a_{n}}$ と表すことにすると、$a_{n}=d+(n-1)r$ となる。試しに小さい数で確かめると、

${\begin{aligned}a_{1}&=d+(1-1)r\iff a_{1}=d\\a_{2}&=d+(2-1)r\iff a_{2}=d+r\\a_{3}&=d+(3-1)r\iff a_{3}=d+2r\\\end{aligned}}$

となって正しいことが推測される。

さて、このようにして $a_{n}$ を式で表すことができた。これを数列の一般項という。

総和

さて、等差数列の第n項目までの数の総和について考えてみよう。先ほどの数列

$6,13,20,27,34$

の総和を考える。単純に

$S=6+13+20+27+34$

としてももちろん良いのだが、これでは余りに一般性がない。そこで、次のようなことを考える。

${\begin{aligned}S&=6+13+20+27+34\\S&=34+27+20+13+6\\&\therefore 2S=40+40+40+40+40\iff S=100\end{aligned}}$

縦に見ると、縦2つの和は常に等しい。だからこのように計算するとうまく求まるのである。

さて、この考え方を一般的な等差数列に拡張してみよう。第k項までの総和の公式を導いてみる。考え方は、初項と第k項を足したものにkをかけて2で割るである。

${\begin{aligned}S&=d+(d+r)+(d+2r)+\cdots +(d+(k-2)r)+(d+(k-1)r)\\S&=(d+(k-1)r)+(d+(k-2)r)+\cdots (d+2r)+(d+r)+d\\&\therefore 2S=d+(d+(k-1)r)\ +\ (d+r)+(d+(k-2)r)\ +\ \cdots \\&+\ (d+(k-2)r)+(d+r)\ +\ (d+(k-1)r)+d\\&\iff 2S=(2d+(k-1)r)+(2d+(k-1)r)+\cdots +(2d+(k-1)r)\\&\iff 2S=(2d+(k-1)r)k\\&\iff S={\frac {1}{2}}(2d+(k-1)r)k\\\end{aligned}}$

あるいは簡単に、$S={\frac {1}{2}}k(a_{1}+a_{k})$

この公式を使って先ほどの初項 6、公差 7 の数列を第5項まで足したものを計算してみる。

${\begin{aligned}S&={\frac {1}{2}}(2\cdot 6+(5-1)\cdot 7)\cdot 5\\&={\frac {1}{2}}(12+28)\cdot 5\\&=20\cdot 5\\&=100\end{aligned}}$

となった。公式はおそらく正しいのだろうと推測される。しかしこれではまだ厳密さは得られていないので、厳密性を得るには数学的帰納法を用いて証明すれば良い。その具体的な内容は省くが、数列では数学的帰納法がかなり役立つということを知っておいて欲しい。

問 等差数列の総和の公式が正しいことを数学的帰納法を用いて証明せよ。

総和記号

総和を一々言葉で表現するのは面倒なので記号を用いて表す。

$\sum _{i=m}^{n}a_{i}=a_{m}+a_{m+1}+\cdots +a_{n}$

という記号が一般的に使われる。

さて、総和の公式というものをここで確かめていく。どれも総和記号を外して考えればほとんど自明である。

公式 1

${\begin{aligned}&\sum _{i=m}^{n}(a_{i}+b_{i})=\sum _{i=m}^{n}a_{i}\ +\ \sum _{i=m}^{n}b_{i}\\&\sum _{i=m}^{n}ca_{i}=c\left(\sum _{i=m}^{n}a_{i}\right)\\\end{aligned}}$

これを先ほどの等差数列の公式を表すと、次のように表わせる。

$a_{n}=d+(n-1)r\ \ (n\geqq 1)$

${\begin{aligned}\sum _{i=1}^{k}a_{i}&={\frac {1}{2}}(a_{1}+a_{k})k\\&={\frac {1}{2}}(2d+(k-1)r)k\end{aligned}}$

例えば、次のような数列

$a_{n}=n$

の総和は、

${\begin{aligned}\sum _{i=1}^{k}a_{i}&={\frac {1}{2}}(a_{1}+a_{k})k\\&={\frac {1}{2}}(k+1)k\end{aligned}}$

等比数列

等比数列とは、次の数がその数の定数倍になっている数列である。例えば、

$1,2,4,8,16,32,\cdots$

$2,10,50,250,1250,\cdots$

一般項は

$a_{n}=dr^{n-1}$

である。このときの $r$ を公比という。

総和

まずは、$1+2+4+8+16+\cdots$ を考える。

$S=1+2+4+8+16+\cdots 2^{n-1}$

となる。ここで、次の因数分解の公式を使う。

$x^{n}-y^{n}=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\cdots +y^{n-2}x+y^{n-1})$

${\begin{aligned}&2^{n}-1=(2-1)(2^{n-1}+2^{n-2}+\cdots +2+1)\\&\iff 2^{n}-1=(2-1)S\\&\iff S={\frac {2^{n}-1}{2-1}}\end{aligned}}$

さて、これを一般の場合に適応してみる。

$a_{n}=dr^{n-1}$ とする。

$S=a_{1}+a_{2}+a_{3}+\cdots +a_{n}$ として、

${\begin{aligned}&r^{n}-1=(r-1)(r^{n-1}+r^{n-2}+\cdots +r+1)\\&\iff d(r^{n}-1)=(r-1)(dr^{n-1}+dr^{n-2}+\cdots +dr+d)\\&\iff d(r^{n}-1)=(r-1)S\\&\iff S={\frac {d(r^{n}-1)}{r-1}}\end{aligned}}$

となり、公式が求まった。もちろん、公比は 1 ではない。公比が 1 のときは、公差 0 の等比数列になる。

別の導き方としては、

${\begin{aligned}S&=d+dr+dr^{2}+\cdots +dr^{n-1}\\rS&=\ \ \ \ \ dr+dr^{2}+\cdots +dr^{n-1}+dr^{n}\\\end{aligned}}$

$\therefore rS-S=dr^{n}-d\iff (r-1)S=d(r^{n}-1)\iff S={\frac {d(r^{n}-1)}{r-1}}$

さて、これで等比数列の公式が求まった。しかしこれは厳密な導き方とは言えない。そこで厳密な証明を与えるならば、やはり数学的帰納法を用いる。数学的帰納法でこの公式の妥当性を証明するのは読者に任せる。

総和記号の公式

先ほど総和記号の公式を挙げたが、他にもある。

公式 2

$\sum _{i=n}^{m}a_{i}=\sum _{i=n+k}^{m+k}a_{i-k}$

証明

${\begin{aligned}\sum _{i=n+k}^{m+k}a_{i-k}&=a_{n+k-k}+a_{n+1+k-(1+k)}+\cdots a_{m+k-k}\\&=a_{n}+a_{n+1}+\cdots +a_{m}\\&=\sum _{i=n}^{m}a_{i}\end{aligned}}$

より厳密に証明するならば、m > n であることを利用して、m = n + c とおいて、c について数学的帰納法を用いればよいだろう。

問

数学的帰納法を用いた厳密な方法で証明せよ。

公式 3

$\sum _{i=1}^{m}\sum _{j=1}^{n}a_{i}b_{j}=\left(\sum _{i=1}^{m}a_{i}\right)\left(\sum _{j=1}^{n}b_{j}\right)$

証明

${\begin{aligned}\sum _{i=1}^{m}\sum _{j=1}^{n}a_{i}b_{j}&=\sum _{i=1}^{m}a_{i}(b_{1}+b_{2}+\cdots +b_{n})\\&=a_{1}(b_{1}+\cdots +b_{n})+a_{2}(b_{1}+\cdots +b_{n})+\cdots +a_{m}(b_{1}+\cdots +b_{n})\\&=(a_{1}b_{1}+a_{1}b_{2}+\cdots +a_{1}b_{n})+(a_{2}b_{1}+a_{2}b_{2}+\cdots +a_{2}b_{n})+\cdots +(a_{m}b_{1}+a_{m}b_{2}+\cdots +a_{m}b_{n})\\&=b_{1}(a_{1}+a_{2}+\cdots a_{m})+b_{2}(a_{1}+a_{2}+\cdots a_{m})+\cdots +b_{n}(a_{1}+a_{2}+\cdots a_{m})\\&=(b_{1}+b_{2}+\cdots +b_{n})\left(\sum _{i=1}^{m}a_{i}\right)\\&=\left(\sum _{j=1}^{n}b_{i}\right)\left(\sum _{i=1}^{m}a_{i}\right)\\&=\left(\sum _{i=1}^{m}a_{i}\right)\left(\sum _{j=1}^{n}b_{i}\right)\end{aligned}}$

より厳密に証明するならば、m についての数学的帰納法を用いる。その際、m = 1 が正しいことを証明するときに、n に関する数学的帰納法を用い、m = k のとき正しいならば m = k+1 も正しいことを証明するときにも、n に関する数学的帰納法を用い、と二重で数学的帰納法が出てきて複雑になるかも知れないが、厳密な証明はこれしかないのである。