care sta la baza relatiei:
p(pre).

    [I{~0~}]   [I{~N  ~}]

    [I{~0~}]    [I{~N  ~}]

M * [I{~1~}] = [I{~N+1~}]

    [I{~2~}]   [I{~N+2~}]

    [I{~2~}]    [I{~N+2~}]

Din asta se deduce:
p(pre).

     [I{~0~}]   [I{~N  ~}]

     [I{~0~}]    [I{~N  ~}]

M^N^ * [I{~1~}] = [I{~N+1~}]

     [I{~2~}]   [I{~N+2~}]

     [I{~2~}]    [I{~N+2~}]

astfel problema se reduce la a calcula $M^N^$ in {$O(lg N)$}. Algoritmul de ridicare la putere in timp logaritmic este clasic si nu-l mai mentionez aici.