משפט מוסנר

משפט מוסנר או "הקסם של מוסנר" הוא כינוי לתהליך המחשב עבור כל $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].