เราลองมาหาเอกลักษณ์ฟีโบนักชีและจำนวนลูคัสกันเถอะ

[จินตนาการ สร้างสรรค์]

ฟีโบนักชี มีนิยามคือ F(n)=F(n-1)+F(n-2) โดยที่ F(0)=1,F(1)=1,F(2)=2 เมื่อ n มากกว่าหรือเท่ากับ 2


อยากจะรู้การพิสูจน์ว่า

กำหนดให้ m,n เป็นจำนวนเต็ม แต่ m ไม่เท่ากับ 0

ถ้า m หาร n ลงตัว แล้ว F(m) หาร F(n) ลงตัว


หวังว่าน่าจะมีคนที่พิสูจน์แล้วน่ะคับ

มีตารางฟีโบนักชีให้น่ะคับ

เมื่อ N 1 2 3 4 5 6 7 8 9 10 11 12
F(N) 1 1 2 3 5 8 13 21 34 55 89 144

[nooonuii]

ใช้อันนี้ครับ

$(F_m,F_n)=F_{(m,n)}$

[จินตนาการ สร้างสรรค์]

อันนี้ใช้หรม. ใช่ป่าวด้านบน ลงรายละเอียดให้หน่อยนะคับ

[picmy]

ผมสังเกตเห็นว่า นิยามกับตารางที่คุณ”จินตนาการ สร้างสรรค์”ให้มา มีความไม่สอดคล้องกัน
ซึ่งโดยทั่วๆไป แล้วเรามักจะนิยาม ลำดับฟีโบนักชี ดังความสัมพันธ์ด้านล่าง (นิยามนี้จะสอดคล้องกับตารางที่คุณ”จินตนาการ สร้างสรรค์” ให้มา)
$F_{n+1}=F_n+F_{n-1}$ โดยที่ $n$ เป็นจำนวนเต็มบวก และ $F_0=0 , F_1=1$

สำหรับการที่จะพิสูจน์ว่า : ถ้า $m$ หาร $n$ ลงตัว แล้ว $F_m$ หาร $F_n$ ลงตัว
ผมคิดว่าคงมีหลายวิธีที่จะพิสูจน์
ข้างล่าง ผมจะเสนอวิธีคิดของผมวิธีหนึ่งละกันนะครับ

เราสามารถใช้อุปนัยเชิงคณิตศาสตร์พิสูจน์ได้ว่าสำหรับทุกจำนวนเต็มบวก $t$ และ $0 \leq k \leq t-1$ เรามี
$F_t=F_{k+1}F_{t-k}+F_kF_{t-k-1}$

<Proof by induction1>

ใช้อุปนับเชิงคณิตศาสตร์กับ $k$
(๑) ถ้า $k=0$ หรือ $k=1$ จะเห็นได้อย่างง่ายว่าข้อสรุปเป็นจริง
(๒) สมมติว่า สำหรับทุกจำนวนเต็มบวก $t$ เรามี
$F_t=F_{k+1}F_{t-k}+F_kF_{t-k-1}$
โดยที่ $k < t-1$
ข้างล่างจะแสดงว่า
$F_t=F_{(k+1)+1}F_{t-(k+1)}+F_{k+1}F_{t-(k+1)-1}$
ที่จริงแล้ว เรามี
$F_t=F_{k+1}F_{t-k}+F_kF_{t-k-1}$
$=F_{k+1}(F_{t-k-1}+F_{t-k-2})+ F_kF_{t-k-1}$
$=(F_{k+1}+F_k)F_{t-k-1}+F_{k+1}F_{t-k-2}$
$=F_{k+2}F_{t-k-1}+ F_{k+1}F_{t-k-2}$

จากข้อสรุปนี้ แทน $t=t+k$
เราจะได้ว่า
$F_{t+k}=F_{k+1}F_t+F_kF_{t-1}$
ใช้เอกลักษณ์นี้ และอุปนัยเชิงคณิตศาสตร์ สามารถพิสูจน์ได้ว่า สำหรับทุกจำนวนเต็มบวก $k ,p$ ($p$ เท่ากับ 0 ได้) มี
$F_k | F_{pk}$

<Proof by induction2>

ใช้อุปนับเชิงคณิตศาสตร์กับ $p$
(๑) ถ้า $p=0$ หรือ $p=1$ จะเห็นได้อย่างชัดเจนว่าข้อสรุปเป็นจริง
(๒) สมมติว่า
$ F_k | F_{pk} $
ข้างล่างจะแสดงว่า
$F_k | F_{(p+1)k}$
ที่จริงแล้ว จากเอกลักษณ์ข้างบน เราจะได้ว่า
$F_{(p+1)k}=F_{k+1}F_{pk}+F_kF_{pk-1}$
และเนื่องจาก
$ F_k | F_{pk} $
ดังนั้น
$ F_k | F_{k+1}F_{pk}+F_kF_{pk-1}$
นั่นคือ
$F_k | F_{(p+1)k}$

