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

ข้อย่อย 1

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

(Base Case) ในกรณีนี้ $n=1\,$ ซึ่งเราจะได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 304223074
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Wed, 25 Feb 2026 08:59:28 GMT


Sensitive client information

IP address: 158.108.32.49

${\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) สมมติให้ สำหรับ บางตัว เราได้ว่า