פיתרון בעית התחלקות המערבת מספרי פיבונאצ'י (2024)

מבוא

באולימפיאדת גיליס ה-48 (תחרות מתמטיקה לנוער), שהתקיימה ב-28.12.14, הופיעה השאלה הבאה:

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

זו הייתה השאלה השביעית והאחרונה. נוכיח אותה כאן בשני אופנים:

• קומבינטורי – הוכחה אלמנטרית לחלוטין ברוח ההגדרה הקומבינטורית של מספרי פיבונאצ'י וההוכחה הקומבינטורית של המשפט הקטן של פרמה
• ואלגברי – הוכחה מעולם הפולינומים הסימטריים, עם אינטרפרטציה מאנליזה p-אדית

כמו כן, נציג הכללות שונות ומשונות.

פילוסופיה

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

• סעיף א' נובע ישירות מהפעלת סעיף ב' עבור , כי .לכן נוכיח פשוט את סעיף ב' לכל שלם אי-שלילי.
• כמו כן, אין סיבה להגביל את להיות אי-זוגי – מבחינתנו מותר ל-להיות שווה 2.

נסמן. אפשר לנסח את השאלה באופן הבא:

עבור כל מספר טבעי נגדיר את הסדרה . עבור סדרה זו מתקיימת טענה אנלוגית:

עבור זהו המשפט הקטן של פרמה, ועבור כללי זו מסקנה ישירה ממשפט אוילר ( אם , כאשר היא פונקציית אוילר).
מסתבר ש- חולקות תכונות קומבינטוריות ואלגבריות – נראה זאת במהלך הפוסט. הפילוסופיה של הפוסט תהיה:

פילוסופיה: כל הוכחה של הטענה ניתנת להסבה להוכחה של הטענה המקבילה

הוכחה קומבינטורית – פיצות פיבונאצ'י

הוכחה עבור

Laten we naar pizza's kijken משולשים, כאשר כל משולש יכול לקבל בדיוק אחת מבין תוספות. כמה פיצות כאלו יש?

התשובה היא , בהנחה שאנחנו חושבים על המשולשים של הפיצה כממוספרים מ-1 עד . לדוגמא, אם , אנחנו מבדילים בין הפיצה "זיתים, אננס, עגבניות" ו-"אננס, עגבניות, זיתים".

סופרת פיצותעם משולשים, כאשר כל משולש יכול לקבל בדיוק אחת מבין תוספות, ויש חשיבות לסדר המשולשים (לצורך העניין, המשולשים ממוספרים 1 עד ).

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

• "בטטה, תירס, בטטה, תירס, בטטה, תירס, בטטה, תירס" זו פיצה מחזורית
• "אננס, עגבניות, זיתים" שהופיע קודם היא לא מחזורית

מחזור של פיצה מוגדר בתור "בכמה משולשים אני צריך לסובב אותה כדי לקבל פיצה זהה (כלומר, עם אותן תוספות)?":

• "בטטה, תירס, בטטה, תירס, בטטה, תירס, בטטה, תירס" בעלת מחזור 2
• "אננס, עגבניות, זיתים" בעלת מחזור 3

ננסה לספור פיצות לא מחזוריות עם משולשים. נספור אותן באמצעות לספור את כל הפיצות עם כזה מספר משולשים () ולחסר את כל הפיצות המחזוריות עם כזה מספר משולשים.

לפיצה עם משולשים יכולים להיות רק מחזורים שמחלקים את . אם המחזור הוא בדיוק אז היא לא מחזורית, אחרת היא כן.
במקרה קורה משהו נחמד: או שהפיצה לא מחזורית, או שהמחזור מחלק את . לכן צריך לספור פיצות עם מחזור המחלק את.

