משפט זקנדורף

המחשה ויזואלית של הצגת זקנדורף של כל המספרים הטבעיים עד 160 (ציר ה-y). כל צבע מייצג מספר פיבונאצ'י עד 144. גובהו של כל מלבן שווה למספר פיבונאצ'י המתאים לו. ניתן לראות שכל מספר נוצר כסכום של המלבנים שמתחתיו.

בתורת המספרים, משפט זקנדורף הוא משפט הקובע כי כל מספר טבעי ניתן להצגה בצורה יחידה כסכום של מספרי פיבונאצ'י שונים שאין ביניהם שניים עוקבים (סמוכים זה לזה בסדרה). את המשפט הוכיח הרופא הצבאי הבלגי אדואר זקנדורף (1901‏-1983), שהיה מתמטיקאי חובב.

הצגה שכזו נקראת הצגת זקנדורף. למשל הצגת זקנדורף של 100 היא:

100 = 89 + 8 + 3

את 100 ניתן להציג כסכום של מספרי פיבונאצ'י גם בדרכים אחרות. למשל:

100 = 89 + 8 + 2 + 1 = 55 + 34 + 8 + 3

אבל הצגות אלו אינן הצגות זקנדורף כי מופיעים בהן מספרי פיבונאצ'י עוקבים.

רקע וניסוח פורמלי

מספרי פיבונאצ'י מוגדרים באופן רקורסיבי לפי נוסחת הנסיגה:

${\begin{cases}F_{1}=F_{2}=1\\F_{n+1}=F_{n}+F_{n-1}\end{cases}}$

כלומר שני מספרי פיבונאצ'י הראשונים הם 1 וכל מספר פיבונאצ'י אחר מתקבל כסכום שני מספרי פיבונאצ'י הקודמים. $F_{n},F_{n+1}$ נקראים מספרי פיבונאצ'י עוקבים.

בניסוח פורמלי, משפט זקנדורף טוען כי לכל $\ N$ טבעי, קיימים טבעיים יחידים $\ c_{1},\ldots ,c_{n}$ כך שלכל $\ 1\leq i<n$ מתקיים $\ 2\leq c_{i}<c_{i+1}-1$, ושמקיימים: $\ N=\sum _{i=1}^{n}F_{c_{i}}$.

כאשר מופיע 1 בהצגת זקנדורף הוא נחשב ל-$\ F_{2}$ ולא ל-$\ F_{1}$ (וכך נמנעת ה"רמאות" של שימוש הן ב-$\ F_{3}=2$ והן ב-$\ F_{1}=1$ שלכאורה אינם עוקבים).

הוכחה

כמו משפטי קיום ויחידות רבים, הוכחת זקנדורף מתחלקת לשניים. הוכחת קיום והוכחת יחידות:

קיום: נוכיח באינדוקציה שלמה כי לכל מספר טבעי יש הצגת זקנדורף. ל-$\ n=1$ הטענה בוודאי נכונה כי $\ F_{2}=1$ (גם מספר יחיד נחשב סכום). נניח כי הטענה נכונה לכל $\ k\leq n$ ונוכיח את נכונותה ל-$\ n+1$. אם $\ n+1$ מספר פיבונאצ'י הוא מהווה הצגה של עצמו. אחרת קיימים שני מספרי פיבונאצ'י כך ש-$\ F_{i}<n+1<F_{i+1}$. נגדיר $\ a=(n+1)-F_{i}$. ברור כי $a\leq n$ ולכן קיימת ל-$\ a$ הצגת זקנדורף לפי הנחת האינדוקציה, שאותה נסמן $\ {\bar {a}}$. לפי הגדרת $\ a$ והגדרת מספרי פיבונאצ'י:

$\ a+F_{i}=n+1<F_{i+1}=F_{i-1}+F_{i}\implies a<F_{i-1}$

ולכן הצגת זקנדורף של $\ a$ לא כוללת את $\ F_{i-1}$. כלומר $\ {\bar {a}}+F_{i}=n+1$ היא הצגת זקנדורף של $\ n+1$ והאינדוקציה הושלמה.

