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

ข้อย่อย 1

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

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

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

ฉะนั้นเราจึงสามารถสรุปได้ว่าข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับจำนวนเต็มบวก $n\,$ ทุกจำนวน

ข้อย่อย 2

จากข้อย่อย 1 เราสามารถคำนวณ $f_{n}$ ได้ด้วยการคำนวณ ${\begin{matrix}1&1\\1&0\end{matrix}}^{n}$ ซึ่งเราสามารถใช้อัลกอริทึีมได้ เพียงแต่เปลี่ยนการคูณจำนวนเต็มเป็นการคูณเมตริกซ์เท่านั้น เนื่องจากการคูณเมตริกซ์ขนาด 2 x 2 สามารถทำได้ใน $O(1)\,$ เราจึงได้ว่าเราสามารถคำนวณ $f_{n}\,$ ได้ในเวลา $O(\log n)\,$