איך נעשה זאת? נשים לב שלכל פיצה מחזורית עם משולשים אפשר להתאים פיצה עם משולשים, ע"י לקחת את הפיצה שהמשולשים שלה הם ה- משולשיםהראשונים של הפיצה המקורית. לדוגמא, במקרה ,נתאים ל-"בטטה, תירס, בטטה, תירס, בטטה, תירס, בטטה, תירס" את "בטטה, תירס, בטטה, תירס".
התאמה זו היא חח"ע ועל (מהאבחנה הקודמת לגבי מחזורים – אתן לכם להשלים את הפרטים), ולכן כמות הפיצות המחזוריות יוצאת .

קיבלנו:

כמות הפיצות הלא מחזוריות עם משולשים היא

טענה: כמות זו מתחלקת ב-.הוכחה: כל פיצה לא מחזורית עם משולשים אפשר לסובב ב- דרכים ולקבל כך פיצה שונה. זה המקרה .

מסקנה: המשפט הקטן של פרמה. הוכחה: נבחר .

פירוש קומבינטורי של מספרי פיבונאצ'י

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

נסתכל על מחרוזות באורך של אפסים ואחדות, כך שאסור שיהיו 2 אפסים רצופים (010 – חוקי, 001 – לא חוקי). נקרא למחרוזות כאלה "חוקיות".

טענה: יש סה"כ מחרוזות חוקיות באורך .
הוכחה:יש בדיוק שתי אפשרויות: או שמחרוזת כזו מתחילה ב-1 וממשיכה במחרוזת חוקית הקצרה בתו אחד, או שהיא מתחילה ב-01 ואז מחרוזת חוקית הקצרה בשניים. לכן מספר המחרוזות מקיים את נוסחת הנסיגה של פיבונאצ'י. תנאי ההתחלה שונים: יש 2 מחרוזות מאורך 1 (0, 1), ו-3 מאורך 2 (11, 01, 10), ולכן זו סדרת פיבונאצ'י בהזזה. .

נסווג את המחרוזות החוקיות לארבעה סוגים:

1. מחרוזות שמתחילות ב-1 ומסתיימות ב-1
2. מחרוזות שמתחילות ב-0 ומסתיימות ב-0
3. מחרוזות שמתחילות ב-0 ומסתיימות ב-1
4. מחרוזות שמתחילות ב-1 ומסתיימות ב-0

אפשר לראות ש:

• מספר המחרוזות מהסוג הראשון הוא : אם מתעלמים מהתו הראשון והאחרון, נשארים עם מחרוזת חוקית באורך בלי הגבלות.
• מספר המחרוזות מהסוג השני הוא : כדי שמחרוזת כזו תהיה חוקית, התו השני והתו הלפני האחרון צריכים להיות 1, ואם מתעלמים מ-2 התווים הראשונים ו-2 התווים האחרונים, נשארים עם מחרוזת חוקית בלי הגבלות.
• בדומה, אפשר לוודא שמספר המחרוזות משני הסוגים האחרונים הוא .

סופר את המחרוזות החוקיות באורך שמתחילות ומסתיימות באותו התו. נתנו הרגע פירוש קומבינטורי לסדרה שהופיעה בשאלה!

הערה: במקום 0 ו-1 יכולנו באותה מידה לכתוב "בצל" ו"פטריות". בסעיף הבא נעשה זאת:

פיצות פיבונאצ'י

איך זה מתקשר אלינו? אני רוצה לספור עכשיו פיצות עם משולשים ועם תוספות: בצל ופטריות. כמה כאלו יש? , נכון. אבל מה קורה אם אני מוסיף את האילוץ הבא: "אסור 2 משולשים של בצל אחד אחרי השני"?

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

נקרא לפיצות כאלה "פיצות פיבונאצ'י".

