שברים משולבים, ולמה הם מגניבים

אוהבים לטעון שהמתמטיקה היא כל כולה ערב רב של נוסחאות מפחידות בעלות משמעות לא ברורה. אני חושב שזה מאוד לא מדויק, אבל מדי פעם אכן מתפלקת לה איזו נוסחה שנראית מפחיד גם למי שכבר יש לו נסיון בסיסי כלשהו במתמטיקה. מה שהפחיד אותי בשעתו היו השברים המשולבים – שברים מהצורה החביבה $latex \frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{4}}}}$. כשרואים דבר כזה, התגובה המיידית של אדם שפוי צריכה להיות "מה, לעזאזל…". בפוסט הזה אני רוצה להסביר מה, לעזאזל. מכיוון שאני חושב שבנושא הזה הדרך הטובה ביותר לדעת מה לעזאזל היא ללכלך את הידיים, חלקו השני של הפוסט יהיה יותר "חישובי" מהרגיל – אך חישובים שלדעתי הם יפים ומעניינים (ובלי לעשות אותם "בידיים"קצת קשה לראות את זה, לדעתי).

בראש ובראשונה, הדבר הזה הוא בסך הכל שבר רגיל. תלמיד כיתה ה' אמור כבר להיות מסוגל להבין מהו ולחשב את ערכו. במקרה של השבר שלעיל, למשל, פשוט צריך לעשות סדרה של חיבורים. $latex 1+\frac{1}{4}=\frac{5}{4}$ ו-$latex \frac{1}{\frac{5}{4}}=\frac{4}{5}$ כך שהשבר שווה ל-$latex \frac{1}{1+\frac{1}{3+\frac{4}{5}}}$; וכעת $latex 3+\frac{4}{5}=\frac{19}{5}$ כך שנקבל שהשבר שווה ל-$latex \frac{1}{1+\frac{5}{19}}$; ולסיום נקבל שהוא שווה ל-$latex \frac{19}{24}$. מה שלא ברור הוא למה לבחור בדרך ייצוג כה מסורבלת ל-$latex \frac{19}{24}$, והתשובה הבסיסית היא – כי זו דרך הייצוג הטבעית והנכונה ביותר למספרים. לא מאמינים? חכו חכו.

ראשית בואו נוותר על הייצוג המסורבל והמזוויע טיפוגרפית. שבר משולב כללי הוא מהצורה $latex a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\dots}}$ (כמובן שאפשר להגדיר שברים משולבים בצורה כללית יותר כך שבמונים יהיו מספרים השונים מ-1, אך זה מסבך את האנליזה ואינו הכרחי כאן ולכן אשתמש בהגדרה המצומצמת) ואת אותו דבר אפשר לתאר בצורה ברורה בעזרת הסימון $latex a_{0}+\frac{1}{a_{1}+}\dots\frac{1}{a_{n}}$. למשל, השבר המשולב שלעיל מיוצג בידי $latex \frac{1}{1+}\frac{1}{3+}\frac{1}{1+}\frac{1}{4}$.

השאלה הראשונה שאני רוצה לעסוק בה היא זו – נניח שיש לנו מספר רציונלי, $latex \frac{a}{b}$; איך מציגים אותו כשבר משולב? למשל, $latex \frac{19}{24}$. מה עושים כדי לתת לו את הצורה ה"קנונית"? כדי לסבך עוד קצת את העניינים אעדיף לדבר על שבר שגדול מ-1, נניח $latex \frac{67}{24}$. את הייצור הזה אפשר לייצג כ-$latex 2+\frac{19}{24}$, כך ש-$latex a_{0}=2$ במקרה שלנו. מה עכשיו? אנחנו רוצים להחליף את ה-$latex \frac{19}{24}$ בגורם מהצורה אחד חלקי משהו, אז ראשית כל נכתוב $latex \frac{19}{24}=\frac{1}{\frac{24}{19}}$, וכעת במכנה יש לנו שוב שבר מדומה ואפשר לפרק אותו לחלק ממשי וחלק שברי: $latex \frac{1}{1+\frac{5}{19}}$ (כלומר $latex a_{1}=1$). נחזור על התעלול שוב עבור $latex \frac{5}{19}$ ונקבל $latex a_{2}=3$ ו"שארית"של $latex \frac{4}{5}$; וכשנטפל ב-$latex \frac{5}{4}$ נקבל $latex 1+\frac{1}{4}$ והמשחק יסתיים. זה תהליך שיטתי ופשוט למדי, וייתכן שלחדי העין שבכם הוא הזכיר תהליך אחר במתמטיקה, שידוע עוד מימי היוונים הקדמונים – האלגוריתם האוקלידי.