למה: נציג למה שתשמש בהמשך: הסכום של קבוצת מספרי פיבונאצ'י שונים זה מזה שאין מביניהם שניים עוקבים, כך שהמספר הגדול בסכום הוא $\ F_{n}$, תמיד יהיה קטן מ-$\ F_{n+1}$ (ל-$\ n>1$). נקרא לסכום שכזה סכום זקנדורף. ההוכחה באינדוקציה: המקרה $\ n=2$ טריוויאלי, כי הסכום יהיה $\ F_{2}=1$, שקטן מ-$\ F_{3}=2$. נניח כי הטענה נכונה לכל $\ k\leq n$ ונוכיח את נכונותה ל-$\ n+1$. נסמן ב-$\ a$ את סכום כל איברי סכום זקנדורף מלבד $\ F_{n+1}$. ידוע כי $\ F_{n}$ לא מופיע בסכום כי $\ F_{n+1}$ עוקב שלו. לכן המספר הגדול ביותר בסכום $\ a$ הוא לכל היותר $\ F_{n-1}$, ולכן לפי הנחת האינדוקציה $\ a<F_{n}$. ומכאן: $\ a+F_{n+1}<F_{n}+F_{n+1}=F_{n+2}$ כפי שנדרש להוכיח.

יחידות: נניח בשלילה כי קיים N שיש לו שתי הצגות זקנדורף שונות. נסמן ב-$\ S$ את קבוצת המספרים בסכום הראשון וב-$\ T$ את קבוצת המספרים בסכום השני. לפי ההנחה שני הסכומים שווים. נגדיר $\ S'=S\setminus T$ ו-$\ T'=T\setminus S$ (ראו הפרש קבוצות), כלומר יצרנו שתי קבוצות חדשות שנוצרו משתי הקבוצות הקודמות לאחר הסרת האיברים המשותפים להן, מכל אחת מהן. מאחר שהסרנו רק איברים משותפים סכום איברי הקבוצה הראשונה עדיין שווה לסכום איברי הקבוצה השנייה. לא ייתכן כי אחת מהקבוצות ריקה, כי אז גם השנייה ריקה (יש להן את אותו הסכום) ומכיוון שהן התקבלו מהסרת האיברים המשותפים של שתי הקבוצות המקוריות, המסקנה היא כי הקבוצות היו שוות, בסתירה להנחה.

נסמן ב-$\ F_{s}$ ו-$\ F_{t}$ את האיברים הגדולים ביותר ב-$\ S'$ וב-$\ T'$ בהתאמה. $\ F_{s}\neq F_{t}$ כי הסרנו איברים משותפים. נניח ללא הגבלת הכלליות כי $\ F_{s}<F_{t}$, כלומר $\ F_{s+1}\leq F_{t}$. לפי הלמה הסכום של $\ S'$ קטן מ-$\ F_{s+1}$ ולכן גם קטן מ-$\ F_{t}$. לעומת זאת ברור כי הסכום של $\ T'$ הוא לפחות $\ F_{t}$, בסתירה לכך שהסכומים שווים. מכאן שלכל מספר טבעי יש הצגת זקנדורף יחידה.

מציאת הצגת זקנדורף

את הצגת זקנדורף של מספר נתון N ניתן למצוא בעזרת אלגוריתם חמדן פשוט הנובע ישירות מהוכחת המשפט:

1. מוצאים את מספר פיבונאצ'י הגדול ביותר שקטן או שווה ל-N.
2. מחסרים מ-N את המספר שמצאנו בשלב 1 וחוזרים על שלב 1 עם ההפרש שחושב.

האלגוריתם נעצר כאשר ההפרש יוצא 0. אז קבוצת מספרי פיבונא'צי שמצאנו היא הצגת זקנדורף הרצויה.

בהצגת זקנדורף של מספר N יהיו בערך $\ \log N$ מחוברים, כי סדרת פיבונאצ'י $\ F_{n}$ גדלה בקצב אסימפטוטי לסדרה ההנדסית ${\tfrac {1}{\sqrt {5}}}\phi ^{n}$ (כאשר $\ \phi$ הוא יחס הזהב).