טענה: כמות הפיצות הזו היא בדיוק הסדרה .
הוכחה:אפשרלחשוב על פיצה עם משולשים בתור סדרה באורך של תוספות, כאשר התוספת ה--ית היא התוספת הראשונה.
באופן כזה אני מתרגם את הדרישה "אין בצלים עוקבים" על פיצה מעגלית באורך לדרישה "אין בצלים עוקבים" על סדרה באורך .
שימו לב שהיינו חייבים להאריך את הסדרה ב-1: אחרת, הפיצה המעגלית עם 3 משולשים "בצל, פטריות, בצל" הייתה נחשבת פיצה חוקית (כי בסדרה "בצל, פטריות, בצל" אין 2 בצלים עוקבים, למרות שפיצה היא מעגל ואחרי הבצל במשולש השלישי מגיע הבצל במשולש הראשון). חייבים לקודד אותה בתור הסדרה באורך 4 "בצל, פטריות, בצל, בצל".
על השאלה הזו (כמה סדרות עם 2 ערכים כך שערך מסוים לא מופיע פעמיים רצוף יש?) ענינו בסעיף הקודם, רק שבמקום הערכים בצל ופטריות השתמשנו ב-0 ו-1.

הסיום האלגנטי

הבנו ש- סופרת פיצות עם משולשים ו-2 תוספות: בצל ופטריות, כך שאין 2 משולשים עוקבים עם בצל. עכשיו נתעניין, כמו שהתעניינו קודם, בפיצות פיבונאצ'י שאינן מחזוריות.

טענה:סופר את כמות פיצות פיבונאצ'י הלא מחזוריות עם משולשים.

הוכחה:ראינו שהמחובר הראשון סופר את כמות פיצות פיבונאצ'י עם משולשים.
פיצה כזו היא מחזורית אמ"מ המחזור שלה מחלק את. לכן נותר להסביר למה הביטוי שחיסרנו, , סופר פיצות פיבונאצ'י עם ומחזור המחלק את . ההסבר הוא זה:
יש התאמה חח"ע ועל בין פיצות עם מחזור המחלק את לבין פיצות עם משולשים – ההתאמה היא להצטמצם לפיצה שנוצרת מ- המשולשים של הפיצה המקורית. היא חח"ע בגלל המחזור, וההעתקה היא על כי אם אני לוקח איזושהי פיצת פיבונאצ'י עם משולשים ויוצר ממנה פיצה עם פי משולשים (ע"י חזרה) – מקבלים פיצה חוקית (רק בקצוות יש סיכון לבצל שאחריו יגיע בצל, אבל זה לא יתכן כי הפיצה המקורית היא מסוג פיבונאצ'י).

מסקנה:מתחלק ב-.
הוכחה: לכל פיצת פיבונאצ'י לא מחזורית עם משולשים יש סיבובים שנותנים פיצת פיבונאצ'י שונה. זה המקרה .

כדי להדגים, נייצג את התוספות עם 0 (בצל) ו-1 (פטריות).אם , נקבל שמספר פיצות הפיבונאצ'י עם משולשים הוא .

מתוכן, פיצות פיבונאצ'י מחזוריות יש.אלו הן הפיצות 111111111 (שמתאימה לפיצה 111 עם 3 משולשים) ו-101101101,011011011,110110110 (שמתאימות לפיצות 101,011,110 עם 3 משולשים).
ההפרש מתחלק ב-. זה קורה בגלל שלכל פיצה שספרנו יש 9 סיבובים שונים, לדוגמא:

111111110, 111111101, 111111011, 111110111, 111101111, 111011111, 110111111, 101111111, 011111111

הוכחה אלגברית – פונקציות סימטריות ופונקציות p-מכווצות

הוכחה עבור

יהי ראשוני. נסתכל על הפונקציה מהמספרים השלמים לעצמם. יש לה 2 תכונות "קסם":

• – שקול למשפט הקטן של פרמה
• אם (כאשר ) אז – נובע מכך ש- ושהמנה שמופיע מתחלקת ב-:

פונקציה שמקיימת 2 תנאים אלו תיקרא "p-מכווצת". הסדרה מקיימת , דבר שגורר, באינדוקציה, :

• עבור זה שקול לכך ש- מתחלק ב- – נובע מהתכונה הראשונה של פונקציה p-מכווצת.
• אם זה נכון עבור כלשהו, זה נכון גם ל-, מהתכונה השנייה של פונקציה p-מכווצת:

הערה: אם עובדים בנורמה ה-p-אדית (בה ), הפונקציה הזו היא "כמעט" ליפשיצית. אפשר לנסח את התנאים עליה בתור:

ניסוח מחדש של הבעיה

נחזור לבעיה שלנו.
תהי.באינדוקציה ישירה רואים כי לכל שלם אי-שלילי. נשים לב ש-.לכן אפשר לנסח את השאלה בתור:

הראו כי מתחלק ב-.

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

לפני שנתחיל בהוכחות, נשים לב שעבור מטריצות 1 על 1, מקבלים את הטענה מהסעיף הקודם.

המקרה n=0

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

בגלל ש- אינווריאנטי לשינוי בסיס (כלומר, הצמדה), נרצה ללכסן את . זה לא תמיד אפשרי, אבל מה שכן תמיד אפשרי זה שילוש – לפחות אם עובדים בהרחבה מספיק גדולה של .בבסיס זה גם משולשית, והשיוויון נהיה:,כאשר הסכום הוא על הע"ע של .

למקרה הזה יש הוכחה פשוטה במיוחד. הצעד הראשון הוא (נכונותו נובעת לדוגמא מכך שהעלאה בחזקת היא אוטומורפיזם בכל הרחבה סופית של). הצעד השני הוא להראות ש-– שיוויון במספרים שלמים (כי)שנובע מהמשפט הקטן של פרמה.
תרגיל 1: הראו את השיוויון עבור בסיס של המטריצות השלמות, ואז הראו שאם השיוויון עובד לשתי מטריצות הוא עובד גם לסכומן (רמז: השתמשו בכך ש- אינווריאנטי לסיבובים – ).

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

הוכחה קומבינטורית עם גרפים – חדשה אך שקולה

לפני שנוכיח את המקרה הכללי עם פונקציות p-מכווצות, אתן את ההוכחה הקומבינטורית שהבטחתי. הסיפור הוא כזה: אפשר לחשוב על בתור מטריצת שכנויות של גרף מכוון (ולאו דווקא פשוט).
באופן כללי, מהגדרת כפל מטריצות, סופר את כמות המסלולים באורך מקודקוד לקודקוד .
העקבה של סופרת מסלולים בגרף, שאורכם , והם מתחילים ומסתיימים באותו קודקוד.
הביטויסופר את מספר המסלולים הלא מחזוריים (כלומר, לא מורכבים מאותו מסלול שחוזר על עצמו מספר פעמים) באורך.המספר הזה מתחלק ב- כי לכל מסלול כזה יש הזזות ציקליות שונות שגם נותנות מסלול המקיים את אותן התכונות.
ודאו שאתם מבינים את השקילות להוכחה עם הפיצות. עבור המקרה של פיבונאצ'י, יש לגרף 2 קודקודים (0 ו-1), ושלוש צלעות (לולאה מ-1 לעצמו, צלע מ-0 ל-1 וצלע בכיוון השני).

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

המקרה הכללי עם פולינומים סימטרים

נמשיך עם האלגברה. ההוכחה שלנו תהיה בניחוח ההוכחה איתה פתחנו את הפרק. היא מבוססת מאמר של Mazur ו-Petrenko, שם הוכיחו את הטענה החזקה הבאה:

• למטריצות אותו פולינום אופייני מודולו p
• אם ל- אותו פולינום אופייני מודולו , אז יש ל- אותו פולינום אופייני מודולו .

ומתוכן מקבלים באינדוקציה ישירה:

בעלי פולינומים אופייניים שמסכימים מודולו , לכל .

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

ההוכחה דורשת היכרות עם פולינומים סימטריים. אני אציג אינטרפרטציה להוכחה (שהבנתי אחרי שיחה עם ד. כ., קורא הבלוג), ואח"כ אציג את ההוכחה המקורית במספר שלבים, שם תצטרכו להשלים חלק מהפרטים.

אינטרפרטציה להוכחה

באינטרפרטציה הזו, למען הנוחות, נתמקד בטענה שהזכרנו (הנובעת מהמאמר): בעלי פולינומים אופייניים שמסכימים מודולו , לכל .