בהינתן שני מספרים טבעיים $latex a,b$, האלגוריתם האוקלידי מוצא את המחלק המשותף המקסימלי שלהם: מספר טבעי $latex d$ שמחלק הן את $latex a$ והן את $latex b$ והוא הגדול ביותר בעל תכונה זו. עבור $latex 67$ ו-$latex 24$ המחלק המקסימלי הזה הוא המספר הלא מרשים $latex 1$ (במקרה כזה אומרים ש-67 ו-24 הם "זרים"), אבל מן הסתם יש דוגמאות מעניינות יותר – למשל המחלק המשותף המקסימלי של $latex 78$ ו-$latex 42$ הוא $latex 6$.

כדי למצוא מחלק מקסימלי אפשר לעשות דברים מטופשים כמו לעבור על כל המספרים הקטנים מ-$latex a$ ו-$latex b$ ולבדוק אם הם מחלקים אותם וכדומה, אבל מבחינה חישובית זו שיטה איטית ומייגעת. האלגוריתם האוקלידי, לעומת זאת, פועל מהר מאוד (פורמלית – זמן לוגריתמי בגודל המספרים המעורבים). למעשה, היעילות של האלגוריתם האוקלידי היא הבסיס לתורת המספרים האלגוריתמית; רבים מהחישובים שמתבצעים בתורה זו מסתמכים ברמה זו או אחרת על האלגוריתם האוקלידי (בפרט על גרסה מורחבת שלו, שמאפשרת למצוא $latex x,y$ שלמים (לא בהכרח חיוביים) כך ש-$latex ax+by=d$, כש-$latex d$ הוא המחלק המשותף המקסימלי) ואלמלא הוא היה יעיל, מספר הדברים שניתן לבצע ביעילות היה קטן משמעותית (בפרט, שימוש קריטי שלו הוא למציאת הופכי מודולו $latex n$ של מספרים, מה שהוא הבסיס למימוש פעולות חשבון ב-$latex \mathbb{Z}_{n}^{*}$ – אחרת, אין אפשרות לבצע חלוקה).

הרעיון שמאחורי האלגוריתם האוקלידי פשוט מאוד: בהינתן $latex a,b$ (נניח ש-$latex a$ גדול יותר מ-$latex b$) אפשר לחלק את $latex a$ ב-$latex b$ ולקבל שארית $latex r$ (במילים אחרות, למצוא $latex q,r$ כך ש-$latex a=qb+r$ ו-$latex 0<r<b$). האבחנה המרכזית היא שהמחלק המשותף המקסימלי של $latex a,b$ הוא גם המחלק המשותף המקסימלי של $latex b,r$ (למה?) ולכן אפשר להפעיל את האלגוריתם באופן רקורסיבי על $latex b,r$, כשתנאי העצירה שלנו הוא שאם $latex b$ מחלק את $latex a$ ללא שארית, אז המחלק המשותף המקסימלי שלהם הוא $latex b$ עצמו.

בואו ונראה איך זה עובד עבור $latex 67$ ו-$latex 24$:

$latex 67=2\times24+19$

$latex 24=1\times19+5$

$latex 19=3\times5+4$

$latex 5=1\times4+1$

$latex 4=4\times1+0$

ובשלב האחרון סיימנו: קיבלנו $latex a=4,b=1$ וראינו ש-$latex b$ מחלק את $latex a$ ללא שארית. אלא שמה שמעניין כאן הוא דווקא אותם ערכי $latex q$ שהצטברו במהלך הדרך (המספרים שמשמאל לסימן ה-$latex \times$ בכל שורה) – הסתכלו עליהם – האם הם נראים מוכרים?

הבה ונציג את החלוקות שמבצע האלגוריתם האוקלידי בדרך אחרת. במקום לדבר על חלוקה עם שארית, נעבוד ישירות עם שברים:

$latex \frac{67}{24}=2+\frac{19}{24}$

$latex \frac{24}{19}=1+\frac{5}{19}$

$latex \frac{19}{5}=3+\frac{4}{5}$

$latex \frac{5}{4}=1+\frac{1}{4}$

$latex \frac{4}{1}=4+0$