דוגמה

נמצא את הצגת זקנדורף של 83:

• מספר פיבונאצ'י הגדול ביותר שקטן או שווה 83 הוא 55.
  • 28 = 83 − 55
• מספר פיבונאצ'י הגדול ביותר שקטן או שווה 28 הוא 21.
  • 7 = 28 − 21
• מספר פיבונאצ'י הגדול ביותר שקטן או שווה 7 הוא 5.
  • 2 = 7 − 5
• מספר פיבונאצ'י הגדול ביותר שקטן או שווה 2 הוא 2.
  • 0 = 2 − 2

נקבל את ההצגה: 83 = 55 + 21 + 5 + 2.

הצגת זקנדורף וקוד פיבונאצ'י

יש דמיון רב בין הצגת זקנדורף של מספר להצגה שלו בבסיס ספירה, ובייחוד בבסיס בינארי. הצגת זקנדורף מציגה כל מספר כסכום של מספרי פיבונאצ'י שונים ואילו הצגה בינארית מציגה כל מספר כסכום של חזקות שונות של 2. למשל לפי הסימון המקובל: $\ 100=2^{6}+2^{5}+2^{2}=1100100_{2}$ (ההצגה הבינארית של מאה). באופן דומה ניתן להציג כל מספר ב"בסיס פיבונאצ'י" או "בסיס זקנדורף" כאשר הספרה הראשונה מימין מייצגת את $\ F_{2}$ ובאופן כללי הספרה ה-n מימין מייצגת את $\ F_{n+1}$. אם הספרה היא '1' סימן שמספר פיבונאצ'י המתאים משתתף בסכום, ואם היא '0' סימן שהוא לא משתתף. למשל הצגת זקנדורף של מאה היא: $\ 100=F_{11}+F_{6}+F_{4}=1000010100_{Z}$.

