2022.03.08記
漸化式で定まる整数に値をとる数列の余りは途中から周期をもつが,特に漸化式をうまく逆に辿ることができるなら,その周期は初項から始まる。
で
となることは普通に使う訳だが,それを示せという問題.
[解答]
(1) 漸化式から は正の整数をとる数列であることが帰納的に言えるので,任意の正の整数 に対して
() をみたす正または0の整数をとる数列 が一意に定まる.
このとき,漸化式より
つまり
が成立するので,登場する文字が全て整数であることに注意すると
は の倍数となり,よって と を で割った余りは等しい.
(2) なる最小の自然数の組 () が存在すると,(1) により が成立するので帰納的に,任意の自然数 について が成立することになるので,数列 は第項以降は周期 で繰り返す数列になる.
のとき,,,, であるから,数列 は第項以降は周期 で繰り返す数列になる.
よって,,, となる.
(3) で割った余りが等しいことを「」で結ぶこととする.
() なる自然数の組 () が存在するとき,
となるが,, より となる.
(4) の組み合わせは高々 通りであるから,ディリクレの部屋割り論法により
から までの 組の中には
()
なる自然数の組 が存在する.そして題意から 以上の全ての自然数 に対して だから,
()
において(3)を 回繰り返すと
()
が成立する.ここで により であるから, が言え,よって も では割り切れない.