במקום לדבר על פולינומים אופייניים, נחזור לדבר על השורשים שלהם (קרי, הערכים העצמיים של המטריצה. מתוכם אפשר לשחזר את הפולינום). נסמן את השורשים של הפולינום של ב-. נשים לב שכשמעלים מטריצה בחזקה, הערכים העצמיים שלה עולים באותה חזקה.
בגלל שהמטריצות שלנו שלמות, הפולינומים האופייניים הם מתוקנים ועם מקדמים שלמים. בפרט, אפשר לחשוב על השורשים כעל שורשים של פולינום מתוקן עם מקדמים שלמים. המקרה שלנו מתייחס ספציפית לפולינום , עם השורשים .
מנוסחאות ויאטה, אנחנו יודעים שהפולינומים הסימטרים האלמנטרים בשורשים אלו הם מספרים שלמים (במקרה שלנו, ).
אנחנו רוצים לחקור את העקבה של , שהיא .
נסמן ב- את הפולינומים הסימטרים האלמנטרים ב- משתנים (לדוגמא: ). אותנו מעניין הפולינום הראשון, , כשמציבים בו את השורשים המדוברים בחזקת חזקות ראשוניים. הדרך להבין את ההצבה הזו היא להבין את כל הפולינומים הסימטרים בו"ז כשמציבים בהם את החזקות הנ"ל, כלומר גם את כשמציבים בהם את החזקות.לכן נסמן:

(כאמור, אותנו מעניינת רק הקואורדינטה הראשונה, אבל נבין אותה אם נבין את השאר.)
נסמן ב- את הפונקציה המקיימת:

(לדוגמא: .) מהמשפט היסודי שלהפולינומים הסימטריים, זה פולינום, ולמעשה עם מקדמים שלמים (בפרט, נובע ש- וקטור שלם).
אפשר להגיד משהו חזק יותר – בגלל ש- עם מקדמים שלמים (מהמשפט הקטן של פרמה), נובע שוב מהמשפט היסודי שזה פולינום עם מקדמים שלמים בפולינומים הסימטרים ובפרט נכון להגיד ש:

אם נסמן ב- את הפונקציה הוקטורית שמורכבת מכל הפולינומים הללו, , נקבל ש:

זה שיוויון פנטסטי, שמציג את הסדרה המעניינת אותנו כסדרת רקורסיה מעומק 1. איך נראית הפונקציה ?

• עבור מטריצות 1 על 1,
• עבור מטריצות 2 על 2, . לדוגמא, עבור נקבל .
  עבור מטריצות 3על 3,

עבור מטריצות 1 על 1, הטענות שאנחנו צריכים להוכיח נובעות מכך ש- היא p-מכווצת, כמו שראינו בתחילת הפרק.
העניין הוא שגם עבור מטריצות גדולות יותר זה נכון, אם נרחיב את ההגדרה של פונקציות p-מכווצות:

פונקציה תיקרא "p-מכווצת" אם מתקיימות 2 התכונות הבאות:

• – כלומר, כל קואורדינטה של הפרש הוקטורים מתאפסת מודולו p
• (כאשר ) גורר

אם נראה ש- היא p-מכווצת, אז התכונות שלה יגררו באינדוקציה ישירה ש-, וזה בדיוק מה שרצינו להוכיח.

תרגיל חשוב: הראו ש- שלנו היא p-מכווצת מתוך כך שהיא פונקציה פולינומיאלית המקיימת .
(רמז:התנאי הראשון נובע ישירות מהמשפט הקטן של פרמה. התנאי השני סגור לחיבור, לכן מספיק להוכיח זאת עבור הפונקציה ועבור פונקציה פולינומיאלית שכל מקדמיה מתחלקים ב-.)

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

מגניב.

הערה:כדאי לחשוב על כעל העלאה בחזקת (קואורדינטה-קואורדינטה), עד כדי "שגיאה" שהיא פולינום כפול . זה מבטיח התכנסות -אדית של הסדרה – אנחנו מתכנסים לנקודת שבת לא טריוויאלית של ב--אדים. כלומר, ב--אדים, הפונקציה מקיימת בדיוק את התנאים (הכמו-ליפשיציים) כדי שהאיטרציות יתכנסו לנקודת שבת, מה שמזכיר מאודאת הבנייה של van Teichmüller.

