เลขฟีโบนัชชีและการพิสูจน์อุปนัยแบบพร้อมเพรียงกัน
ลำดับฟีโบนัชชีนั้น แม้จะนิยามขึ้นมาจากความสัมพันธ์เวียนเกิดง่ายๆ $F_n = F_{n-1} + F_{n-2}$ และจุดเริ่มต้นที่ $F_1 = F_2 = 1$ แต่ก็ทำให้เกิดเอกลักษณ์อันสวยงามต่างๆ มากมาย เช่น $\sum_{i=1}^n F_i = F_{n+2} - 1$ การพิสูจน์เอกลักษณ์เหล่านี้สามารถทำได้โดยง่ายผ่านการอุปนัยเชิงคณิตศาสตร์
แต่ก็ยังมีเอกลักษณ์บางอย่างที่ดูแล้วไม่น่าเป็นไปได้ที่จะพิสูจน์ด้วยเทคนิคข้างต้น เช่น
\[F_n^2 + F_{n-1}^2 = F_{2n-1}\]หรือเอกลักษณ์ที่คล้ายๆ กันอย่าง
\[F_{n+1}F_n + F_nF_{n-1} = F_{2n}\]ถึงแม้เราสามารถสังเกตจากการทดลองได้ว่า สมการข้างต้นเป็นจริงเมื่อ $n$ มีค่าน้อยๆ ก็ตามที แต่หากยังไม่ได้พิสูจน์ เราจะแน่ใจได้อย่างไรว่าสมการข้างต้นจะเป็นจริงสำหรับ $n$ ใดๆ?
เทคนิคที่จะนำมาใช้พิสูจน์สมการข้างต้น ทำได้โดยการขยายขีดความสามารถของการอุปนัยขึ้นไป กล่าวคือแทนที่เราจะพิสูจน์ให้เห็นว่าเป็นจริงทีละสมการ ก็เปลี่ยนมาพิสูจน์ทั้งสองสมการพร้อมกันไปเลย ซึ่งทำได้ดังนี้
ก่อนอื่น ให้ $P(n)$ แทนค่าความจริงของสมการ $F_n^2 + F_{n-1}^2 = F_{2n-1}$ และในทำนองเดียวกัน ให้ $Q(n)$ แทนค่าความจริงของสมการ $F_{n+1}F_n + F_nF_{n-1} = F_{2n}$
สังเกตได้ไม่ยากว่า $P(2)$ และ $Q(2)$ เป็นจริง
ขั้นต่อไป สมมติให้ $P(k)$ และ $Q(k)$ เป็นจริง สิ่งที่เราต้องการคือแสดงให้เห็นว่า $P(k+1)$ และ $Q(k+1)$ เป็นจริงด้วย
เริ่มจากฝั่ง $P(k+1)$ ก่อน จะเห็นว่า
\[\begin{align*} F_{k+1}^2 + F_k^2 &= (F_k + F_{k-1})^2 + F_k^2 \\ &= (F_k^2 + 2F_kF_{k-1} + F_{k-1}^2) + F_k^2 \\ &= (F_k^2 + F_{k-1}^2) + 2F_kF_{k-1} + F_k^2 \\ &= (F_k^2 + F_{k-1}^2) + F_kF_{k-1} + F_kF_{k-1} + F_k^2 \\ &= (F_k^2 + F_{k-1}^2) + F_kF_{k-1} + F_k(F_{k-1} + F_k) \\ &= \underbrace{(F_k^2 + F_{k-1}^2)}_{\text{induction}} + \underbrace{F_kF_{k-1} + F_kF_{k+1}}_{\text{mutual equation}} \\ &= F_{2k-1} + F_{2k} \\ &= F_{2k+1} \end{align*}\]และแน่นอนว่าฝั่ง $Q(k+1)$ ก็สามารถถูกพิสูจน์ได้ในทำนองเดียวกัน
\[\begin{align*} F_{k+2}F_{k+1} + F_{k+1}F_k &= (F_{k+1} + F_k)F_{k+1} + (F_k + F_{k-1})F_k \\ &= (F_{k+1}^2 + F_kF_{k+1}) + (F_k^2 + F_{k-1}F_k) \\ &= \underbrace{(F_{k+1}^2 + F_k^2)}_{\text{mutual equation}} + \underbrace{(F_kF_{k+1} + F_{k-1}F_k)}_{\text{induction}} \\ &= F_{2k+1} + F_{2k} \\ &= F_{2k+2} \end{align*}\]เราอาจเรียกเทคนิคนี้ว่าเป็นการพิสูจน์โดยอุปนัยแบบพร้อมเพรียงกัน (simultaneous induction)
แผนภาพแนวคิดการพิสูจน์โดยอุปนัยแบบพร้อมเพรียงกัน
ความเจ๋งของเอกลักษณ์ทั้ง 2 สมการข้างต้นนี้ คือมันช่วยให้เราได้อัลกอริทึมคำนวณค่าฟีโบนัชชีที่ตำแหน่ง $n$ ภายในเวลา $O(\log n)$ ซึ่งสังเกตได้จากการที่ฝั่งขวาของทั้งสองสมการนั้น ตำแหน่งฟีโบนัชชีจะมีค่าเป็นสองเท่าของตำแหน่งฟีโบนัชชีทางซ้ายมือของสมการ ทำให้เราสามารถกระโดดข้ามการคำนวณค่าฟีโบนัชชีในตำแหน่งที่ไม่จำเป็นได้เป็นจำนวนมาก
ส่วนการนำไปใช้งานจริงนั้น เราอาจจัดรูปเอกลักษณ์ในกรณีเลขคู่ให้กลายเป็น $F_n(2F_{n+1} - F_n) = F_{2n}$ เสียก่อน เพื่อลดจำนวนพจน์ฟีโบนัชชีที่แตกต่างกันลง (จากเดิมต้องรู้ทั้ง $F_{n-1}, F_n, F_{n+1}$) อัลกอริทึมที่คำนวณค่าฟีโบนัชชีด้วยวิธีนี้มีชื่อว่า fast doubling ซึ่งสามารถเขียนเป็นโค้ดได้ดังนี้
def fibonacci(n):
if n in {1, 2}:
return 1
elif n % 2 == 0:
f0 = fibonacci(n//2)
f1 = fibonacci(n//2+1)
return f0 * (2*f1 - f0)
else:
f0 = fibonacci(n//2 + 1)
f1 = fibonacci(n//2)
return f0**2 + f1**2
หมายเหตุ
บล็อกตอนนี้อาจถือได้ว่าเป็นตอนต่อของการคำนวณค่าฟิโบนัชชีด้วยเมทริกซ์ ซึ่งเราสามารถมาถึงข้อสรุปของเอกลักษณ์ข้างต้นได้เช่นกัน ผ่านการแก้สมการเมทริกซ์จากตอนที่แล้วต่อดังนี้
\[\begin{align*} \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{2n} &= \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n \\ &= \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} \end{bmatrix} \\ \begin{bmatrix} F_{2n+1} & F_{2n} \\ F_{2n} & F_{2n-1} \end{bmatrix} &= \begin{bmatrix} F_{n+1}^2 + F_n^2 & F_{n+1}F_n + F_nF_{n-1} \\ F_nF_{n+1} + F_{n-1}F_n & F_n^2 + F_{n-1}^2 \end{bmatrix} \end{align*}\]อ้างอิง
- Lovász, L., Pelikán, J. and Vesztergombi, K., 2003. Discrete mathematics, Undergraduate Texts in Mathematics.
author