וזה כבר מאוד מזכיר את התהליך שתיארתי למעלה, של בניית השבר המשולב עבור $latex \frac{19}{24}$. המסקנה היא ש-$latex \frac{67}{24}$ מתואר בידי השבר המשולב $latex 2+\frac{1}{1+}\frac{1}{3+}\frac{1}{1+}\frac{1}{4}$, ושבאופן כללי אפשר למצוא את השבר המשולב עבור $latex \frac{a}{b}$ ביעילות באמצעות האלגוריתם האוקלידי – ובגלל שהעצירה של האלגוריתם האוקלידי מובטחת, גם העצירה של בניית השבר המשולב מובטחת. מה שעוד לא ברור כאן הוא שאם מספר מיוצג בידי שבר משולב, הייצוג הזה הוא יחיד, ולא ייתכן ששני שברים משולבים ייצגו את אותו המספר; גם את זה לא מסובך להוכיח אך ההוכחה טכנית ואפסח עליה.

עד כה לא ממש ברור ממה ההתלהבות הגדולה. אז כן, מצאנו דרך חדשה ומופרעת להציג שברים, אך במה היא טובה יותר מלכתוב סתם $latex \frac{a}{b}$? החלק המעניין מתחיל כשאנו רוצים לייצג באמצעות שברים משולבים מספרים שלא ניתן לייצג באמצעות שברים רגילים, כלומר מספרים אי רציונליים. לצורך כך יהיה הכרחי להרחיב קצת את ההגדרה של שברים משולבים, שכן לא קשה לראות שכרגע כל שבר משולב שאנו מדברים עליו הוא מספר רציונלי (פשוט "פותחים"אותו באופן שעליו כבר דיברתי קודם).

אם כן, מה שנעשה הוא להרשות לתהליך של יצירת השבר להימשך עד אינסוף. במקום שנייצג שבר משולב עם סדרה סופית $latex a_{0}+\frac{1}{a_{1}+}\dots\frac{1}{a_{n}}$, פשוט נרשה לסדרה להיות אינסופית: $latex a_{0}+\frac{1}{a_{1}+}\dots$. למי שמטרידה אותו השאלה איך אפשר לתת משמעות פורמלית לכזה דבר, התשובה פשוטה: $latex a_{0}+\frac{1}{a_{1}+}\dots=\lim_{n\to\infty}a_{0}+\frac{1}{a_{1}+}\dots\frac{1}{a_{n}}$. במילים אחרות, אם יש לנו סדרה אינסופית $latex a_{0},a_{1},\dots$ אנחנו יכולים לקבל ממנה סדרה אינסופית של מספרים רציונליים שמתקבלים מכך ש"קוטמים"את השבר המשולב בכל פעם בשלב מתקדם יותר. כמובן שלא ברור מיידית שהסדרה הזו אכן שואפת למספר ספציפי יחיד; כדי להבין יותר טוב מה הולך כאן, נרצה קודם כל להבין את סדרת הקירובים שמגדיר שבר משולב. ההמשך יהיה יחסית טכני (אם כי לטעמי מעניין מאוד), ואת השורה התחתונה כבר אכתוב בפוסט הבא, לטובת אלו שלא יצליחו לעקוב.

באופן כללי, אם $latex a_{0}+\frac{1}{a_{1}+}\frac{1}{a_{2}+}\dots$ הוא שבר משולב (סופי או אינסופי) אפשר להגדיר סדרה $latex \frac{A_{0}}{B_{0}},\frac{A_{1}}{B_{1}},\frac{A_{2}}{B_{2}},\dots$ של הקירובים המתקבלים משלבי הביניים: $latex \frac{A_{0}}{B_{0}}=a_{0}$, ו-$latex \frac{A_{1}}{B_{1}}=a_{0}+\frac{1}{a_{1}}$ וכן הלאה. השאלה המעניינת ביותר כאן לטעמי היא "האם אפשר לכתוב את $latex A_{n},B_{n}$ בצורה פשוטה כפונקציות של $latex a_{0},\dots,a_{n}$?" והתשובה המפתיעה היא שלא רק שאפשר לעשות את זה, אלא גם ש-$latex A_{n}$ ו-$latex B_{n}$ מאוד, מאוד דומים.

