は でを満たす。の値を固定したとき満たす関数がただ1つ存在することを示せ。
を満たす全ての関数の集合をとする。また
を満たす全ての関数の集合をとする。
以下の補題を示す。
補題1
においての値を固定したとき満たす関数がただ1つ存在する。
は奇数ならに,偶数ならにとすることでより小さい関数の値で表せるので(の中身が負になったときはを用いる)帰納的にはのみで表せる。のときは明らかでの時はより上のように表せることが従う。逆にその関数がを満たすことを示す。
はとで同値であり、は明らかだから正のときを考える。
においてのときはすぐ従う。のときはの値を求めるときに用いたので満たすことはすぐに分かる。
において負の整数の関数の値を求めるときに用いたので満たすことはすぐに分かる。よって示せた。
を示せば補題1より題意を示したことになる。それを示すためいくつかの補題を示す。
その前に、
と定める。
以下はすぐに分かる。
が共に偶数であるとき
まずとが同値であることを示す。
よって示せた。
のときは明らかだからのとき補題が成り立つことを示す。すなわち、
を示す。
(左辺)
(右辺)
よって(左辺)(右辺)が示せた。
以上より補題が示せた。
補題2.1より
両辺差を取り、(5)を用いることで補題の式を得る。
とが同値でありも成り立つのでが正のときを考えればよい。についても同様。を固定する。
が成り立つとき任意の正の整数で成り立つことを帰納的に示す。そのとき先程の議論よりでも成り立つ。
が成り立つと仮定してが成り立つことを示す。
帰納法の仮定
よって示せた。
あとはを示せば良い。
をしらみ潰しに示して、が従い、は対称であるからである場合も示せた。
以上より補題が示せた。
が正のときのみで良い。
のときは明らか。
のときは補題2,補題3.1より、
それ以外の場合は帰納法で示す。
のとき成り立つと仮定してのときを示す。が偶数のときは補題3.2でのときを用いればすぐに従う。奇数のときを考える。とする。であることに注意する。
補題3.3より
であるから帰納法の仮定を用いることで
これらとから、
が従う。
よって示せた。
補題4.1
を満たすにおいてが存在して
でまたはとなる。逆にそれらはを満たす。
からが共に偶数またはが共に偶数である。の対称性よりが共に偶数であるときのみ考えれば良い。
この比を互いに素な整数でとしたときが存在して、
と表せる。より共に偶数またはが共に偶数であるがは互いに素であるからが共に偶数。
としについて解くと
を得る。それらがを満たすことはすぐに分かる。
であることはすぐ分かる。
補題4.1よりの条件は
と同値であるから補題4.2よりも得る。よって
補題1,補題4より題意は示された。