広島大学(理系) 2022年 問題3
$a,\ b\ を整数とする。また、整数の数列 \ \{c_n\}\ を \ c_1=a,\ c_2=b\ および漸化式 \ \ c_{n+2}=c_{n+1}+c_n\ \ (n=1,\ 2,\ 3,\ \cdots)$
$により定める。このとき、次の問いに答えよ。$
$(1)\ \ a=39,\ b=13\ とする。このとき、二つの整数 \ c_5\ と \ c_6\ の最大公約数を求めよ。$
$(2)\ \ a\ と \ b\ はともに奇数であるとする。このとき、自然数 \ n\ に対して次の命題 \ P_n \ が成り立つことを、$
$\quad n\ についての数学的帰納法で示せ。$
$\qquad P_n: c_{3n-2}\ と \ c_{3n-1}\ はともに奇数であり、c_{3n}\ は偶数である。$
$(3)\ \ d\ を自然数とし、a\ と \ b\ はともに \ d\ の倍数であるとする。このとき、自然数 \ n\ に対して \ c_n \ が \ d\ の$
$\quad 倍数になることを示せ。ただし、数学的帰納法を用いて証明すること。$
$(4)\ \ c_{2022}\ が奇数であるならば、a+b\ も奇数であることを示せ。$
$(解説)$
$(1)\ \ 漸化式をつかって、c_5,\ c_6\ を求めます。2\ 数の最大公約数の性質をつかう方法もあります。$
$(2)\ \ ごく普通の数学的帰納法で示します。$
$(3)\ \ n=k-1,\ n=k \ が成り立つとして \ n=k+1\ のときも成り立つという数学的帰納法をつかいます。$
$(4)\ \ 2022\ は \ 3\ の倍数だから、a_{3n}\ が奇数ならば \ a_{3n-3}\ も奇数であることを示しておきます。$
(1)
$c_1=39,\quad c_2=13 \quad より$
$c_3=c_2+c_1=13+39=52$
$c_4=c_3+c_2=52+13=65$
$c_5=c_4+c_3=65+52=117=13 \times 9$
$c_6=c_5+c_4=117+65=182=13 \times 14$
$よって \quad c_5=13 \times 9 \quad c_6=13 \times 14 \quad で \ \ 9\ と \ 14\ は互いに素だから最大公約数は \ \ 13$
$(別解)$
$a\ と \ b\ の最大公約数を \ (a,\ b)\ と表すことにすると 任意の整数 \ k\ について \quad (a,\ ka+b)=(a,\ b)\ \ がなりたつから$
$\quad （このことについては($最大公約数の性質$)をご覧ください。）$
$この性質をつかって \quad (c_n,\ c_{n+1})=(c_n,\ c_n+c_{n-1})=(c_n,\ c_{n-1})$
$よって \quad (c_{n-1},\ c_n)=(c_n,\ c_{n+1})$
$n \longrightarrow n+1 \quad とおくと \quad (c_n,\ c_{n+1})=(c_{n+1},\ c_{n+2})$
$このように、この漸化式で定まる連続する \ 2\ 項の最大公約数は保存されることがわかります。$
$したがって \quad (c_1,\ c_2)=(c_2,\ c_3)=(c_3,\ c_4)=(c_4,\ c_5)=(c_5,\ c_6) \quad です。$
(2)
(i)$\ \ n=1 \quad のとき$
$\qquad c_1=a,\ c_2=b \ はともに奇数だから、c_3=c_2+c_1\ は偶数である。よって \quad n=1\ のとき成り立つ。$
(ii)$\ \ n=k\ のとき成り立つとすると$
$\qquad P_k: c_{3k-2}\ と \ c_{3k-1}\ はともに奇数であり、c_{3k}\ は偶数である。$
$\quad このとき$
$\qquad c_{3(k+1)-2}=c_{3k+1}=c_{3k}+c_{3k-1} \quad は \ \ 偶数+奇数 \ \ だから \ \ 奇数$
$\qquad c_{3(k+1)-1}=c_{3k+2}=c_{3k+1}+c_{3k} \quad は \ \ 奇数+偶数 \ \ だから \ \ 奇数$
$\qquad c_{3(k+1)}=c_{3k+3}=c_{3k+2}+c_{3k+1}\ \ は \ \ 奇数+奇数 \ \ だから \ \ 偶数$
$\quad よって \quad n=k+1\ \ のときも成り立つ。$
(i),(ii)$\ \ より すべての自然数 \ n\ に対して命題 \ P_n \ が成り立つ。$
(3)
$a\ と \ b\ はともに \ d\ の倍数のとき$
$\quad 命題 \ : c_n\ は \ d\ の倍数$
(i)$\ \ a\ と \ b\ はともに \ d\ の倍数より \quad c_1=a,\ c_2=b \quad だから \quad n=1,\ \ n=2\ \ のとき成り立つ。$
(ii)$\ \ n=k-1,\ \ n=k \ \ のとき成り立つとすると$
$\qquad c_{k-1},\ \ c_k \ \ はともに \ d\ の倍数だから \quad c_{k-1}=dp,\ \ c_k=dq \ \ (p,\ q\ は整数)\ \ とおける。$
$\quad このとき$
$\qquad c_{k+1}=c_k+c_{k-1}=dq+dp=d(q+p) \quad より \quad c_{k+1}\ \ は \ d\ の倍数$
$\qquad よって \quad n=k+1\ \ のときも成り立つ。$
(i),(ii)$\ \ よりすべての自然数 \ n\ に対して \ c_n \ は \ d\ の倍数になる。$
$\quad なお、この証明方法については($数学的帰納法による証明$)をご覧ください。$
(4)
$まず、c_{3n}\ が奇数ならば \ \ c_{3n-3}\ も奇数であることを証明します。$
$c_{3n}\ \ が奇数ならば \quad c_{3n}=c_{3n-1}+c_{3n-2} \quad より次の \ 2\ 通りの場合がある。$
(i)$\ \ c_{3n-1}\ \ は奇数でかつ \ \ c_{3n-2}\ \ は偶数の場合$
$\qquad c_{3n-1}=c_{3n-2}+c_{3n-3} \quad より \quad c_{3n-3}=c_{3n-1}-c_{3n-2} \quad だから$
$\qquad c_{3n-3}\ \ は \ \ 奇数-偶数 \ \ だから\ \ 奇数 $
(ii)$\ \ c_{3n-1}\ \ は偶数でかつ \ \ c_{3n-2}\ \ は奇数の場合$
$\qquad c_{3n-3}=c_{3n-1}-c_{3n-2}\ \ は \ \ 偶数-奇数 \ \ だから \ \ 奇数 $
(i),(ii)$より \quad c_{3n}\ \ が奇数ならば \ \ c_{3n-3}\ \ も奇数である。$
$2022=3 \times 674 \quad は \ 3\ の倍数だから、c_{2022}\ \ が奇数ならば \ \ c_{2019}\ \ は奇数である。$
$これを繰り返して \qquad c_{2016},\ \ c_{2013},\ \ \cdots ,\ \ c_3\ \ は奇数である。$
$c_3=c_2+c_1=b+a \quad だから \quad a+b\ \ は \ \ 奇数である。$
メインメニュー に戻る