בואו נראה לאט לאט כיצד נבנה שבר משולב. בשלב הראשון יש לנו $latex \frac{a_{0}}{1}$ ותו לא. בשלב השני יש לנו את $latex a_{0}+\frac{1}{a_{1}}$; כדי לראות למה זה שווה אנחנו מבצעים מכנה משותף ומקבלים $latex \frac{a_{0}a_{1}+1}{a_{1}}$. בשלב השלישי יש לנו $latex a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}}}$ וכאן המכנה המשותף נוצר בשני שלבים: ראשית כל מתקבל $latex a_{0}+\frac{1}{\frac{a_{1}a_{2}+1}{a_{2}}}$, ולאחר מכן המכנה "מתהפך", מקבלים $latex a_{0}+\frac{a_{2}}{a_{1}a_{2}+1}$, ולבסוף מתקבל $latex \frac{a_{0}a_{1}a_{2}+a_{0}+a_{2}}{a_{1}a_{2}+1}$.

חדי העין בוודאי שמו לב לדמיון שבין המונה של $latex a_{0}+\frac{1}{a_{1}}$ ובין המכנה של $latex a_{0}+\frac{1}{a_{1}+}\frac{1}{a_{2}}$: הראשון הוא $latex a_{0}a_{1}+1$, השני הוא $latex a_{1}a_{2}+1$. זהו כמובן אינו מקרה: הרי המכנה של $latex a_{0}+\frac{1}{a_{1}+}\frac{1}{a_{2}}$ התקבל מהמונה של $latex a_{1}+\frac{1}{a_{2}}$. זכרו – כדי לחשב את $latex a_{0}+\frac{1}{a_{1}+}\frac{1}{a_{2}}$ אמרנו "בואו קודם כל נשכח מה-$latex a_{0}$ ונסתכל על המכנה $latex a_{1}+\frac{1}{a_{2}}$", אבל מכנה זה הוא בעצמו שבר משולב "רגיל". אחרי שגמרנו לחשב אותו ולהביא אותו לצורה $latex \frac{x}{y}$ ביצענו בו "היפוך" שבו הוחלפו המונה והמכנה.

ההבנה הזו, שהמכנה של שבר משולב הוא בעצם המונה של שבר משולב קצת יותר פשוט, מאפשרת לנו לתאר בצורה קצת יותר נחמדה את המונה והמכנה. נשתמש בסימון $latex \left[a_{0},a_{1},\dots,a_{n}\right]$ כדי לתאר את המונה של השבר המשולב, ועכשיו יש לנו תיאור יפה לקירובים: $latex \frac{A_{n}}{B_{n}}=\frac{\left[a_{0},\dots,a_{n}\right]}{\left[a_{1},\dots,a_{n}\right]}$. זה עדיין לא עוזר לנו להבין איך בדיוק נראית המפלצת שמיוצגת על ידי $latex \left[a_{0},\dots,a_{n}\right]$, אבל זו התחלה טובה.

כעת בואו ונתבונן שניה בשבר המשולב $latex a_{0}+\frac{1}{a_{1}+}\frac{1}{a_{2}+}\dots\frac{1}{a_{n}}$. מצד אחד, אפשר לכתוב אותו כ-$latex \frac{\left[a_{0},\dots,a_{n}\right]}{\left[a_{1},\dots,a_{n}\right]}$ כפי שכבר אמרתי. מצד שני, אפשר לכתוב אותו כ-$latex a_{0}+\frac{\left[a_{2},\dots,a_{n}\right]}{\left[a_{1},\dots,a_{n}\right]}$, שכן אפשר "לחשב עד הסוף" את $latex a_{1}+\frac{1}{a_{2}+}\dots\frac{1}{a_{n}}$ ולבסוף לבצע היפוך שלו. מכאן מתקבלת בקלות הנוסחה הבאה: $latex \left[a_{0},\dots,a_{n}\right]=a_{0}\left[a_{1},\dots,a_{n}\right]+\left[a_{2},\dots,a_{n}\right]$. זו כבר ההתחלה של הגיון בשגעון – ראשית, כעת יש לנו דרך רקורסיבית פשוטה לחשב את $latex \left[a_{0},\dots,a_{n}\right]$; אבל שנית, כעת נוכל להוכיח באינדוקציה תיאור כללי ולא רקורסיבי של המבנה של $latex \left[a_{0},\dots,a_{n}\right]$ שהתגלה, כמו מיליארד דברים אחרים, בידי אוילר.

