演習問題 - 岡本研究室

離散数学 (13)
演習問題
2016 年 7 月 22 日
岡本吉央
提出締切： 2016 年 7 月 29 日講義終了時
復習問題 13.1 任意の正の整数 n に対して
追加問題 13.7 任意の正の整数 n に対して
8n − 3n が 5 で割り切れる
11n − 4n が 7 で割り切れる
ことを数学的帰納法により証明せよ．
ことを数学的帰納法により証明せよ．
復習問題 13.2 任意の正の整数 n に対して
追加問題 13.8 3 以上の任意の正の整数 n に対して
2n ≤ 2n
3n2 ≤ 3n
となることを数学的帰納法により証明せよ．
となることを数学的帰納法により証明せよ．(ヒント：
復習問題 13.3 3 以上の任意の正の整数 n に対して
問題 13.3 の結果を用いてもよい．)
6n ≤ 3n
追加問題 13.9 任意の正の整数 n に対して，Cn を
次のように定義する

1
Cn = 4n − 2

Cn−1
n+1
となることを数学的帰納法により証明せよ．
復習問題 13.4 任意の正の整数 n に対して，an を

1
(n = 1 のとき)
an =
a
+ 2 (n > 1 のとき)
(n = 1 のとき)
(n > 1 のとき).
このとき，任意の正の整数 n に対して，
n−1
と定義する．このとき，任意の正の整数 n に対して，
an = 2n − 1
Cn =
(2n)!
n!(n + 1)!
となることを証明せよ．(補足：Cn はカタラン数と
となることを証明せよ．
呼ばれ，よく研究されているものである．)
復習問題 13.5 任意の正の整数 n に対して，第 n 番
追加問題 13.10 任意の正の整数 n に対して，an を


1
(n = 1 のとき)


an = 3
(n = 2 のとき)



3a
n−1 − 2an−2 (n > 2 のとき)
フィボナッチ数 Fn を



1


Fn = 1



F
n−1 + Fn−2
(n = 1 のとき)
(n = 2 のとき)
(n > 2 のとき)
で定義する．任意の正整数 n に対して
で定義する．任意の正整数 n に対して
an = 2n − 1
2
Fn+1
− Fn+2 Fn = (−1)n
が成り立つことを証明せよ．
が成り立つことを証明せよ．
復習問題 13.6 第 n 番フィボナッチ数を Fn とする
追加問題 (発展) 13.11 第 n 番フィボナッチ数を Fn
とき，任意の正の整数 n に対して，
((
√ )n (
√ )n )
1+ 5
1− 5
1
−
Fn = √
2
2
5
とするとき，任意の正の整数 n に対して，
2
2
F2n+1 = Fn+1
+ Fn2 および F2n+2 = Fn+2
− Fn2
が成り立つことを証明せよ．
が成り立つことを証明せよ．
1
追加問題 (発展) 13.12 2 以上の任意の整数 n に対
して，次が正しいことを証明したい．
平面上で，どの 2 つも平行でないような
任意の n 個の直線 `1 , `2 , . . . , `n はある 1
点で交わる．
次の数学的帰納法による証明は正しく見えるが，こ
の命題自体は正しくない．すなわち，証明には誤り
がある．証明の誤りを見つけ，指摘せよ．
数学的帰納法により証明を行う．
[基底段階] n = 2 のとき，平行でない 2
つの直線は必ず 1 点で交わるので，命題
は正しい．
[帰納段階] n = k ≥ 2 のとき，この命題
が正しいと仮定する．証明すべきことは，
平面上で，どの 2 つも平行でないような
任意の k + 1 個の直線 `1 , `2 , . . . , `k+1 が
ある 1 点で交わることである．
`1 , `2 , . . . , `k を考えると，帰納法の仮定
から，これらはある 1 点で交わる．その
交点を p とする．
また，`1 , `2 , . . . , `k−1 , `k+1 を考えると，
帰納法の仮定から，これらはある 1 点で
交わる．その交点を q とする．
ここで，p も q も `1 と `2 の交点であり，
平行でない 2 直線は 1 点でしか交わらな
いので，p = q である．
すなわち，`1 , `2 , . . . , `k+1 は 1 点 p を共
有する．
2

Download Report