与えられた漸化式を以下のように変形してみましょう。
Ei=Ei−1+∑1≤k≤i−1EkE_i = E_{i-1} + \displaystyle \sum_{1 \leq k \leq i - 1} E_kEi=Ei−1+1≤k≤i−1∑Ek
Ei=Ei−1+(Ei−1−Ei−2+Ei−1)E_i = E_{i-1} + (E_{i - 1} - E_{i - 2} + E_{i - 1)}Ei=Ei−1+(Ei−1−Ei−2+Ei−1)
Ei=3Ei−1−Ei−2E_i = 3 E_{i - 1} - E_{i - 2}Ei=3Ei−1−Ei−2
よって、漸化式は 333 項間漸化式に帰着され、行列累乗などを用いることによって高速に第 NNN 項の値を求めることができます。