מאפיין ייחודי של הצגת זקנדורף של מספר הוא שלעולם לא יופיעו שני '1' סמוכים (כי אין בהצגה שני מספרי פיבונאצ'י עוקבים). עובדה זו מנוצלת בתורת הקודים, שם משתמשים בהצגת זקנדורף להגדרת קוד פיבונאצ'י. קוד פיבונאצ'י הוא קוד בינארי (מופיעים בו רק 0 ו-1) שמייצג מספרים טבעיים. קוד פיבונאצ'י של מספר טבעי מתקבל מהיפוך סדר הספרות של הצגת זקנדורף שלו והוספת '1' בסופו (צד ימין). למשל קוד פיבונאצ'י של מאה הוא: $\ 00101000011$. מכיוון שבהצגת זקנדורף לעולם לא מופיעים שני '1' סמוכים, '11' תמיד מייצג סוף של מספר בקוד פיבונאצ'י. למעשה ה-'1' שנוסף בסוף הקוד מתפקד כפסיק, ומאפשר לכתוב מחרוזת רציפה של מספרים שניתן להבדיל ביניהם. לדוגמה המחרוזת $\ {\color {Blue}1011}{\color {Red}001011}{\color {OliveGreen}11}$ מייצגת את הסדרה: $\ {\color {Blue}4},{\color {Red}11},{\color {OliveGreen}1}$ (הצביעה לשם נוחות הקריאה בלבד).

עוקב פיבונאצ'י

עוקב פיבונאצ'י היא פעולה אונרית המוגדרת על מספרים לפי הצגת זקנדורף שלהם. העוקב פיבונאצ'י של n מוגדר כמספר שהצגת זקנדורף שלו מתקבלת מלקיחת מספר הפיבונאצ'י העוקב לכל מספר פיבונאצ'י בהצגת זקנדורף של n. כלומר אם $\ n=\sum _{i=1}^{k}F_{c_{i}}$ היא הצגת זקנדורף של n, אז העוקב מוגדר $\sigma (n)=\sum _{i=1}^{k}F_{c_{i}+1}$. למשל $\sigma (100)=\sigma (89)+\sigma (8)+\sigma (3)=144+13+5=162$.

קל לראות שמספר הוא עוקב פיבונאצ'י של מספר אחר אם ורק אם הוא "זוגי פיבונאצ'י", כלומר $F_{2}=1$ לא מופיע בהצגת זקנדורף שלו.

הסדרה עם תנאי ההתחלה $a_{2}=1$ שכל $2<n$ מקיימת $a_{n+1}=\sigma (a_{n})$ היא סדרת פיבונאצ'י. באופן כללי כל סדרה שכזו עם תנאי התחלה כלשהו מקיימת את יחס הנסיגה של סדרת פיבונאצ'י.

לעוקב פיבונאצ'י קשר הדוק לטבלת וייטהוף (Wythoff array), שמציגה תכונות מעניינות רבות של סדרות דמויות פיבונאצ'י.

מכפלת פיבונאצ'י

מכפלת פיבונאצ'י היא פעולה בינארית בין מספרים טבעיים המוגדרת בעזרת הצגת זקנדורף. את הפעולה הגדיר דונלד קנות' שגם הוכיח שהיא אסוציאטיבית.

בהינתן הצגות זקנדורף $\ a=\sum _{i=1}^{k}F_{c_{i}}$ ו-$\ b=\sum _{j=1}^{l}F_{d_{j}}$ של $\ a$ ו-$\ b$, מכפלת פיבונאצ'י $\ a\circ b$ מוגדרת: $\ a\circ b=\sum _{i=1}^{k}\sum _{j=1}^{l}F_{c_{i}+d_{j}}$.

למשל: $\ 4\circ 6=(F_{2}+F_{4})\circ (F_{2}+F_{5})=F_{2+2}+F_{2+5}+F_{4+2}+F_{4+5}=3+13+8+34=58$.

הכללות

את משפט זקנדורף ניתן להכליל למספרי פיבונאצ'י מסדר שלילי. מספרים אלו מוגדרים $\ F_{-n}=(-1)^{n+1}F_{n}$ (ו-$\ F_{0}=0$). כך הם ממשיכים לקיים את נוסחת הנסיגה ואת תנאי ההתחלה של סדרת פיבונאצ'י. לכל מספר שלם, חיובי או שלילי (או אפס), קיימת הצגה יחידה כסכום של מספרי פיבונאצ'י מסדר שלילי. למשל:

• 24 = F_-1 + F_-4 + F_-6 + F_-9 = 1 + (-3) + (-8) + 34
• -43 = F_-2 + F_-7 + F_-10 = (-1) + 13 + (-55)

ואילו 0 הוא הסכום הריק.

ניתן להגדיר הצגת זקנדורף שלילית וקוד פיבונאצ'י שלילי באופן דומה למקרה החיובי. בניגוד לאנלוג החיובי, ההצגה והקוד השליליים מסוגלים לתאר כל מספר שלם, ולא רק חיוביים.

משפט זקנדורף תקף גם לסדרות k-בונאצ'י $\ F_{n}^{(k)}$. אלו הן סדרות המוגדרות על ידי נוסחת הנסיגה $\ F_{n+k}^{(k)}=F_{n+k-1}^{(k)}+\ldots +F_{n+1}^{(k)}+F_{n}^{(k)}$ (מספר k-בונאצ'י הוא סכום k מספרי k-בונאצ'י הקודמים) ותנאי ההתחלה $\ F_{1}^{(k)}=\ldots =F_{k-2}^{(k)}=0,F_{k-1}^{(k)}=F_{k}^{(k)}=1$ (הסדרה מתחילה ב-k−2 אפסים ואחריהם שני 1). המקרה k=2 הוא סדרת פיבונאצ'י הרגילה. לכל מספר טבעי יש הצגה יחידה כסכום של מספרי k-בונאצ'י שאין ביניהם k מספרי k-בונאצ'י עוקבים.

קישורים חיצוניים

• נוסחה סגורה למכפלת פיבונאצ'י (קובץ טקסט)