שלבי ההוכחה המקורית

אע"פ שהאינטרפרטציה שנתתי מכילה את כל הרעיונות של ההוכחה, אני בכל זאת מפרט כאן את שלבי ההוכחה בניסוחם המקורי – מיועד בעיקר למי שהסתבך עם האינטרפרטציה:

1. יהיפולינום סימטרי ו-מספר ראשוני. הראו שקיים פולינום סימטריכך ש-

2. יהיוהפולינומים הסימטרים האלמנטרים ב-.מהמשפט היסודי של הפולינומים הסימטרים, לכל קיים פולינום יחידכך ש-

השתמשו בסעיף הקודם כדי להראות ש-.

3. נעבוד ב-ונגדיר את האידאל.השתמשו בפיתוח טיילור ובסעיף הקודם כדי להראות ש-

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

5. מסקנה משני הסעיפים האחרונים: אם חוג חילופי, ו-אידאל בו, אז גורר.
עבור נקבל: גורר .

6. הראו, בעזרת סעיף 4, כי עבורמתוקן, מתקיים.כלומר, ל-ול-אותו פולינום אופייני מודולו .

7. כעת אפשר להראות, באינדוקציה על ,של-אותו פולינום אופייני מודולו : מקרה הבסיס הוא הסעיף הקודם, וצעד האינדוקציה מהסעיף הקודם-קודם.
בפרט, יש להם אותה עקבה מודולו .

הכללות

הכללה של ההוכחה הראשונה

נכליל את ההוכחה הראשונה באמצעות פונקציית מביוס:

מתחלק ב- לכל טבעי.

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

הכללה של ההוכחה השנייה

נכליל את ההוכחה השנייה באמצעות חקר מטריצות.

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

מסתבר שלכל נוסחת נסיגהעם מקדמים שלמים, יש תנאי התחלה יחידים כך שהיא תתקבל בתור. הפולינום האופייני של כזו חייב להיות הפולינום האופייני של הנוסחה: (ואפשר לבנות כזו מטריצה לדוגמא בעזרתמטריצה נלוות). לאחר שילוש, אנחנו מגלים ש-כאשר הסכום הוא על שורשי הפולינום.
נובע שתנאי ההתחלה הם: עבור .
הערה: אפשר לכתוב אתכפולינומים במקדמים – ראו זהויות ניוטון.

דוגמא: אם אז והסדרה נהיית.
אם , אז ו-. בפרט, אם רוצים את נוסחת הנסיגה של פיבונאצ'י, נקבל את תנאי ההתחלה .

נשים לב ש-היא גם סדרה כזו – אם נשתמש בנוסחת המפורשת,נקבל:

כאשר השיוויון האחרון נבע מכך ש-.

מוכרת בתור "סדרת לוקאס" ומקיימת בין השאר.

שילוב שתי ההכללות

אם נשלב את 2 ההכללות, נקבל שאם היא סדרת נסיגה מעומק המקיימת (סכום על שורשי הפולינום האופייני של הסדרה)עבור, אזמתחלק ב-לכל טבעי.

תרגיל 2:הראו שהביטוי מתחלק ב-, לכל טבעי. (רמז: נגדיר שפיצות הן שקולות אם אחת מתקבלת מהשנייה ע"י סיבוב. סיפרו את מספר מחלקות השקילות של פיצות חוקיות באורך בעזרת משפט המנייה של פוליה.)
תרגיל 3: הראו שלא מקבלים אינפורמציה אריתמטית חדשה על הסדרה מתוך התרגיל הקודם, ושלמעשה גם התכונהוגם התכונהשקולות לתכונה: לכל ראשוני ו- טבעיים.
(תרגילים נוספים בניחוח זה תוכלו למצוא באוסף התרגילים על פונקציות אריתמטיות כאן– הסתכלו לדוגמא על שאלה 8.)