418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 6

ข้อย่อย 1

เราจะพิสูจน์ข้อความนี้ด้วย induction

(Base Case) ในกรณีนี้ $n=1\,$ ซึ่งเราจะได้ว่า ${\begin{bmatrix}1&1\\0&1\end{bmatrix}}^{1}={\begin{bmatrix}1&1\\0&1\end{bmatrix}}={\begin{bmatrix}f_{1}&f_{2}\\0&f_{1}\end{bmatrix}}\,$

(Induction Case) สมมติให้ ${\begin{bmatrix}1&1\\0&1\end{bmatrix}}^{n}={\begin{bmatrix}f_{n}&f_{n+1}\\0&f_{n}\end{bmatrix}}$ สำหรับ $n\geq 1\,$ บางตัว เราได้ว่า