neizod's speculation

insufficient data for meaningful answer

เลขฟีโบนัชชีและการพิสูจน์อุปนัยแบบพร้อมเพรียงกัน

Thursday, August 23, 2018, 08:11 AM

ลำดับฟีโบนัชชีนั้น แม้จะนิยามขึ้นมาจากความสัมพันธ์เวียนเกิดง่ายๆ $F_n = F_{n-1} + F_{n-2}$ และจุดเริ่มต้นที่ $F_1 = F_2 = 1$ แต่ก็ทำให้เกิดเอกลักษณ์อันสวยงามต่างๆ มากมาย เช่น $\sum_{i=1}^n F_i = F_{n+2} - 1$ การพิสูจน์เอกลักษณ์เหล่านี้สามารถทำได้โดยง่ายผ่านการอุปนัยเชิงคณิตศาสตร์

แต่ก็ยังมีเอกลักษณ์บางอย่างที่ดูแล้วไม่น่าเป็นไปได้ที่จะพิสูจน์ด้วยเทคนิคข้างต้น เช่น

หรือเอกลักษณ์ที่คล้ายๆ กันอย่าง

ถึงแม้เราสามารถสังเกตจากการทดลองได้ว่า สมการข้างต้นเป็นจริงเมื่อ $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)$ ก่อน จะเห็นว่า

และแน่นอนว่าฝั่ง $Q(k+1)$ ก็สามารถถูกพิสูจน์ได้ในทำนองเดียวกัน

เราอาจเรียกเทคนิคนี้ว่าเป็นการพิสูจน์โดยอุปนัยแบบพร้อมเพรียงกัน (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

หมายเหตุ

บล็อกตอนนี้อาจถือได้ว่าเป็นตอนต่อของการคำนวณค่าฟิโบนัชชีด้วยเมทริกซ์ ซึ่งเราสามารถมาถึงข้อสรุปของเอกลักษณ์ข้างต้นได้เช่นกัน ผ่านการแก้สมการเมทริกซ์จากตอนที่แล้วต่อดังนี้

อ้างอิง

  • Lovász, L., Pelikán, J. and Vesztergombi, K., 2003. Discrete mathematics, Undergraduate Texts in Mathematics.