ทฤษฎีบทของเซกเคนดอร์ฟ การแทนค่าจำนวนเต็มด้วยลำดับฟีโบนักชี

ทฤษฎีบทของเซกเคนดอร์ฟ (Zeckendorf's theorem) เป็นหลักการทางคณิตศาสตร์ที่ตั้งชื่อตาม Edouard Zeckendorf นักคณิตศาสตร์สมัครเล่น โดยทฤษฎีนี้กล่าวถึงวิธีการแทนค่าจำนวนเต็มบวกใดๆ ในรูปของผลรวมของจำนวนในลำดับฟีโบนักชี (Fibonacci numbers) ที่มีคุณสมบัติเฉพาะตัว

นิยามของทฤษฎีบท

ทฤษฎีบทของเซกเคนดอร์ฟระบุว่า จำนวนเต็มบวกทุกจำนวนสามารถเขียนแทนได้ด้วยผลรวมของจำนวนฟีโบนักชีหนึ่งจำนวนหรือมากกว่า โดยมีเงื่อนไขสำคัญคือ ต้องไม่ใช้จำนวนฟีโบนักชีสองจำนวนที่อยู่ติดกันในลำดับ และผลรวมนี้จะมีลักษณะเป็นเอกลักษณ์ (Unique) คือมีเพียงรูปแบบเดียวเท่านั้นสำหรับจำนวนเต็มนั้นๆ

หากให้ $N$ เป็นจำนวนเต็มบวก จะมีจำนวนเต็มบวก $c_i \geq 2$ ซึ่ง $c_{i+1} > c_i + 1$ ที่ทำให้เกิดสมการดังนี้:

โดยที่ $F_n$ คือจำนวนฟีโบนักชีลำดับที่ $n$ การแทนค่าในลักษณะนี้เรียกว่า การแทนค่าแบบเซกเคนดอร์ฟ (Zeckendorf representation) ซึ่งเป็นพื้นฐานในการสร้างการเข้ารหัสแบบฟีโบนักชี (Fibonacci coding)

ตัวอย่างการคำนวณ

พิจารณาจำนวน 64 การแทนค่าแบบเซกเคนดอร์ฟของ 64 คือผลรวมของจำนวนฟีโบนักชีที่ไม่ต่อเนื่องกัน เช่น $55 + 8 + 1$ (ซึ่งเป็นจำนวนฟีโบนักชีลำดับที่ 10, 6 และ 2 ตามลำดับ) ในขณะที่การเขียน 64 ในรูปแบบอื่น เช่น $34 + 21 + 8 + 1$ ไม่ถือเป็นการแทนค่าแบบเซกเคนดอร์ฟ เนื่องจาก 34 และ 21 เป็นจำนวนฟีโบนักชีที่อยู่ติดกันในลำดับ

วิธีการหาค่าด้วยอัลกอริทึมแบบละโมบ (Greedy Algorithm)

เราสามารถหาการแทนค่าแบบเซกเคนดอร์ฟได้โดยการเลือกจำนวนฟีโบนักชีที่มีค่ามากที่สุดที่ยังน้อยกว่าหรือเท่ากับจำนวนนั้นๆ ในแต่ละขั้นตอน ดังนี้:

• ตัวอย่างที่ 1: 11 = 8 + 3
• ตัวอย่างที่ 2: 13 = 13 (เนื่องจาก 13 เป็นจำนวนฟีโบนักชีอยู่แล้ว จึงไม่ต้องบวกเพิ่ม)
• ตัวอย่างที่ 3: 31 = 21 + 8 + 2

การพิสูจน์ทฤษฎีบท

การพิสูจน์ทฤษฎีบทของเซกเคนดอร์ฟแบ่งออกเป็นสองส่วนหลัก คือ การพิสูจน์ว่าการแทนค่านี้ มีอยู่จริง (Existence) และการพิสูจน์ว่าการแทนค่านี้ มีเพียงหนึ่งเดียว (Uniqueness)

1. การพิสูจน์การมีอยู่ (Existence)

สามารถพิสูจน์ได้โดยใช้การอุปนัยทางคณิตศาสตร์ (Mathematical Induction) โดยเริ่มจากกรณีพื้นฐาน $n=1$ ซึ่งมีการแทนค่าเป็น $F_2$

หากสมมติว่าจำนวนเต็มทุกจำนวนที่น้อยกว่า $n$ มีการแทนค่าแบบเซกเคนดอร์ฟ เราสามารถหาจำนวนฟีโบนักชี $F_j$ ที่ใหญ่ที่สุดที่ $F_j < n < F_{j+1}$ แล้วนำ $n - F_j$ มาหาการแทนค่า ซึ่งจะทำให้ได้ผลรวมที่ไม่ใช้จำนวนฟีโบนักชีที่ติดกัน

2. การพิสูจน์ความเป็นเอกลักษณ์ (Uniqueness)

การพิสูจน์ส่วนนี้มักใช้เอกลักษณ์ทางคณิตศาสตร์ที่เกี่ยวข้องกับผลรวมของจำนวนฟีโบนักชี เพื่อแสดงให้เห็นว่าหากมีการแทนค่าสองรูปแบบที่แตกต่างกันสำหรับจำนวนเดียวกัน จะนำไปสู่ข้อขัดแย้งทางคณิตศาสตร์