אינדוקציה: בסיס, מעבר וכשל

בסיס: עבור $n=1$ מתקבל $1=1$. מעבר: נניח שהסכום עד $2n-1$ הוא $n^2$. מוסיפים את האיבר הבא $2n+1$ ומקבלים $n^2+2n+1=(n+1)^2$. זה בדיוק הסכום עבור האינדקס הבא. לכן הטענה נכונה לכל $n\ge1$.

השיטה: שימוש מפורש בהנחת האינדוקציה. אם $3^n\ge2n+1$, אז $3^{n+1}=3\cdot3^n\ge6n+3\ge2n+3=2(n+1)+1$. האי־שוויון האחרון תקף כי $n\ge1$. יחד עם הבסיס מתקבלת הוכחה מלאה. בדיקת מקרה נוסף אינה מוכיחה מעבר כללי.

השיטה: סכום חשבוני ובדיקת המעבר הראשון שנכשל. באגף שמאל יש $n+1$ איברים, ולכן סכומם $\frac{5n(n+1)}2$. ההפרש בין האגפים הוא $\frac{(n-1)(n-2)}2$. השוויון מתקיים בדיוק כאשר $n=1$ או $n=2$. בפרט $P(2)$ נכונה ו־$P(3)$ שגויה, ולכן צעד האינדוקציה הכללי נכשל. רק ההיגד השני מתאים לכל המסקנות.

השיטה: הפרדה בין בסיס לצעד. סכום האי־זוגיים הוא $n^2$, ולכן אין $n$ טבעי שעבורו $n^2=n^2+10$. עם זאת, מתוך ההנחה הפורמלית $P(n)$, הוספת $2n+1$ נותנת $(n+1)^2+10$, ולכן המעבר שומר על צורת הטענה. גם מבחינה לוגית הגרירה תקפה כאשר ההנחה שגויה. אין בסיס תקף, ולכן אין הוכחת אינדוקציה לטענה עצמה. ההיגד השני הוא הנכון.