הכלל נשמע טיפה מוזר ומפחיד בשמיעה ראשונה, אבל עברנו את פרעה ואת "איך בוטלה המתמטיקה"ונעבור גם את זה: $latex \left[a_{0},\dots,a_{n}\right]$ הוא סכום של מכפלות שמתקבלות באופן הבא: ראשית, המכפלה $latex a_{1}a_{2}\cdots a_{n}$. שנית, המכפלה $latex a_{1}a_{2}\cdots a_{n}$ כשהוסר ממנה זוג איברים סמוכים (נניח, $latex a_{3}a_{4}$ הוסר ממנה) – כל המכפלות האפשריות שיכולות להתקבל מהסרת זוג כזה משתתפות בסכום. שלישית, כל המכפלות שמתקבלות מהסרת שני זוגות זרים (כלומר, למשל, $latex a_{2}a_{3}$ ו-$latex a_{7}a_{8}$) וכן הלאה. אם כל האיברים הוסרו ממכפלה היא הופכת להיות "המכפלה הריקה" – 1 (שכן 1 הוא האיבר הנייטרלי לכפל, ולכן הוא מתאים רעיונית לייצוג מכפלה ריקה כשם ש-0 מתאים רעיונית לייצוג סכום ריק).

דוגמאות פשוטות עוזרות כמובן להבין. $latex \left[a_{0}\right]=a_{0}$ שכן יש לנו את המכפלה של "כל" האיברים, וזהו (אין זוגות סמוכים שאפשר להוריד). $latex \left[a_{0}a_{1}\right]=a_{0}a_{1}+1$ שכן יש לנו את המכפלה של כל האיברים $latex a_{0}a_{1}$ ואת המכפלה הריקה $latex 1$. $latex \left[a_{0},a_{1},a_{2}\right]=a_{0}a_{1}a_{2}+a_{0}+a_{2}$, כש-$latex a_{1}$ לא מופיע בסכום לבדו שכן אין זוג סמוך שניתן להוריד ויותיר רק אותו. לבסוף, הנה דוגמה יותר מורכבת:

$latex \left[a_{0},a_{1},a_{2},a_{3},a_{4}\right]=a_{0}a_{1}a_{2}a_{3}a_{4}+$

$latex a_{0}a_{1}a_{2}+a_{0}a_{1}a_{4}+a_{1}a_{2}a_{3}+a_{2}a_{3}a_{4}+$

$latex a_{0}+a_{2}+a_{4}$

כש-$latex a_{2}$ התקבל מכך שהסרנו את הזוגות $latex a_{0}a_{1}$ ו-$latex a_{3}a_{4}$.

מבלבל? כן, אבל לא קשה כל כך להוכחה באינדוקציה בעזרת הנוסחה $latex \left[a_{0},\dots,a_{n}\right]=a_{0}\left[a_{1},\dots,a_{n}\right]+\left[a_{2},\dots,a_{n}\right]$. את הבסיס (עבור $latex \left[a_{0}\right]$ ו-$latex \left[a_{0}a_{1}\right]$) אפשר לראות ישירות; באופן כללי, הבה ונראה מה קורה עם $latex \left[a_{0},\dots,a_{n}\right]$. ראשית, הגורם $latex \left[a_{2},\dots,a_{n}\right]$ תופס את כל המחוברים שהתקבלו על ידי הסרת הזוג $latex a_{0}a_{1}$ ואולי עוד דברים, כך שהגורם הזה בסדר; ואילו $latex a_{0}\left[a_{1},\dots,a_{n}\right]$ תופס את כל הגורמים שהתקבלו ללא הסרת $latex a_{0}$ מההתחלה, ומכיוון שאם מסירים את $latex a_{0}$ זה חייב להיות במסגרת הזוג $latex a_{0}a_{1}$ תפסנו את כל המקרים.

יופי, אז יש לנו תיאור די מפורש של $latex \left[a_{0},\dots,a_{n}\right]$; מה עכשיו? ראשית, עכשיו ברור ש-$latex \left[a_{0},\dots,a_{n}\right]$ הוא ביטוי סימטרי, במובן זה שהוא זהה ל-$latex \left[a_{n},\dots,a_{0}\right]$, ולכן את נוסחת הנסיגה $latex \left[a_{0},\dots,a_{n}\right]=a_{0}\left[a_{1},\dots,a_{n}\right]+\left[a_{2},\dots,a_{n}\right]$ אפשר לכתוב גם מהסוף להתחלה, בתור $latex \left[a_{n},\dots,a_{0}\right]=a_{n}\left[a_{n-1},\dots,a_{0}\right]+\left[a_{n-2},\dots,a_{0}\right]$. עכשיו, מכיוון ש-$latex A_{n}=\left[a_{0},\dots,a_{n}\right]$ ו-$latex B_{n}=\left[a_{1},\dots,a_{n}\right]$, קיבלנו את נוסחת הנסיגה $latex A_{n}=a_{n}A_{n-1}+A_{n-2}$ ו-$latex B_{n}=a_{n}B_{n-1}+B_{n-2}$. אותה נוסחת נסיגה מתארת הן את המונה והן את המכנה וזה כמובן לא מפתיע בהתחשב בכך שכבר אמרתי שהם בעצם אותו הדבר.

