フィボナッチの数畑〜解答
まず、一桁フィボナッチ数列同士の和(繰り上がりは無視する)はやはり一桁フィボナッチ数列である事を証明する。 二つの一桁フィボナッチ数列
an: an+2 = (an + an+1) mod 10
bn: bn+2 = (bn + bn+1) mod 10
が与えられたとする。("x mod 10" は、xを10で割った余りを示す)
数列cnを、
cn = (an + bn) mod 10
とすると、
cn+2 = (an+2 + bn+2) mod 10
= ((an + an+1) mod 10 + (bn + bn+1) mod 10) mod 10
= (an + an+1 + bn + bn+1) mod 10
= (cn + cn+1) mod 10
となり、cnは一桁フィボナッチ数列である。
フィボナッチの数畑の n+2 行目の数列は、n 行目の数列と n+1 行目の数列の和として表されるので、 n 行目と n+1 行目の数列が一桁フィボナッチ数列であれば、n+2 行目の数列もまたフィボナッチ数列である。 1行目と2行目の数列は種から展開された一桁フィボナッチ数列であるので、 数畑の全ての行の数列は一桁フィボナッチ数列となる。
なお、上記の式から "mod 10" を取り除いても式が成立する事からわかるとおり、 この事実は通常のフィボナッチ数列についてもあてはまる。