จากข้อสรุปนี้ เราได้ว่า ถ้า $m$ หาร $n$ ลงตัว แล้ว $F_m$ หาร $F_n$ ลงตัว

แต่ ที่จริงแล้ว เรามีข้อสรุปที่ Strong กว่า ข้อสรุปข้างต้น
กล่าวคือ ที่จริงแล้วเรามี
$F_{gcd(m,n)}=gcd(F_m,F_n)$
ในที่นี้ $gcd(m,n)$ คือห.ร.ม.ของ $m$ และ $n$

แน่นอนว่าคงจะมีหลายวิธีที่จะพิสูจน์ข้อสรุปนี้
ข้างล่างผมจะเสนอแนวคิดของผมคร่าวๆละกันนะครับ

<ขั้นตอนที่ ๑>

ขยายนิยามของลำดับฟีโบนักชี โดยที่ อนุญาตให้สามารถแทน $n$ เป็นลบ หรือ 0 ลงใน $F_{n+1}=F_n+F_{n-1}$ ได้
ยกตัวอย่างเช่น แทน $n=0$ ก็จะได้ว่า $F_1=F_0+F_{-1}$ ดังนั้น $F_{-1}=1$ (เนื่องจาก $F_0=0, F_1=1$)
แทน $n=-1$ ได้ว่า $F_0=F_{-1}+F_{-2}$ ดังนั้น $F_{-2}=-1$
สามารถแสดงได้ว่า สำหรับทุกจำนวนเต็ม $n$ ($n$ อาจเป็นบวก เป็นลบ หรือเป็นศูนย์ก็ได้ )
$F_{-n}=(-1)^{n+1}F_n$
ตอนนี้ เราก็จะได้ลำดับฟีโบนักชี ดังที่แสดงไว้ข้างล่าง
$...,5,-3,2,-1,1,0,1,1,2,3,5,…$

<ขั้นตอนที่ ๒>

สามารถแสดงได้ว่า สำหรับทุกจำนวนเต็ม $t$ และ $k$ ($t ,k$ อาจเป็นบวก เป็นลบ หรือเป็นศูนย์ก็ได้ )
$F_{t+k}=F_{k+1}F_t+F_kF_{t-1}$
(วิธีพิสูจน์ คล้ายๆกับ proof by induction1 )

<ขั้นตอนที่ ๓>

ใช้ข้อสรุปจากขั้นตอนที่ ๒ และอุปนัยเชิงคณิตศาสตร์ สามารถแสดงได้ว่า ถ้า $m$ หาร $n$ ลงตัว แล้ว $F_m$ หาร $F_n$ ลงตัว (ในที่นี้ $m,n$ อาจจะเป็นบวกหรือเป็นลบก็ได้ และ $n$ เป็นศูนย์ได้)

<ขั้นตอนที่ ๔>

เนื่องจาก
$gcd(m,n) |m$ และ $gcd(m,n) |n$
ใช้ข้อสรุปจากขั้นตอนที่ ๓ จะได้ว่า
$F_{gcd(m,n)} |F_m$ และ $F_{gcd(m,n)} |F_n$
ดังนั้น
$F_{gcd(m,n)} |gcd(F_m,F_n)$
ข้างล่างจะแสดงว่า $ gcd(F_m,F_n) | F_{gcd(m,n)} $
ที่จริงแล้ว เนื่องจาก จะต้องมีจำนวนเต็ม $x ,y$ ที่ทำให้
$mx+ny=gcd(m,n)$
ใช้เอกลักษณ์ที่กล่าวถึงในขั้นตอนที่ ๒
จะได้ว่า
$F_{mx+ny}=F_{ny+1}F_{mx}+F_{ny}F_{mx-1}$
และ เนื่องจาก
$gcd(F_m,F_n)|F_m$ และ $F_m|F_{mx}$
ดังนั้น $gcd(F_m,F_n)|F_{mx}$
ในทำนองเดียวกัน จะได้ว่า
$gcd(F_m,F_n)|F_{ny}$
ดังนั้น
$gcd(F_m,F_n)| F_{ny+1}F_{mx}+F_{ny}F_{mx-1}$
นั่นคือ
$ gcd(F_m,F_n) | F_{mx+ny} $
และจาก $mx+ny=gcd(m,n)$
จึงได้ว่า
$ gcd(F_m,F_n) | F_{gcd(m,n)} $
นอกจากนี้ ข้างหน้าเราได้แสดงแล้วว่า $F_{gcd(m,n)} |gcd(F_m,F_n)$
ดังนั้น $F_{gcd(m,n)} =gcd(F_m,F_n)$