מנוסחאות הנסיגה הללו אפשר לגזור נוסחה שקושרת את $latex A_{n},B_{n}$ והיא לב-לבו של העסק. הבה ונסמן ב-$latex \Delta_{n}$ את הביטוי הבא: $latex \Delta_{n}=A_{n}B_{n-1}-A_{n-1}B_{n}$. למה הוא שווה? מסתבר שניתן לחשב אותו במדוייק וערכו מאוד פשוט. כדי לראות זאת, נשתמש בנוסחת הנסיגה ונקבל את הפיתוח הבא:

$latex \Delta_{n}=A_{n}B_{n-1}-A_{n-1}B_{n}=\left(a_{n}A_{n-1}+A_{n-2}\right)B_{n-1}-A_{n-1}\left(a_{n}B_{n-1}+B_{n-2}\right)=$

$latex B_{n-1}A_{n-2}-A_{n-1}B_{n-2}=-\Delta_{n-1}$

ולא קשה לראות כי $latex \Delta_{1}=A_{1}B_{0}-A_{0}B_{1}=1$, כך שקיבלנו בסך הכל ש-$latex \Delta_{n}=\left(-1\right)^{n-1}$. הבה ונכתוב את הנוסחה במפורש:

$latex A_{n}B_{n-1}-A_{n-1}B_{n}=\left(-1\right)^{n-1}$

זו לדעתי דוגמה לנוסחה "יפה", ובכלל – כל החיפוש אחר התכונות של $latex A_{n},B_{n}$ מהווה לטעמי דוגמה למתמטיקה שהיא מצד אחד טכנית וחשבונית מאוד, ומצד שני היא יפה ואף יצירתית.

טוב, חדל התלהבות, נשאלת השאלה מה יצא לנו מכל זה. התשובה היא שיצא לנו המון – עכשיו אנחנו יודעים לתאר היטב את ההתנהגות של הסדרה $latex \frac{A_{0}}{B_{0}},\frac{A_{1}}{B_{1}},\dots$. בפרט, אנחנו יודעים לתאר בקלות את ההפרש בין שני גורמים סמוכים. נסו לחשוב שנייה מדוע, ואז הציצו בשורה הבאה:

$latex \frac{A_{n}}{B_{n}}-\frac{A_{n-1}}{B_{n-1}}=\frac{A_{n}B_{n-1}-A_{n-1}B_{n}}{B_{n}B_{n-1}}=\frac{\left(-1\right)^{n-1}}{B_{n}B_{n-1}}$.

מכיוון ש-$latex B$-ים חיוביים תמיד, נובע שאם $latex n$ אי זוגי, אז $latex \frac{A_{n}}{B_{n}}$ גדול מ-$latex \frac{A_{n-1}}{B_{n-1}}$ (הפרשם חיובי) ואחרת הוא קטן ממנו. מכאן שסדרת הקירובים "מזפזפת" מעלה ומטה. אבל האם היא נרגעת? ובכן, בואו ננסה לראות מה קורה כשמשווים איבר לא לקודמו, אלא לזה שלפניו, כלומר מנסים לחשב את $latex \frac{A_{n}}{B_{n}}-\frac{A_{n-2}}{B_{n-2}}$. הדרך הפשוטה ביותר לעשות זאת היא באמצעות תעלול נפוץ מאוד בחשבון: להוסיף ולהחסיר את אותו איבר. נקבל:

$latex \frac{A_{n}}{B_{n}}-\frac{A_{n-2}}{B_{n-2}}=\left(\frac{A_{n}}{B_{n}}-\frac{A_{n-1}}{B_{n-1}}\right)+\left(\frac{A_{n-1}}{B_{n-1}}-\frac{A_{n-2}}{B_{n-2}}\right)=\frac{\left(-1\right)^{n-1`}}{B_{n}B_{n-1}}+\frac{\left(-1\right)^{n-2}}{B_{n-1}B_{n-2}}=\frac{\left(-1\right)^{n-1}}{B_{n-1}}\left[\frac{1}{B_{n}}-\frac{1}{B_{n-2}}\right]$

האיבר בסוגריים המרובעים הוא ללא ספק שלילי, כי הוא מכיל משהו חיובי במכנה ו-$latex B_{n-2}-B_{n}$ במונה, אבל ב-$latex B_{n}$ גדול מ-$latex B_{n-2}$ כי הוא מכיל את $latex B_{n-2}$ כחלק מהסכום שלו (מדוע?). מסקנה: עבור ערכים זוגיים של $latex n$, אנחנו מקבלים שההפרש כולו חיובי, ולכן הסדרה של ה-$latex \frac{A_{n}}{B_{n}}$-ים הזוגיים היא עולה, ואילו סדרת ה-$latex \frac{A_{n}}{B_{n}}$-ים האי זוגיים היא יורדת; וסדרת האיברים הזוגיים חסומה מלמעלה על ידי סדרת האיברים האי זוגיים (ובאופן סימטרי, סדרת האיברים האי זוגיים חסומה מלמטה על ידי סדרת האיברים הזוגיים). כאן נכנס לתמונה משפט בסיסי מחשבון אינפיניטסימלי: אם יש לנו שתי סדרות מספרים, האחת עולה והשנייה יורדת, כך שהמרחק ביניהן שואף לאפס – הן מתכנסות, ולאותו הגבול (במקרה שלנו המרחק הוא $latex \frac{\left(-1\right)^{n-1}}{B_{n}B_{n-1}}$ והוא בוודאי שואף לאפס כי ה-$latex B_{n}$-ים שואפים לאינסוף).

הגענו לשורה התחתונה: אם ניקח סדרה כלשהי של מספרים טבעיים ונתבונן בשבר המשולב שהיא מגדירה, $latex a_{0}+\frac{1}{a_{1}+}\frac{1}{a_{2}+}\dots$, נקבל תמיד שהשבר הזה מתכנס למספר ממשי כלשהו. השאלה שנותרה היא האם עבור כל מספר ממשי קיים שבר משולב שמתכנס אליו, ואני מניח שאתם מנחשים שהתשובה חיובית. מספיק לדבר על מספרים ממשיים חיוביים, כי עבור מספרים שליליים השינוי היחיד שיידרש הוא שהאיבר $latex a_{0}$ יהיה שלילי.

ניקח אם כן מספר ממשי $latex \alpha$ שהוא אי רציונלי (ברציונליים כבר טיפלנו). אפשר לפרק אותו לשני חלקים – החלק השלם $latex a_{0}$, שהוא המספר הטבעי הגדול ביותר שעודנו קטן מ-$latex \alpha$; והחלק השברי, שהוא מספר ממשי חיובי קטן מ-1. מכיוון שהוא קטן מ-1, ניתן לכתוב אותו בתור $latex \frac{1}{\alpha_{1}}$. אם כן: $latex \alpha=a_{0}+\frac{1}{\alpha_{1}}$. אני מניח שאתם מבינים מה יבוא כעת: אם $latex \alpha_{1}$ אי רציונלי (אחרת $latex \alpha$ היה רציונלי – מדוע?) ולכן נחזור על התעלול גם עבורו ונקבל $latex \alpha=a_{0}+\frac{1}{a_{1}+\frac{1}{\alpha_{2}}}$ וכן הלאה וכן הלאה. כל שנשאר להבין הוא האם התוצאה אכן מתכנסת אל $latex \alpha$ – ואם כן, כמה מהר?

לשם כך נשים לב לרגע לעובדה שלא באמת השתמשנו במה שעוללנו ל-$latex A_{n},B_{n}$ בכך שה-$latex a_{n}$-ים כולם שלמים. זה מאפשר לנו לכתוב את $latex \alpha$ בתור "שבר משולב" סופי אם נרשה לאיבר האחרון להיות לא שלם, דהיינו $latex \alpha=\frac{\left[a_{0},a_{1},\dots,a_{n},\alpha_{n+1}\right]}{\left[a_{1},a_{2},\dots,a_{n},\alpha_{n+1}\right]}$. אם נשתמש כאן בנוסחת הנסיגה שכבר מצאנו למונה והמכנה, אז אפשר לכתוב $latex \alpha=\frac{\alpha_{n+1}A_{n}+A_{n-1}}{\alpha_{n+1}B_{n}+B_{n-1}}$. עכשיו, כדי לראות עד כמה $latex \frac{A_{n}}{B_{n}}$ הוא קירוב טוב ל-$latex \alpha$ נחסר את האחד מהשני ונקבל:

$latex \alpha-\frac{A_{n}}{B_{n}}=\frac{\alpha_{n+1}A_{n}+A_{n-1}}{\alpha_{n+1}B_{n}+B_{n-1}}-\frac{A_{n}}{B_{n}}=\frac{A_{n-1}B_{n}+A_{n}B_{n-1}}{B_{n}\left(\alpha_{n+a}B_{n}+B_{n-1}\right)}=\frac{\left(-1\right)^{n-1}}{B_{n}\left(\alpha_{n+a}B_{n}+B_{n-1}\right)}$

כאן שוב השתמשנו בנוסחה הקסומה $latex A_{n}B_{n-1}-A_{n-1}B_{n}=\left(-1\right)^{n-1}$. ניקח ערך מוחלט לביטוי, ונקבל בסופו של דבר ש:

$latex \left|\alpha-\frac{A_{n}}{B_{n}}\right|<\frac{1}{B_{n}B_{n+1}}$ (מאיפה ה-$latex B_{n+1}$ צץ פתאום? הוא קטן יותר מהגורם שבתוך הסוגריים במכנה – מדוע?).

ושוב, מכיוון ש-$latex B_{n}$ היא סדרה עולה, נובע מכך ש-$latex \frac{A_{n}}{B_{n}}$ מתכנסת ל-$latex \alpha$, בדיוק כפי שרצינו. לא רק זה – קצב ההתכנסות הוא ריבועי; אך על כך ארחיב בפוסט הבא.

19 תגובות בנושא “שברים משולבים, ולמה הם מגניבים”

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

    תן איזה גיוון קטן מידי פעם שגם לא מתמטיקאים יבינו ויהנו מהמקום המגניב הנ"ל.

    בתודה רבה מראש.

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

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

    בכבוד.

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

  4. Sorry for the English this time, "computer says no" to Hebrew today.

    I'm sorry as well for being pedantic. Feel free to remove this comment. This is a wonderful post, I guess the length got to you, I know it would get me tired. I hope you forgive me for assuming the role of editor.

    1. There's a missing space after the link to "How Mathematics was canceled".

    2. In the next paragraph you omitted the comma in [a0a1]=… (this typo is repeated in the next paragraph)

    3. In the same paragraph you expand [a0,a1,a2,a3,a4], but you wrote [a1,a2,a3] in the sum instead of [a0,a3,a4]

  5. אף פעם לא חשבתי שיש משהו מעניין כל כך בשברים המשולבים האלו, ועכשיו אני רואה שטעיתי.
    מעניין.

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

  6. היי גדי,

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

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

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

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

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

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

  9. בעזרת הגרסה המורחבת של האלגוריתם האוקלידי, בהינתן a,n זרים אפשר למצוא x,y כך ש-ax+ny=1. מכאן שמודולו n מתקיים ax=1, כלומר x הוא ההופכי של a מודולו n. אם a אינו זר ל-n הוא גם אינו הפיך מודולו n.

    השיטה הזו עובדת לכל n, לא רק לראשוניים.

  10. אני חושב שיש לך טעות קטנה באמצע, כשאתה מסביר על התיאור הכללי של אוילר:
    [a0,…,an] הוא סכום של מכפלות שמתקבלות באופן הבא:
    ראשית, המכפלה a1*a2*…*an(אמור להיות גם את a0) .
    ואחרי כן, בדוגמה של a0*a1*a2*a3*a4, אני חושב באחד האברים כתבת
    a1*a2*a3 במקום a0*a3*a4…
    זה נכון?

  11. בדיוק בזמן, נראה לי שיש טעות קלה בתיאור של שבר משולב ללא נוסחאת נסיגה:
    [a0,a1,a2,a3,a4]=a0a1a2a3a4+[a0,a1,a2,a3,a4]=a0a1a2a3a4+
    a0a1a2+a0a1a4+a1a2a3+a2a3a4+a0a1a2+a0a1a4+a1a2a3+a2a3a4+
    a0+a2+a4

    אני חושב שלא אמורה להופיע השלשה a1a2a3 בסכום כי זה דורש את הסרת a0 ו-a4 והם אינם זוג סמוך.

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *