משפט זקנדורף – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
יצירת דף עם התוכן "בתורת המספרים, '''משפט זקנדורף''' הוא משפט (מתמטיקה) הקובע כי כל מספר טבעי ניתן ל[[קיום ..." |
אין תקציר עריכה |
||
שורה 1:
ב[[תורת המספרים]], '''משפט זקנדורף''' הוא [[משפט (מתמטיקה)|משפט]] הקובע כי כל [[מספר טבעי]] ניתן
הצגה שכזו נקראת '''הצגת זקנדורף'''. למשל הצגת זקנדורף של 100 היא:
שורה 16:
בניסוח פורמלי משפט זקנדורף טוען כי לכל <math>\ N</math> טבעי, קיימים טבעיים יחידים <math>\ c_1,\ldots, c_n</math> כך שלכל <math>\ 1\le i<n</math> מתקיים <math>\ 2\le c_i<c_{i+1}-1</math>, וכן:
:<math>\ N=\sum_{i=1}^n F_{c_i}</math>
==הוכחה==
כמו משפטי [[קיום ויחידות]] רבים, הוכחת זקנדורף מתחלקת לשניים. הוכחת קיום והוכחת יחידות:
'''קיום:''' נוכיח ב[[אינדוקציה שלמה]] כי לכל מספר טבעי יש הצגת זקנדורף. ל-<math>\ n=1</math> הטענה בוודאי נכונה כי <math>\ F_2=1</math> (גם מספר יחיד נחשב סכום). נניח כי הטענה נכונה לכל <math>\ k\le n</math> ונוכיח את נכונותה ל-<math>\ n+1</math>. אם <math>\ n+1</math> מספר פיבונאצ'י הוא מהווה הצגה של עצמו. אחרת קיימים שני מספרי פיבונאצ'י כך ש-<math>\ F_i<n+1<F_{i+1}</math>. נגדיר <math>\ a = (n+1) - F_i</math>. ברור כי <math> a\le n</math> ולכן קיימת ל-<math>\ a</math> הצגת זקנדורף לפי הנחת האינדוקציה, שאותה נסמן <math>\ \bar{a}</math>. לפי הגדרת <math>\ a</math> והגדרת מספרי פיבונאצ'י:
:<math>\ a+F_i = n+1 < F_{i+1} = F_{i-1}+F_i \implies a<F_{i-1}</math>
ולכן הצגת זקנדורף של <math>\ a</math> לא כוללת את <math>\ F_{i-1}</math>. כלומר <math>\ \bar{a}+F_i = n+1</math> היא הצגת זקנדורף של <math>\ n+1</math> והאינדוקציה הושלמה.
| |||