問題
不思議な性質を説明する前にまずこの問題を愚直に解いてみる。
この漸化式の特性方程式が であるので
とし、とするとかつ
よって
となる。
と置くと
となる。
であり、であるから
これを使うと
簡単な計算でを得るから
よって求める値はである。
これでも十分良問だがもっとこの問題について掘り下げていく。実はになったのはたまたまではない。上の数列を含むある数列は以下のような性質がある。
性質
を数列が満たすならば
を満たす任意の整数において
が成り立つ。
確かに上の具体例はこれを満たしている。先ほどの上の解答からを機械的に計算できるのでとんでもない数の場合分けを行えば上の性質を証明できそうではあるが別の方法で示す。厳密に証明を書くと長くなって(面倒くさいので)しまうので簡単に証明のプロセスを下に書く。
証明
はすぐに従うので省略。
上についてもを用いればすぐに証明できる。以降、でが負のときはが解決してくれるので非負のときのみ考える。
証明
と変形できるのでについての帰納法からのみを示せば良いが、は対称的であるからを示せば良く、同じ議論からを示せば良くこれは有限回の計算で示せる。(が負のときはから非負のときに帰着できる。)
証明
の式にとすることでの等式を得る。以降、についての帰納法で示す。
・のとき
より成り立つ。ただし、最後の変形は帰納法の仮定を用いた。
・のとき
の式にとすると
とを入れ替えて
の帰納法の仮定を用いることでを得る。(が負のときはから非負のときに帰着できる。)
証明
であり
任意のに対してあるが存在してが成り立つのが示せるのでそれを用いれば示したいものが示せる。