משפט זקנדורף – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה
אין תקציר עריכה
שורה 29:
 
נסמן ב-<math>\ F_s</math> ו-<math>\ F_t</math> את האיברים הגדולים ביותר ב-<math>\ S'</math> וב-<math>\ T'</math> בהתאמה. <math>\ F_s\ne F_t</math> כי הסרנו איברים משותפים. נניח [[ללא הגבלת הכלליות]] כי <math>\ F_s<F_t</math>, כלומר <math>\ F_{s+1}\le F_t</math>. לפי הלמה הסכום של <math>\ S'</math> קטן מ-<math>\ F_{s+1}</math> ולכן גם קטן מ-<math>\ F_t</math>. לעומת זאת ברור כי הסכום של <math>\ T'</math> הוא לפחות <math>\ F_t</math>, בסתירה לכך שהסכומים שווים. מכאן שלכל מספר טבעי יש הצגת זקנדורף יחידה.
 
==הצגת זקנדורף==
יש דמיון רב בין הצגת זקנדורף של מספר להצגה שלו ב[[בסיס ספירה]], ובייחוד ב[[בסיס בינארי]]. הצגת זקנדורף מציגה כל מספר כסכום של מספרי פיבונאצ'י שונים ואילו הצגה בינארית מציגה כל מספר כסכום של חזקות שונות של 2. למשל לפי הסימון המקובל: <math>\ 100 = 2^6+2^5+2^2 = 1100100_2</math> (ההצגה הבינארית של [[100 (מספר)|מאה]]). באופן דומה ניתן להציג כל מספר ב"בסיס זקנדורף" כאשר הספרה הראשונה (הימנית ביותר) מייצגת את <math>\ F_2</math> ואילו הספרה ה-n מייצגת את <math>\ F_{n+1}</math>. למשל הצגת זקנדורף של מאה היא: <math>\ 100 = F_{11}+F_6+F_4 = 1000010100_Z</math>.
 
[[en:Zeckendorf's Theorem]]