בקצרה:אינדוקציה מתמטית היא שיטה להוכיח בבת אחת סדרה אינסופית של טענות, טענה לכל מספר טבעי: מוכיחים שהטענה הראשונה נכונה (הבסיס), ומוכיחים שאם טענה כלשהי נכונה, גם הטענה שאחריה נכונה (הצעד). בסרטון המרצה ממחיש זאת בשורה של אבני דומינו: האבן הראשונה נופלת, וכל אבן שנופלת מפילה את הבאה אחריה, ולכן כל האבנים נופלות; אם האבן הראשונה לא נופלת, או שיש בשורה רווח גדול מדי, השרשרת נעצרת. בצעד לא מניחים את מה שצריך להוכיח: מניחים שהטענה נכונה עבור [math]\displaystyle{ n }[/math] מסוים, ומוכיחים אותה עבור [math]\displaystyle{ n+1 }[/math]. הדוגמה המרכזית בפרק היא אי-שוויון ברנולי[math]\displaystyle{ (1+x)^n\ge1+nx }[/math], שבעזרתו מוכיחים מיד אחר כך שהחזקות של מספר הגדול מאחד שואפות לאינסוף.
▶ ההרצאה: אינדוקציה מתמטית
ריצוף לוח משבצות שחסרה בו משבצת אחת (המסומנת ב־X) בחתיכות בצורת L, כמו בדוגמה 4. משמאל, הצעד של האינדוקציה (כאן [math]\displaystyle{ n=2 }[/math]): לוח [math]\displaystyle{ 2^{n+1}\times2^{n+1} }[/math] מתחלק לארבעה רבעים בגודל [math]\displaystyle{ 2^n\times2^n }[/math]. המשבצת החסרה נמצאת באחד מהם, והחתיכה הירוקה שבמרכז מכסה משבצת אחת בכל אחד משלושת הרבעים האחרים. עכשיו בכל רבע חסרה (או כבר מכוסה) משבצת אחת בדיוק, ולכן לפי הנחת האינדוקציה [math]\displaystyle{ P(n) }[/math] אפשר לרצף כל רבע. מימין, הריצוף המלא של לוח [math]\displaystyle{ 8\times8 }[/math] ב־[math]\displaystyle{ 21 }[/math] חתיכות, שמתקבל מחזרה על אותו צעד: החתיכה הירוקה מונחת ראשונה (level 1), החתיכות האפורות במרכזי ארבעת הלוחות [math]\displaystyle{ 4\times4 }[/math] (level 2), והחתיכות התכולות ממלאות את שישה־עשר הלוחות [math]\displaystyle{ 2\times2 }[/math], שהם הבסיס (level 3).
תהי [math]\displaystyle{ P(1),P(2),P(3),\dots }[/math] סדרת טענות כך שמתקיימים שני התנאים הבאים:
הטענה [math]\displaystyle{ P(1) }[/math] נכונה.
לכל [math]\displaystyle{ n\in\mathbb N }[/math], אם הטענה [math]\displaystyle{ P(n) }[/math] נכונה אזי גם הטענה [math]\displaystyle{ P(n+1) }[/math] נכונה.
אזי הטענה [math]\displaystyle{ P(n) }[/math] נכונה לכל [math]\displaystyle{ n\in\mathbb N }[/math].
דוגמה 1: חסם לסדרת נסיגה: [math]\displaystyle{ a_{n+1}=1+\frac{|a_n|}2 }[/math]
תהי [math]\displaystyle{ a_n }[/math] הסדרה המוגדרת על ידי [math]\displaystyle{ a_1=1 }[/math] ו־[math]\displaystyle{ a_{n+1}=1+\frac{|a_n|}2 }[/math] לכל [math]\displaystyle{ n\in\mathbb N }[/math]. (א) הוכיחו באינדוקציה כי [math]\displaystyle{ 1\le a_n<2 }[/math] לכל [math]\displaystyle{ n\in\mathbb N }[/math]. (ב) הוכיחו כי הסדרה עולה ממש, כלומר [math]\displaystyle{ a_n<a_{n+1} }[/math] לכל [math]\displaystyle{ n\in\mathbb N }[/math].
(א) לכל [math]\displaystyle{ n\in\mathbb N }[/math] תהי [math]\displaystyle{ P(n) }[/math] הטענה [math]\displaystyle{ 1\le a_n<2 }[/math]. בסיס: [math]\displaystyle{ a_1=1 }[/math], ולכן [math]\displaystyle{ 1\le a_1<2 }[/math], כלומר [math]\displaystyle{ P(1) }[/math] נכונה.
צעד: יהי [math]\displaystyle{ n\in\mathbb N }[/math] כך ש [math]\displaystyle{ P(n) }[/math] נכונה, כלומר [math]\displaystyle{ 1\le a_n<2 }[/math]. צריך להוכיח את [math]\displaystyle{ P(n+1) }[/math], כלומר [math]\displaystyle{ 1\le a_{n+1}<2 }[/math].
מהנחת האינדוקציה [math]\displaystyle{ a_n\ge1>0 }[/math], ולכן [math]\displaystyle{ |a_n|=a_n }[/math] ו־[math]\displaystyle{ a_{n+1}=1+\frac{a_n}2 }[/math]. נחלק את [math]\displaystyle{ 1\le a_n<2 }[/math] ב־[math]\displaystyle{ 2 }[/math] ונוסיף [math]\displaystyle{ 1 }[/math]: [math]\displaystyle{ \frac32\le1+\frac{a_n}2<2 }[/math], כלומר [math]\displaystyle{ \frac32\le a_{n+1}<2 }[/math], ובפרט [math]\displaystyle{ 1\le a_{n+1}<2 }[/math]. לכן [math]\displaystyle{ P(n+1) }[/math] נכונה.
לפי משפט האינדוקציה (2.5.1) [math]\displaystyle{ 1\le a_n<2 }[/math] לכל [math]\displaystyle{ n\in\mathbb N }[/math].
(ב) יהי [math]\displaystyle{ n\in\mathbb N }[/math]. לפי (א) [math]\displaystyle{ a_n>0 }[/math], ולכן [math]\displaystyle{ a_{n+1}=1+\frac{a_n}2 }[/math]. מכאן [math]\displaystyle{ a_{n+1}-a_n=1-\frac{a_n}2 }[/math] [math]\displaystyle{ =\frac{2-a_n}2>0 }[/math], כי לפי (א) [math]\displaystyle{ a_n<2 }[/math]. לכן [math]\displaystyle{ a_n<a_{n+1} }[/math]. כאן אין צורך באינדוקציה נוספת: החסם מ־(א) מספיק.
למה הנחת האינדוקציה כוללת גם את החסם התחתון? הפונקציה [math]\displaystyle{ 1+\frac{|x|}2 }[/math] אינה עולה בכל הישר, ומהנתון [math]\displaystyle{ a_n<2 }[/math] לבדו לא נובע [math]\displaystyle{ a_{n+1}<2 }[/math]: עבור [math]\displaystyle{ a_n=-3 }[/math] היינו מקבלים [math]\displaystyle{ a_{n+1}=\frac52 }[/math]. החסם [math]\displaystyle{ a_n\ge1 }[/math] מאפשר להוריד את הערך המוחלט, ואחרי זה רק מחלקים במספר חיובי ומוסיפים קבוע, פעולות ששומרות על אי־השוויונות.
בבוחן המקורי ממשיכים: הסדרה עולה וחסומה, ולכן לפי משפט הסדרות המונוטוניות (2.9.2, בהמשך הפרק) קיים [math]\displaystyle{ L\in\mathbb R }[/math] כך ש [math]\displaystyle{ a_n\to L }[/math]. השאפת שני האגפים של [math]\displaystyle{ a_{n+1}=1+\frac{a_n}2 }[/math] (לפי 2.1.15, 2.4.2 ויחידות הגבול 2.1.11) נותנת [math]\displaystyle{ L=1+\frac L2 }[/math], כלומר [math]\displaystyle{ L=2 }[/math].
מקור: בוחן 1, 88-132 תשע"ה (15.12.2014), שאלה 3א: הדף "88-132 אינפי 1 סמסטר א' תשעה/בוחן 1" (ארז הקליד את הבוחן; בשאלה המקורית: "הוכיחו כי הסדרה מתכנסת ומצאו את גבולה"), והפתרון של המתרגל איתמר שטיין בדף "88-132 אינפי 1 סמסטר א' תשעה/בוחן 1 - פתרון" (חיובית, עולה באינדוקציה, חסומה מלעיל ע"י 2 באינדוקציה, [math]\displaystyle{ L=2 }[/math]); גרסה קרובה: בוחן אמצע תשע"א (6.12.10, ארז מתרגל), שאלה 12ג (שם נתון שהסדרה מתכנסת, ומחשבים רק את הגבול; [math]\displaystyle{ L=2 }[/math]) (W6c); מאגר 2.9-19 (◆, ק' 1–2, בוחן ✓ 3 דק')
דוגמה 2: ברנולי בפעולה: [math]\displaystyle{ 1.001^n\to\infty }[/math]
ממבט ראשון נדמה שהסדרה [math]\displaystyle{ 1.001^n }[/math] שואפת ל־[math]\displaystyle{ 1 }[/math], כי הבסיס קרוב ל־[math]\displaystyle{ 1 }[/math]. (א) הוכיחו בעזרת אי-שוויון ברנולי כי [math]\displaystyle{ 1.001^n\to\infty }[/math]. (ב) מצאו [math]\displaystyle{ K\in\mathbb N }[/math] כך שלכל [math]\displaystyle{ n>K }[/math] מתקיים [math]\displaystyle{ 1.001^n>1000 }[/math].
נפעיל את אי-שוויון ברנולי עם [math]\displaystyle{ x=0.001 }[/math] (התנאי [math]\displaystyle{ x>-1 }[/math] מתקיים). לכל [math]\displaystyle{ n\in\mathbb N }[/math]: [math]\displaystyle{ 1.001^n=(1+0.001)^n }[/math] [math]\displaystyle{ \ge1+0.001n=1+\frac{n}{1000} }[/math].
(א) יהי [math]\displaystyle{ M>0 }[/math]. לפי תכונת ארכימדס קיים [math]\displaystyle{ K\in\mathbb N }[/math] כך ש [math]\displaystyle{ K>1000M }[/math]. יהי [math]\displaystyle{ n>K }[/math]. אזי [math]\displaystyle{ 1.001^n\ge1+\frac{n}{1000}>\frac{n}{1000} }[/math] [math]\displaystyle{ >\frac{K}{1000}>M }[/math]. לכן לפי ההגדרה [math]\displaystyle{ 1.001^n\to\infty }[/math]. זה בדיוק חצי סנדביץ': הסדרה גדולה או שווה לסדרה [math]\displaystyle{ 1+\frac{n}{1000} }[/math], ששואפת לאינסוף.
(ב) [math]\displaystyle{ 1+\frac{n}{1000}>1000 }[/math] אם ורק אם [math]\displaystyle{ n>999000 }[/math]. לכן [math]\displaystyle{ K=999000 }[/math] מתאים: לכל [math]\displaystyle{ n>K }[/math] מתקיים [math]\displaystyle{ 1.001^n\ge1+\frac{n}{1000}>1000 }[/math].
ברנולי נותן מקום שעובד, לא את הקטן ביותר: בפועל [math]\displaystyle{ 1.001^n>1000 }[/math] כבר לכל [math]\displaystyle{ n\ge6912 }[/math]. להוכחה שהסדרה שואפת לאינסוף זה לא משנה.
אותו נימוק עם [math]\displaystyle{ x=q-1>0 }[/math] מראה שלכל [math]\displaystyle{ q>1 }[/math] מתקיים [math]\displaystyle{ q^n\ge1+n(q-1) }[/math], ולכן [math]\displaystyle{ q^n\to\infty }[/math]. זו מסקנה 2.6.2(א), ובסרטון 17 המרצה משתמש בברנולי גם בהוכחת המשפט הכללי 2.6.1.
מקור: תמליל 17 (hFa7Nv5o05M) 00:39–01:08 (t=39s): "מה לגבי 1.001 בחזקת n? ממבט ראשון נוטים לחשוב שזה שואף לאחד", ו־02:34 (t=154s): "נשתמש באי שוויון ברנולי"; מחברת ההרצאות תשע"ז עמ' 25 (G1-52: q>1 ⇒ q^n→∞ דרך ברנולי, בוחן ✓); לוח תשפ"ד ל6 ע30 (R5-2.20: "a=1+r, ברנולי, ולפי חצי סנדוויץ'"); מאגר 2.6-01 (◆, ק' 1, בוחן ✓); "צריך למצוא N שעובד ולא דווקא את הכי טוב": מחברת עמ' 11 (G1-22)
דוגמה 3: בסיס שאינו [math]\displaystyle{ 1 }[/math]: [math]\displaystyle{ n^n\ge(n+1)! }[/math]
הוכיחו כי לכל מספר טבעי [math]\displaystyle{ n\ge3 }[/math] מתקיים [math]\displaystyle{ n^n\ge(n+1)! }[/math].
הטענה אינה נכונה עבור [math]\displaystyle{ n=1,2 }[/math] ([math]\displaystyle{ 1<2! }[/math] ו־[math]\displaystyle{ 4<3! }[/math]), ולכן הבסיס הוא [math]\displaystyle{ n=3 }[/math]. פורמלית, מפעילים את משפט האינדוקציה על הטענות [math]\displaystyle{ Q(k) }[/math]: "[math]\displaystyle{ (k+2)^{k+2}\ge(k+3)! }[/math]", [math]\displaystyle{ k\in\mathbb N }[/math]; [math]\displaystyle{ Q(1) }[/math] היא הטענה עבור [math]\displaystyle{ n=3 }[/math], והצעד מ־[math]\displaystyle{ Q(k) }[/math] ל־[math]\displaystyle{ Q(k+1) }[/math] הוא הצעד מ־[math]\displaystyle{ n=k+2 }[/math] ל־[math]\displaystyle{ n+1 }[/math].
צעד: יהי [math]\displaystyle{ n\ge3 }[/math] טבעי כך ש [math]\displaystyle{ n^n\ge(n+1)! }[/math]. צריך להוכיח [math]\displaystyle{ (n+1)^{n+1}\ge(n+2)! }[/math].
נשאיר בצד גורם [math]\displaystyle{ (n+1)^2 }[/math], נשתמש ב־[math]\displaystyle{ n+1>n>0 }[/math] ואחר כך בהנחת האינדוקציה: [math]\displaystyle{ (n+1)^{n+1}=(n+1)^2(n+1)^{n-1} }[/math] [math]\displaystyle{ \ge(n+1)^2n^{n-1} }[/math] [math]\displaystyle{ =\frac{(n+1)^2}{n}\cdot n^n }[/math] [math]\displaystyle{ \ge\frac{(n+1)^2}{n}\cdot(n+1)! }[/math].
נשאר להראות ש [math]\displaystyle{ \frac{(n+1)^2}{n}\ge n+2 }[/math]. אחרי כפל ב־[math]\displaystyle{ n>0 }[/math] זה [math]\displaystyle{ n^2+2n+1\ge n^2+2n }[/math], כלומר [math]\displaystyle{ 1\ge0 }[/math], וזה נכון. לכן [math]\displaystyle{ (n+1)^{n+1}\ge(n+2)\cdot(n+1)! }[/math] [math]\displaystyle{ =(n+2)! }[/math].
למה לא הניסיון הישיר? הפירוק [math]\displaystyle{ (n+1)^{n+1}=(n+1)\cdot(n+1)^n }[/math] והנחת האינדוקציה נותנים רק [math]\displaystyle{ (n+1)^{n+1}\ge(n+1)\cdot(n+1)! }[/math], עם הגורם [math]\displaystyle{ n+1 }[/math] במקום [math]\displaystyle{ n+2 }[/math]; לכן מפצלים את החזקה כך שיישאר גורם [math]\displaystyle{ (n+1)^2 }[/math].
מקור: לוח התרגול 12.11.20, אינפי 1 מדמ"ח תשפ"א (R1-X32, פתרון מלא של ארז: בסיס 3^3>4!, הפיצול (n+1)^2(n+1)^{n-1}, "ונשאר (n+1)^2/n ≥ n+2"); מאגר 2.5-04 (◆, ק' 3, בוחן ✓ 8 דק')
דוגמה 4: אינדוקציה בלי נוסחאות: ריצוף לוח בחתיכות L
יהי [math]\displaystyle{ n\in\mathbb N }[/math]. מלוח משבצות בגודל [math]\displaystyle{ 2^n\times2^n }[/math] הוסרה משבצת אחת, במקום כלשהו. הוכיחו שאפשר לכסות את שאר הלוח, בלי חפיפות, בחתיכות בצורת L שכל אחת מהן מכסה שלוש משבצות (מותר לסובב את החתיכות).
לכל [math]\displaystyle{ n\in\mathbb N }[/math] תהי [math]\displaystyle{ P(n) }[/math] הטענה: "בכל לוח [math]\displaystyle{ 2^n\times2^n }[/math] שהוסרה ממנו משבצת אחת, בכל מקום שהוא, אפשר לכסות את השאר בחתיכות L, בלי חפיפות". המילים "בכל מקום" חשובות: בצעד נפעיל את [math]\displaystyle{ P(n) }[/math] על לוחות שהמשבצת החסרה בהם נמצאת במקומות שונים.
בסיס[math]\displaystyle{ n=1 }[/math]: לוח [math]\displaystyle{ 2\times2 }[/math] בלי משבצת אחת הוא בדיוק חתיכת L אחת.
צעד: יהי [math]\displaystyle{ n\in\mathbb N }[/math] כך ש [math]\displaystyle{ P(n) }[/math] נכונה, ויהי לוח [math]\displaystyle{ 2^{n+1}\times2^{n+1} }[/math] שחסרה בו משבצת. נחלק אותו לארבעה רבעים; הצלע של כל רבע היא [math]\displaystyle{ \frac{2^{n+1}}{2}=2^n }[/math].
המשבצת החסרה נמצאת בדיוק באחד הרבעים. נניח חתיכת L אחת במרכז הלוח כך שתכסה, בכל אחד משלושת הרבעים האחרים, את המשבצת הסמוכה למרכז (שלוש המשבצות האלה הן שלוש מתוך ארבע המשבצות של ריבוע ה־[math]\displaystyle{ 2\times2 }[/math] שבמרכז הלוח, ולכן הן אכן צורת L; החתיכה הירוקה באיור).
עכשיו כל אחד מארבעת הרבעים הוא לוח [math]\displaystyle{ 2^n\times2^n }[/math] שבו משבצת אחת בדיוק חסרה או כבר מכוסה, ולפי [math]\displaystyle{ P(n) }[/math] אפשר לכסות את שאר המשבצות שלו בלי חפיפות. הכיסויים של רבעים שונים אינם חופפים זה לזה, ואף אחד מהם אינו מכסה משבצת של החתיכה שבמרכז (ברבע שלה היא נחשבה חסרה). לכן, יחד עם החתיכה שבמרכז, כיסינו בלי חפיפות את כל הלוח פרט למשבצת החסרה, כלומר [math]\displaystyle{ P(n+1) }[/math] נכונה, ולפי משפט האינדוקציה הטענה נכונה לכל [math]\displaystyle{ n\in\mathbb N }[/math].
ההוכחה היא גם אלגוריתם ("כל פעם אני מחלק ל־4", בסרטון 16:00): בלוח [math]\displaystyle{ 8\times8 }[/math] שבאיור מניחים קודם את החתיכה הירוקה, אחר כך ארבע חתיכות אפורות במרכזי הלוחות [math]\displaystyle{ 4\times4 }[/math], ולבסוף [math]\displaystyle{ 16 }[/math] חתיכות בלוחות [math]\displaystyle{ 2\times2 }[/math], ובסך הכול [math]\displaystyle{ \frac{64-1}{3}=21 }[/math] חתיכות.
מקור: תמליל 16 (n6xkPhKmhQo) 12:07–16:10 (t=727s): הצגת הבעיה 12:07–12:42, הבסיס 12:45–13:09, הצעד 13:13–15:08 ("נניח אותה ככה שתהיה לה משבצת אחת בכל אחד מהלוחות שלא חסרה בו משבצת", 14:46), ההמחשה על לוח 4×4 ב־15:18–15:52, "כל פעם אני מחלק ל4" ב־16:00 (t=960s); מאגר 2.5-06 (◆, הריצוף אינו מתאים לבוחן)
טעויות נפוצות
לחשוב שבצעד מניחים את מה שצריך להוכיח ("רגע, זה בדיוק מה שהיינו צריכים להוכיח!", בסרטון 8:19–8:27): בצעד מניחים את [math]\displaystyle{ P(n) }[/math] רק עבור [math]\displaystyle{ n }[/math] אחד שנתון ("יהי [math]\displaystyle{ n\in\mathbb N }[/math] כך ש [math]\displaystyle{ P(n) }[/math] נכונה") ומוכיחים את [math]\displaystyle{ P(n+1) }[/math], ולא מניחים שהטענה נכונה לכל [math]\displaystyle{ n }[/math].
לשכוח את הבסיס או לבדוק אותו במקום הלא נכון: לטענה "[math]\displaystyle{ 2n+1 }[/math] זוגי" הצעד נכון (אם [math]\displaystyle{ 2n+1 }[/math] זוגי, גם [math]\displaystyle{ 2(n+1)+1=(2n+1)+2 }[/math] זוגי), ובכל זאת הטענה שקרית לכל [math]\displaystyle{ n }[/math] (המספר [math]\displaystyle{ 2n+1 }[/math] אי־זוגי): מה שחסר הוא הבסיס, כי [math]\displaystyle{ P(1) }[/math] שקרית; וכשהטענה נכונה רק החל ממקום מסוים, כמו [math]\displaystyle{ n^n\ge(n+1)! }[/math] החל מ־[math]\displaystyle{ n=3 }[/math], הבסיס הוא המקום הזה ובצעד מניחים [math]\displaystyle{ n\ge3 }[/math].
להפעיל את אי-שוויון ברנולי בלי לבדוק ש [math]\displaystyle{ x>-1 }[/math]: ההנחה משמשת בהוכחה כשכופלים את הנחת האינדוקציה ב־[math]\displaystyle{ 1+x>0 }[/math] (בסרטון 10:00–10:16), ובלעדיה המסקנה עלולה להיכשל, למשל עבור [math]\displaystyle{ x=-4 }[/math] ו־[math]\displaystyle{ n=3 }[/math]: [math]\displaystyle{ (1-4)^3=-27 }[/math] ואילו [math]\displaystyle{ 1+3\cdot(-4)=-11 }[/math].
להסיק מהנחת האינדוקציה [math]\displaystyle{ a_n<b_n }[/math] ש [math]\displaystyle{ f(a_n)<f(b_n) }[/math] בלי לבדוק ש [math]\displaystyle{ f }[/math] עולה בתחום שבו נמצאים [math]\displaystyle{ a_n }[/math] ו־[math]\displaystyle{ b_n }[/math] (בדוגמה 1 הפונקציה [math]\displaystyle{ 1+\frac{|x|}2 }[/math] אינה עולה בכל הישר, ולכן הנחת האינדוקציה כוללת גם את [math]\displaystyle{ a_n\ge1 }[/math]: בקרן [math]\displaystyle{ [1,\infty) }[/math] היא עולה); בפתרון מבחן קיץ תשפ"א (מדמ"ח), בשאלה שבה [math]\displaystyle{ a_{n+1}\le a_n(1-a_n) }[/math] ומוכיחים [math]\displaystyle{ a_n<\frac1n }[/math], המרצה מזהיר: "אסור להגיד כי לפי הנחת האינדוקציה [math]\displaystyle{ a_n(1-a_n)<\frac1n(1-\frac1n) }[/math]", כי [math]\displaystyle{ x-x^2 }[/math] יורדת בקרן [math]\displaystyle{ [\frac12,\infty) }[/math], ולכן קודם מוודאים ששני המספרים בקטע [math]\displaystyle{ [0,\frac12] }[/math], שבו היא עולה.
לקפוץ לאינדוקציה כשאין בה צורך: [math]\displaystyle{ n^2-2n+2=(n-1)^2+1>0 }[/math] מוכח בשורה אחת (בסרטון 1:13–1:39), ובסדרת הנסיגה [math]\displaystyle{ a_{n+1}=a_n^2-a_n+1 }[/math] ההפרש [math]\displaystyle{ a_{n+1}-a_n=(a_n-1)^2\ge0 }[/math] מראה מיד שהסדרה עולה ("10 נקודות מתנה, בלי אינדוקציה", בלוח תרגול של ארז על שאלת מבחן).
לתרגול
מועד מיוחד תשע"ב (מתמטיקה) · שאלה 2א: [math]\displaystyle{ a_1=4 }[/math], [math]\displaystyle{ a_{n+1}=\sqrt{2+a_n} }[/math], יורדת באינדוקציה (הפתרון המלא, כולל הגבול, בדף סדרות מונוטוניות) (פתרון).
מועד א' תשע"ז (מתמטיקה) · שאלה 3: [math]\displaystyle{ a_{n+1}=2a_n-\frac1{a_n} }[/math], [math]\displaystyle{ a_1>1 }[/math]; באינדוקציה [math]\displaystyle{ a_n>1 }[/math], ולכן עולה (פתרון).
מבחן דמה תשע"ז (מתמטיקה) · שאלה 3א: סדרה חיובית עם [math]\displaystyle{ \frac{a_n+a_{n+2}}{a_{n+1}}\ge d>2 }[/math] ו־[math]\displaystyle{ a_1<a_2 }[/math], עולה באינדוקציה (פתרון). קושי 3.
מועד א' קיץ תשפ"א (מדמ"ח) · שאלה 3: [math]\displaystyle{ a_1=2 }[/math], [math]\displaystyle{ a_{n+1}=\frac{2a_n-1}{a_n+4} }[/math]; אינדוקציה ל־[math]\displaystyle{ a_n>-4 }[/math] נתקעת, ומוכיחים את החזק יותר [math]\displaystyle{ a_n>-1 }[/math] (פתרון).
מערך תרגול · מערך התרגול של הקורס (תשע"ב), פרק הסדרות.
סדרות מונוטוניות ונוסחאות נסיגה · התרגיל השלישי: [math]\displaystyle{ a_{n+1}=\frac c2+\frac{a_n^2}2 }[/math], מונוטוניות באינדוקציה, עם פתרון.
![ריצוף לוח משבצות שחסרה בו משבצת אחת (המסומנת ב־X) בחתיכות בצורת L, כמו בדוגמה 4. משמאל, הצעד של האינדוקציה (כאן [math]\displaystyle{ n=2 }[/math]): לוח [math]\displaystyle{ 2^{n+1}\times2^{n+1} }[/math] מתחלק לארבעה רבעים בגודל [math]\displaystyle{ 2^n\times2^n }[/math]. המשבצת החסרה נמצאת באחד מהם, והחתיכה הירוקה שבמרכז מכסה משבצת אחת בכל אחד משלושת הרבעים האחרים. עכשיו בכל רבע חסרה (או כבר מכוסה) משבצת אחת בדיוק, ולכן לפי הנחת האינדוקציה [math]\displaystyle{ P(n) }[/math] אפשר לרצף כל רבע. מימין, הריצוף המלא של לוח [math]\displaystyle{ 8\times8 }[/math] ב־[math]\displaystyle{ 21 }[/math] חתיכות, שמתקבל מחזרה על אותו צעד: החתיכה הירוקה מונחת ראשונה (level 1), החתיכות האפורות במרכזי ארבעת הלוחות [math]\displaystyle{ 4\times4 }[/math] (level 2), והחתיכות התכולות ממלאות את שישה־עשר הלוחות [math]\displaystyle{ 2\times2 }[/math], שהם הבסיס (level 3).](/index.php/%D7%A7%D7%95%D7%91%D7%A5:Infi1-c2-09.png)