概要 項間の線形漸化式を持つ数列の第 項から 項までを の時間計算量で計算するアルゴリズムを説明する。 繰り返し二乗法と多項式の余り付き除算を用いる方法と比べると、定数倍が良いと思われる。 問題設定 が を満たすとする。 この記事内で多項式の除算を…

と定義する。 は中心二項係数と呼ばれていて、 である。これは天下りに与えられたものをテイラー展開で確認する以外の導出方法を知らない。 パスカルの三角形を思い浮かべると、 を つ足し合わせて が作れることに気付く。すなわち であり、ここから である…