סידרה שכזו

[עריסטו]

סידרה שכזו

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

 

[יאיר של תמר]

אולי ננסה יחד...

הצלחתי להוכיח עבור כל An כאשר n הוא ראשוני. הנה... A1 חייב להיות שווה 2 (כי 1 מתחלק רק בעצמו, ו- 2 =2¹) A2 חייב להיות שווה 2 (כי A1 + A2 = 2²) עבור כל עבור n ראשוני, מתקיים A1 + An = 2ⁿ (וזאת מפני ש-n הוא ראשוני ומתחלק רק ב-1 ובעצמו). מכיוון ש A1=2 מתקבל An = 2ⁿ - 2.. little fermat's theorem קובע כי aⁿ-a מתחלק ב-n אם n הוא ראשוני ושונה מ-a. ולכן An מתחלק ב-n.

 

[ןן גיל ןן]

פתרון

ע"פ נוסחת ההיפוך של מביוס, מתקיים

a=SIGMA (d|n) mu(d) 2^(n/d)​

(סכום עבור כל ה d-ים המחלקים את n. הסמל mu מיצג את פונקצית מביוס שהיא 1- בחזקת מס' הגורמים הראשוניים של המספר אם כל הגורמים הראשוניים שונים זה מזה, ו- 0 אם יש גורם ראשוני שחוזר יותר מפעם אחת). נפרק את n לגורמים ראשוניים:

n=p1^e1 * p2^e2 * .. * pr^er​

אז מספר המחוברים בנוסחה הוא 2 בחזקת r כי אנו עוברים על כל המחלקים של p1p2...pr (המחלקים האחרים של n נותנים מחובר 0 כי יש בהם חזקת ראשוני גדולה מ-1). כעת לכל k בין 1 ל-r נוכיח שהסכום מתחלק ב- pk^ek (ובזאת נסיים). נחלק את קבוצת המחלקים של p1...pr לזוגות מספרים מהצורה a,a*pk (כאשר a מחלק של p1...pr שאינו מתחלק ב- pk). אז זוג כזה תורם לסכום (בסימן + או - בהתאם למספר המחלקים הראשוניים של a)

2^(n/a) - 2^(n/(a*pk))​

מכיוון ש- a אינו מתחלק ב- pk נוכל לכתוב

n/a=pk^ek * b n/(a*pk) = pk*(ek-1) * b​

ולכן הסכום הוא

2^(pk^ek*b)-2^(pk^(ek-1)*b)​

אבל, מודולו pk^ek מתקיים

1=2^phi(pk^ek)=2^(pk^ek-pk^(ek-1)) => 2^(pk^ek)=2^(pk^(ek-1))​

(כאשר phi מסמן את פונקצית אוילר). לכן הסכום מודולו pk^ek הוא

2^b-2^b=0​

מש"ל.

 

[עריסטו]

../images/Emo127.gif אמנם פתרונך נכון, אבל

התכוונתי לפתרון הרבה יותר פשוט.

 

[ןן גיל ןן]

האם תוכל להחכימנו בו?

 

[עריסטו]

הנה

zzz a zzz הוא מספר המחרוזות הבינאריות באורך n, שאינן בנויות מקטע שחוזר על עצמו. למשל

a(12)=2^12-a(6)-a(4)-a(3)-a(2)-a(1)​

כי ממספר המחרוזות באורך 12 אנחנו מחסרים את מספר המחרוזות שאורך המחזור שלהן הוא 6, את מספר המחרוזות שאורך המחזור שלהן הוא 4 וכן הלאה. zzz a zzz מתחלק ב-n כי לכל אחת מ-a המחרוזות יש n תמורות מעגליות, שכל אחת מהן היא בעלת אותה תכונה - היא ינה בנויה מקטע שחוזר על עצמו.

 

[ןן גיל ןן]

יפה!

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