j(n)
を n!
と書いて、これを n の階乗とよびます：
(12-21a) 0! º 1 |
(12-21b) s(n)! º n!s(n) |
帰納法と (11-3)
から明らかなように、n!
は 0 になりません。さて、
が成り立つことを n に関する帰納法で証明します。まず n が 0 のときは k も 0 でなければならないので明らかに成り立ちます。
次に n で成り立つと仮定し、k £ s(n)
と仮定します。
このとき k £ n 又は k º s(n)
ですが、前者の場合、帰納法の仮定により k! | n!
であり、(12-21b)
により n! | s(n)!
ですから、(12-8c)
により k! | s(n)!
が成り立ちます。また後者の場合は証明すべき式は s(n)! | s(n)!
となり明らかです。ゆえに帰納法が完成しました。
また、帰納法により k ³ 1 なら k | k!
が成り立つことは明らかですから、これと (12-8d),(12-22)
により
(12-23) 1 £ k £ n Þ k | n! |
がわかります。
さて、n!
は (12-23)
により 2 以上 n 以下の任意の整数で割り切れるので、n!
+ 1 は 2 以上 n 以下の整数では割り切れず、したがって特に n 以下の素数では割り切れません。ところが n!
+ 1 は自然数ですから、前段で示したように、ある素数 p で割り切れます。すると p > n でなければなりません。以上により、任意の自然数 n に対し、n より大きい素数が存在することがわかりました。よって、前節 (11-38)
〜(11-39)
により、n より大きい素数の中で最小のものが存在します。これを仮に l(n)
と書くことにし、帰納的構成の式 (10-7)
で c を 1 、F(n,x)
を l(x)
としたときの j(n)
を pn と書いて、n > 0 のとき、これを第n番目の素数とよびます：
(12-24a) p0 º 1 |
(12-24b) ps(n) º l( pn ) |
さて、{ pn | nÎN+ }
はすべての素数を含んでいます。実際、定義から pn < ps
(
n)
であって、しかもこの両者の間には素数はありません。従って帰納法で明らかなように、任意の自然数 n に対して pn > n が成り立ちます。よって特に、任意の素数 p に対して pn > p となる最小の n が存在します。これは p = pn-1 であることを示しています。
以上の結果から、特に素数の全体は可算集合であることがわかります。
次に、自然数の素因数分解の一意的存在：
(12-25) n º |
k
Õ
i=1 |
piei ( ei > 0 ) |
を帰納法で証明しましょう。
p1 º 2 ですから、n º 2 のときは k º 1 , e1 º 1 とすれば (12-25)
は成り立ちます。また、e1 > 1 あるいは ei > 0 となる i > 1
が存在したとすると、右辺は 2 より大きくなってしまうので、一意性も明らかです。
次に、(12-25)
の存在と一意性が n より小さい自然数に対しては成り立つと仮定します。n が素数のときは、n º pk となる k が存在しますから、ek º 1 , ei º 0 ( i < k )
と置けば存在は明らかで、もし k と等しくない j に対して ej > 0 となったとすれば、素数 n º pk がこれと等しくない素数 pj を約数に持つことになるので矛盾します。よって一意性も証明されました。
他方、n が合成数のときは、ある素数で割り切れますから、ある j に対して n º pjm と書け、m < n なので、帰納法の仮定により m は (12-25)
の右辺の形に一意的に書けます。ゆえに n は ej を 1 増やした形の同様な表示を持つことがわかります。
逆に n が (12-25)
の形に書けたとすると、i が j と等しくなければ pj と pi は互いに素で、しかも pj |
n ですから、(12-14)
を繰り返し用いることにより、pj |
pjej であることがわかり、これより ej > 0 がわかります。ゆえに m に対して (12-25)
の ej を ej - 1 に置き換えた式が成り立ちますが、帰納法の仮定により、その表示は一意的です。ゆえに n の表示も一意的であることがわかり、主張は証明されました。
次に、k £ n に対し、k に関する帰納的構成 (11-30)
によって nP
k を次のように定義します：
(12-26a) nP 0 º 1 |
(12-26b) nPs(k) º (n - k) nPk ( k < n ) |
この nP
k は、#
A º n であるような集合 A における、長さ k の一対一な有限列全体の個数に他ならないことが k に関する帰納法で証明できます。
実際、長さ s(k)
の一対一有限列は、長さ k の一対一有限列と、残る n - k 個の中から任意に選んだ s(k)
における値によって定まるからです。
また、
(12-27) (n - k)! nPk º n! |
が成り立つことを k に関する帰納法で証明しましょう。実際、k が 0 のときは (12-26a)
により明らかです。
また k で正しいと仮定し、２項演算 + や - が連続していてしかも演算が左から順に行われる場合は括弧を省略することにすれば、
(12-28) (n - s(k))! nPs(k) º (n - (k + 1))!(n - k) nPk º (n - k - 1)!s((n - k) - 1) nPk º s(n - k - 1)! nPk º (n - k)! nPk º n! |
となって帰納法が完成し、証明されました。
次に、(12-27)
で n と k をそれぞれ s(n)
と s(k)
に置き換えれば、s(n) - s(k) º (n + 1) - (k + 1)
º n + 1 - 1 - k º n - k ですから
(12-29) (n - k)! s(n)Ps(k) º (s(n) - s(k))! s(n)Ps(k) º s(n)! º n!s(n) º (n - k)! nPk s(n) |
階乗は 0 にならないので、これと (11-10b)
により
(12-30) s(n)Ps(k) º s(n) nP k |
が成り立つことがわかります。そこで
(12-31) "m £ n : m! | nP m |
が成り立つことを n に関する帰納法で証明しましょう。
まず n が 0 のときは、m も 0 なので明らかです。
次に、(12-31)
が n で成り立つと仮定し、n を s(n)
に置き換えた場合について考えます。m が 0 のときは明らかですから、m º s(k)
と書ける場合を考えれば十分です。(12-30)
と (12-26b)
により
(12-32) s(n)Ps(k) º s(n) nPk º s(n - k + k) nPk º (n - k + s(k)) nPk º (n - k) nPk + s(k) nPk º nPs(k) + s(k) nP k |
ここで帰納法の仮定により nPs(k)
は s(k)!
で割り切れ、nP
k は k!
で割り切れるので s(k) nP
k は s(k)!
で割り切れ、従って (12-32)
の左辺も s(k)!
で割り切れることがわかり、帰納法が完成しました。
そこで、nP
k を k!
で割った商を nC
k と書くことにします：
(12-33) nC k :º |
nP k
——
k! |
:º nPk / k! |
そこで、一般に j |
i のとき k > 0 に対して (ik)/( jk) º i/
j が成り立つことに注意して、(12-32)
を s(k)! º k!s(k)
で割れば、
(12-34) s(n)Cs(k) º nCs(k) + nCk ( k < n ) |
という公式が得られます。また、(12-27),(12-33)
により
(12-35a) nC k º |
n!
————
k!(n - k)! |
º nC n-k |
(12-35b) nC0 º nC n º |
n!
——
n!0! |
º 1 |
が成り立ちます。
さて、個数 n の集合 A に対し、Sub(A)
の元のうち判定可能な集合の全体を Dec(A)
と書くことにし、これを集合の相等を同値関係に持つ集合とみなすと、これは可識な集合です。
実際、B, CÎDec(A)
のとき、xÎA に対し、命題 xÎB と xÎC について排中律が成り立つので、命題 xÎB Û xÎC についても排中律が成り立つことがわかり、しかも A は有限集合ですから、"xÎA ( xÎB Û xÎC )
すなわち B = C という命題に対して排中律が成り立ちます。
そこで更に、各 k £ n :º #
A に対し、Dec(A)
の元 B のうち #
B = k であるようなものの全体を Deck(A)
と書くとき、この集合は可識で
(12-36) #Deck(A) º nCk ( k £ n º #A ) |
が成り立つことを証明しましょう。
実際、まず #
B º 0 と B = Æ は同値なので、Dec0(A)
= 1 です。ゆえにこれと (12-35b)
により、k º 0 のときは証明されました。
ゆえに #
A º 0 の場合に成立することは明らかです。そこで A の個数に関する帰納法によることにし、#
A º n のとき正しいと仮定し、#A º s(n)
の場合について証明します。しかも k º 0 のときは既に証明されているので、k を s(k)
に置き換えて証明できれば十分です。
さて、A ¹ Æ なので、任意に aÎA を選びます。このとき Decs(k)(A)
の元 B は、a を元に持つか持たないかいずれかです。そこで、前者のような B の全体を A 、後者のような B の全体を B と書きます。
ここで a :º { xÎA | x =A a }
と置き、B に B \
a を対応させる写像は、A から Deck(A \ a )
への全単射であり、しかも #(A \ a )
º n ですから、帰納法の仮定により #A º #Dec(A \ a ) º nC
k となります。
また、B にそれ自身を対応させる写像は、B から Decs(k)(A \ a )
への全単射なので、帰納法の仮定により #B º #Decs(k)(A \ a ) º nCs(k)
となります。
ゆえに (12-34)
により #Decs(k)(A) º #A + #B º s(n)Cs(k)
が得られ、帰納法が完成しました。
さて、(12-34),(12-35)
を用いて二項定理を導いてみましょう。A を同値関係 = を持つ集合で、= と両立し、結合法則と交換法則を満たし単位元を持つ加法 + と乗法 ·
が与えられ、それらの間に分配法則が成り立っているものとします。このとき、任意の a,
bÎA と任意の自然数 n に対して
(12-37) (a + b) n = |
n
å
k=0 |
nC k ak bn-k |
が成り立つことを n に関する帰納法で証明します。
まず、n が 0 のときは、両辺共に乗法の単位元になりますから成立します。次に n で正しいと仮定すると、(12-34),(12-35),(11-24e),(11-24k)
により
(12-38) (a + b)s(n) |
|
|
= |
n
å
k=0 |
nC k ak bn-k (a + b) |
|
|
= |
n
å
k=0 |
nC k as( k) bn-k + |
n
å
k=0 |
nC k ak bs ( n-k) |
|
|
= |
n
å
k=0 |
nCs(k)-1 as(k) bs(n)-s(k) + |
n
å
k=0 |
nC k ak bs ( n) -k |
|
|
= |
s(n)
å
k=1 |
nC k-1 ak bs ( n) -k + |
n
å
k=0 |
nC k ak bs ( n) -k |
|
|
= as(n) + |
n
å
k=1 |
nC k-1 ak bs ( n) -k + |
n
å
k=1 |
nC k ak bs ( n) -k + bs (n) |
|
|
= as(n) + |
n
å
k=1 |
s(n)C k ak bs ( n) -k + bs (n) |
|
|
= |
s(n)
å
k=0 |
s(n)C k ak bs ( n) -k |
|
となって帰納法が完成しました。特に (12-37)
で a º b º 1 とすれば、
が得られます。従って、(12-36)
を k について 0 から n まで加えて (12-39)
を用いれば
(12-40) #Dec(A) º |
n
å
k=0 |
#Deck(A) º |
n
å
k=0 |
nCk º 2n ( n º #A ) |
が得られます。
さて、二項定理 (12-36)
を拡張した多項定理：
(12-41) (a1 + ¼ + ar ) n = |
å
k1+¼+ kr= n |
æ
è |
n
k1 ¼ kr |
ö
ø |
a1k1 ¼ arkr |
が成り立つことを r に関する帰納法で証明しましょう。ただし
(12-42) |
æ
è |
n
k1 ¼ kr |
ö
ø |
:º nC k1 · n-k1C k2 · n-k1-k2C k3 · ¼ · n-k1-¼-kr-1C kr º |
n!
————
k1! ¼ kr! |
と定義し、これを多項係数といいます。
定義により、この係数が、個数 n の集合から個数 ki の互いに交わらない部分集合 Ai を選んで作る列 ( Ai )
1 £ i £ r 全体の個数に他ならないことがわかります。
さて、(12-41)
の証明ですが、r が 1 のときは明らかです。次に r で正しいと仮定すると、(12-37)
により、
(12-43) (a1 + ¼ + ar + as(r) ) n = |
n
å
k=0 |
nCk (a1 + ¼ + ar )k as(r) n-k = |
n
å
k=0 |
n!
————
k!( n - k)! |
å
k1+¼+ kr= k |
k!
————
k1! ¼ kr! |
a1k1 ¼ arkr as(r) n-k |
となり、n - k を ks(r)
と置けば、(12-41)
で r を s(r)
に置き換えたものが得られ、帰納法が完成しました。
なお、(12-42)
の記法は r º 1 に対して使うことはほとんどないので、紛れのない限り、２項係数を
とも書くことにします。
さて、二項定理の応用として、r, nÎN
に対する
(12-45) sr(n) :º |
n
å
k=1 |
k r |
を、小さな r に対して n の式として具体的に表してみましょう。
(12-46) (n + 1) r+1 - 1 º |
n
å
k=1 |
(k + 1) r+1 - |
n
å
k=1 |
k r+1 º |
n
å
k=1 |
r
å
i=0 |
æ
è |
r + 1
i |
ö
ø |
ki º |
r
å
i=0 |
æ
è |
r + 1
i |
ö
ø |
si(n) |
という関係式が成り立ちますから、r = 0,
1,
2,
3 についてこれを書き下せば、
(12-47a) n º (n + 1) - 1 º s0(n) |
(12-47b) n² + 2n º (n + 1)² - 1 º s0(n) + 2s1(n) |
(12-47c) n³ + 3n² + 3n º (n + 1)³ - 1 º s0(n) + 3s1(n) + 3s2(n) |
(12-47d) n4 + 4n³ + 6n² + 4n º (n + 1)4 - 1 º s0(n) + 4s1(n) + 6s2(n) + 4s3(n) |
ゆえに、これらを順に解いて、
(12-48b) s1(n) º |
n² + 2n - s0(n)
——————
2 |
= |
n² + 2n - n
————–
2 |
= |
n(n + 1)
———–
2 |
(12-48c) s2(n) º |
n³ + 3n² + 3n - s0(n) - 3s1(n)
————————————
3 |
= |
2n³ + 6n² + 6n - 2n - 3n(n + 1)
————————————–
6 |
= |
2n³ + 3n² + n
—————–
6 |
= |
n(n + 1)(2n + 1)
——————–
6 |
(12-48d) s3(n) º |
n4 + 4n³ + 6n² + 4n - s0(n) - 4s1(n) - 6s2(n)
——————————————————
4 |
= |
n4 + 4n³ + 6n² + 4n - n - 2n(n + 1) - 2n³ - 3n² - n
————————————————————–
4 |
= |
n4 + 2n³ + n²
—————
4 |
= |
n²(n + 1)²
————
4 |
が得られます。
この節の最後に、自然数の p進表示について解説します。
p を 1 より大きい自然数とします。任意の自然数 n に対し、自然数の列 ( qk )kÎN
を、
(12-49a) q0 º n |
(12-49b) qs(k) º [qk / p] |
で帰納的に定義し、自然数の列 r :º ( rk )kÎN
を
(12-50) rk :º rem(qk , p) |
で定義します。qs(k)
< qk ですから、帰納法により k £ n なら qk £ n - k となることがわかるので、k ³ n なら qk º 0 で、従って rk º 0 です。また
ですから、n > 0 なら両辺に pk を乗じて k について辺々加えることにより
(12-52) |
dig n
å
k=0 |
qk pk º |
dig n
å
k=0 |
qs(k) ps(k) + |
dig n
å
k=0 |
rk pk |
が得られます。ただし、rk > 0 であるような最大の k を dig
n と書きました。ゆえに (11-2)
により
(12-53) n º q0 p0 º |
dig n
å
k=0 |
rk pk |
が得られます。この (11-49)
の右辺の表示を n のp進表示といい、特に p º s(9)
の場合を十進表示といいます。
そして、0 から 9 までの数字をいくつか並べたとき、この記号列は、並んでいる数字を右から順に rk としたときの十進表示における (11-49)
の n を意味するものと約束します。従って、10 と書いたら、これは s(9)
を意味することになります。
