広島大学 2022年度理系数学第3問解答・解説

問題

$a,$ $b$ を整数とする．また，整数の数列 ${c_{n}}$ を $c_{1} = a,$ $c_{2} = b$ および漸化式 $c_{n + 2} = c_{n + 1} + c_{n}$ （ $n = 1 ， 2 ， 3 ， \dots$ ）により定める．このとき，次の問いに答えよ．(1)　 $a = 39,$ $b = 13$ とする．このとき，二つの整数 $c_{5}$ と $c_{6}$ の最大公約数を求めよ．(2)　 $a$ と $b$ はともに奇数であるとする．このとき，自然数 $n$ に対して次の命題 $P_{n}$ が成り立つことを， $n$ についての数学的帰納法で示せ． $P_{n}$ ： $c_{3 n - 2}$ と $c_{3 n - 1}$ はともに奇数であり， $c_{3 n}$ は偶数である．(3)　 $d$ を自然数とし， $a$ と $b$ はともに $d$ の倍数であるとする．このとき，自然数 $n$ に対して $c_{n}$ が $d$ の倍数になることを示せ．ただし，数学的帰納法を用いて証明すること．(4)　 $c_{2022}$ が奇数であるならば， $a + b$ も奇数であることを示せ．

出典：広島大学 2022年度前期理系第3問

方針

解法1（指定通り帰納法と対偶を使う方法）

漸化式から初めの項を計算する。(2)(3)は指定通り数学的帰納法で示す。(4)は対偶を用い， $a + b$ が偶数なら両方奇数または両方偶数であることから(2)(3)を使う。

解法2（漸化式を法2で調べる方法）

最大公約数はユークリッドの互除法で求める。偶奇については $c_{n + 3} = c_{n} + 2 c_{n + 1}$ から $c_{n + 3} \equiv c_{n} (mod 2)$ を導き、3項周期を明らかにする。(2)(3)では指定通り帰納法も明記する。

解答

解法1（指定通り帰納法と対偶を使う方法）

(1)

c_{3} = 52, c_{4} = 65, c_{5} = 117, c_{6} = 182

である。したがって

182 - 117 = 65, 117 - 65 = 52, 65 - 52 = 13

より， $c_{5}$ と $c_{6}$ の最大公約数は

13

である。

(2)

$n = 1$ のとき， $c_{1} = a, c_{2} = b$ は奇数であり，

c_{3} = a + b

は偶数である。よって $P_{1}$ は成り立つ。

$P_{n}$ が成り立つと仮定する。このとき

c_{3 n - 2}, c_{3 n - 1} は奇数, c_{3 n} は偶数

である。漸化式より

c_{3 n + 1} = c_{3 n} + c_{3 n - 1}

は奇数，

c_{3 n + 2} = c_{3 n + 1} + c_{3 n}

も奇数，

c_{3 n + 3} = c_{3 n + 2} + c_{3 n + 1}

は偶数である。したがって $P_{n + 1}$ も成り立つ。よって数学的帰納法により，すべての自然数 $n$ について $P_{n}$ は成り立つ。

(3)

$n = 1, 2$ のとき，仮定より $c_{1} = a, c_{2} = b$ はいずれも $d$ の倍数である。

$c_{n}$ と $c_{n + 1}$ がともに $d$ の倍数であると仮定すると，

c_{n + 2} = c_{n + 1} + c_{n}

も $d$ の倍数である。したがって数学的帰納法により，すべての自然数 $n$ について $c_{n}$ は $d$ の倍数である。

(4)

対偶を示す。すなわち， $a + b$ が偶数であるとき $c_{2022}$ が偶数であることを示せばよい。

$a + b$ が偶数なら， $a, b$ はともに奇数であるか，ともに偶数である。ともに奇数である場合，(2)より $c_{3 n}$ は偶数である。 $2022 = 3 \cdot 674$ であるから， $c_{2022}$ は偶数である。ともに偶数である場合，(3)を $d = 2$ として用いれば，すべての $c_{n}$ は偶数であり，特に $c_{2022}$ は偶数である。

よって対偶が示されたので， $c_{2022}$ が奇数であるならば $a + b$ は奇数である。

解法2（漸化式を法2で調べる方法）

(1)

c_{3} = 52, c_{4} = 65, c_{5} = 117, c_{6} = 182.

ユークリッドの互除法により

g cd (182, 117) = g cd (117, 65) = g cd (65, 52) = g cd (52, 13) = 13.

(2)

漸化式を2回用いると

c_{n + 3} = c_{n + 2} + c_{n + 1} = c_{n} + 2 c_{n + 1},

したがって

c_{n + 3} \equiv c_{n} (mod 2) .

$a, b$ が奇数なら、最初の3項の偶奇は

c_{1} \equiv 1, c_{2} \equiv 1, c_{3} = a + b \equiv 0 (mod 2) .

そこで $P_{n}$ を「 $c_{3 n - 2}, c_{3 n - 1}$ は奇数、 $c_{3 n}$ は偶数」とする。上の合同式により $P_{n}$ から3項後も同じ偶奇となるので $P_{n + 1}$ が従う。 $P_{1}$ も上で確認したから、数学的帰納法によりすべての自然数 $n$ で $P_{n}$ が成り立つ。

(3)

$d ∣ a$ かつ $d ∣ b$ とする。 $c_{1}, c_{2}$ は $d$ の倍数である。連続する $c_{n}, c_{n + 1}$ がともに $d$ の倍数なら

c_{n + 2} = c_{n + 1} + c_{n}

も $d$ の倍数である。よって数学的帰納法により、すべての $c_{n}$ は $d$ の倍数である。

(4)

$2022 \equiv 0 (mod 3)$ だから、3項周期より

c_{2022} \equiv c_{3} \equiv a + b (mod 2) .

したがって $c_{2022}$ が奇数なら $a + b$ も奇数である。

広島大学 2022年度理系数学 第3問

問題

方針

解法1（指定通り帰納法と対偶を使う方法）

解法2（漸化式を法2で調べる方法）

解答

解法1（指定通り帰納法と対偶を使う方法）

(1)

(2)

(3)

(4)

解法2（漸化式を法2で調べる方法）

(1)

(2)

(3)

(4)

広島大学 2022年度
理系数学第3問