例えば、次のような斉次線形漸化式 an+2 - 5an+1 + 6an = 0 には、次の方程式が対応しています。 x2 - 5x + 6 = 0 なぜなら、上の漸化式を次の形にしようとすると、 an+2 - αan+1 = β(an+1 - αan) これを展開して、 an+2 - (α + β)an+1 + αβan = 0 だから、 …

Problem 15 2×2の格子の左上をスタートし、右下へ行くルート（後戻りはなし）は6つある。 20×20の格子では何通りのルートがあるだろう。 http://projecteuler.net/index.php?section=problems&id=15 40ステップのうち、20ステップが右で、20ステップが下なら…

ということにしておこう。

バイナリ法（英語には同等の用語は無いらしい）は、べき乗を高速に求める方法です。実際には乗算以外にも色々使えるので、必ず覚えておきましょう。 例えば、3の8乗を求めるとき、 6561 = 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 とすると7回の乗算が必要ですが、 9 …