計算機科学のブログ

帰納的定義と証明技法 整数の平方、偶数、必要十分条件、奇数、3つの偶数の和、背理法

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第3章(帰納的定義と証明技法)、章末問題の問3.3、3.4の解答を求めてみる。

3.3

n 2

が偶数とする。

nが奇数と仮定すると、ある整数kが存在して、

n = 2 k + 1

とおくことができる。

このとき、

n 2 = ( 2 k + 1 ) 2 = 4 k 2 + 4 k + 1 = 2 ( 2 k 2 + 2 k ) + 1

となり、これは奇数である。 よって矛盾。

ゆえに、

n 2

が偶数ならば、 nは偶数である。

逆について。

nが偶数ならば、ある整数kが存在して、

n = 2 k

このとき、

n 2 = ( 2 k ) 2 = 2 ( 2 k 2 )

よって、

n 2

は偶数である。

（証明終）

3.4

aを任意の奇数とする。

aが ある3つの偶数

b , c , d ∈ ℤ 2 b , 2 c , 2 d

の和によって表すことができると仮定すると、

a = 2 b + 2 c + 2 d = 2 ( b + c + d )

となり、 aは偶数である。

よって矛盾。

ゆえに、奇数は3つの偶数の和によって表すことができない。