東京大学 後期 1994年 第1問 (解答解説)

【解答】

(1)

数学的帰納法で

を示す．

まずのとき，(式2)の左辺は

であり，(式2)の右辺は

だから両辺ともにで(式2)は成立する．

そこででの成立を仮定してでの成立を示す． (式2)の左辺は

より，でも成立する．

以上から，数学的帰納法により(式2)が示された．

(答)

(2)

表現の簡潔さのため

と置く．

題意を示すには，任意のについて以下の二点を証明すれば良い．

1. a　が以上以下の全ての整数を表すことが出来る

2. b　異なるが同じ値をとることはない

まずは(a)を数学的帰納法により示す． の時は

であり，題意は成立する．

そこででの成立を仮定し，での成立を示す．

と書ける．また，題意よりである． 仮定よりは

なる全ての整数を取るから，と動かすと

なる全ての整数をとる．従って(式10)は

である． とを動かすと

となり，

なる全ての整数をとる．よってでも(a)は成立する．

以上から，数学的帰納法により(a)の成立が示された．

そこで次に(b)について考える．(a)が成立することから，異なるに対して

となる．よってが同じ時に同一の値を与えるがないことを示せば良い． 証明は背理法による．異なるに対して，が同一の値となると仮定する．

ここで，より，第二項目以降は

だから，の時には第一項目より大きくなることはなく等式が成立しない． よってであることが必要である． 以下同様の議論を繰り返せば，となるが，これは当初の仮定に反する． 以上より背理法によって(b)が示された．

従って(a)，(b)が成立し，題意は示された．(答)

(3)

をで割ったあまりによって場合分けする． そこでとする．

\textbf{の時}

この時はが自然数でより小さいから，

である．

\textbf{の時}

この時はが自然数で，かつより小さいから，

である．

\textbf{の時}

をで表して変形すると

である．

\textbf{の時}

をで表して変形すると

である．

\textbf{の時}

をで表して変形すると

である．

以上で全ての場合が尽くされ，いずれの場合も表示が可能であることが示された． 結果をまとめると，法をとする合同式を用いて

である．(答)

【解説】