משפט מוסנר

משפט מוסנר או "הקסם של מוסנר" הוא כינוי לתהליך המחשב עבור כל $n$ קבוע, את סדרת החזקות $a^{n}$ על ידי פעולות של דילוג וחישוב סכומים חלקיים בסדרת המספרים הטבעיים. את התהליך גילה המתמטיקאי הגרמני אלפרד מוסנר (Alfred Moessner). תהליכים דומים מייצרים גם את מספרי העצרת וטורים נוספים^[1].

היסטוריה[עריכת קוד מקור | עריכה]

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

סדרת השלמים	$1,2,3,4,5,6,7,8,9,10,11,12...$
בדילוג על כל מספר שני	$1,3,5,7,9,11...$
סכומים חלקיים	$1,4,9,16,25,36...$
שהם טור הריבועים	$1^{2},2^{2},3^{2},4^{2},5^{2},6^{2}...$

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

בניית הסדרה לחזקה n[עריכת קוד מקור | עריכה]

מתחילים מטור השלמים ומסמנים לדילוג כל מספר $n$ -י. מחשבים את טור הסכומים החלקיים ללא המספרים המדולגים. חוזרים על הפעולה, הפעם מסמנים לדילוג כל מספר $(n-1)$ , ויוצרים סדרת סכומים חדשה. עבור השלב ה- $k$ -י יש לסמן לדילוג את האיברים $(n-k+1)$ . התהליך מסתיים בשלב ה- $n$ -י, והסדרה שתישאר היא $1^{n},2^{n},3^{n},4^{n},5^{n},6^{n},7^{n},8^{n}...$ .

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

${\begin{array}{ccccccccccccccccc}1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17\\1&2&3&&5&6&7&&9&10&11&&13&14&15&&17\\1&3&6&&11&17&24&&33&43&54&&67&81&96&&113\\1&3&&&11&17&&&33&43&&&67&81&&&113\\1&4&&&15&32&&&65&108&&&175&256&&&369\\1&&&&15&&&&65&&&&175&&&&369\\1&&&&16&&&&81&&&&256&&&&625\end{array}}$

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

משפט פאשה[עריכת קוד מקור | עריכה]

הבנייה של מוסנר נעשית בדילוג בצעד קבוע, למשל עבור $n=4$ מדלגים על שלושה מספרים ומשמיטים כל מספר רביעי. ב-1952, שנה אחרי התגלית של מוסנר, הציע איוון פאשה (Ivan Paasche) לדלג במרווחים שגדלים באחד כל פעם: למחוק את המספר הראשון, להשאיר את השני, למחוק את השלישי, להשאיר את 2 הבאים בתור, למחוק את השישי, וכן הלאה, לפי הסדר 1, 3, 6, 10 וכולי, או ${k+1 \choose 2}$ . מחשבים את הסכומים ללא המספרים המחוקים, ובאיטרציה הבאה מוחקים מספרים לפי אותו סדר ומחשבים את הסכומים החלקיים, עד השורה האחרונה. הטור המתקבל הוא טור $\ n!$ ^[2].