אינדוקציה: מבוא ומבנה ההוכחה

שלב 1: בסיס. מציבים $n = 1$ ומוכיחים שהטענה נכונה.
שלב 2: הנחה. מניחים שהטענה נכונה עבור $n = k$ ורושמים מה ההנחה במפורש.
שלב 3: מעבר. מוכיחים שמההנחה עבור $n = k$ נובע שהטענה נכונה גם עבור $n = k + 1$.

שלב המעבר מוכיח: אם הטענה נכונה עבור $n = k$, אז היא נכונה גם עבור $n = k + 1$.
אבל אם אף פעם לא הוכחנו שהטענה נכונה לאיזשהו $n$ ספציפי, שלב המעבר לא עוזר.
דוגמה: שלב המעבר אומר 'אם הגעת למדרגה $k$, תגיע גם ל-$k+1$'. אבל אם לא הוכחת שהגעת למדרגה 1, לא ניתן להסיק כלום.
שלב הבסיס נותן את נקודת ההתחלה הקונקרטית.

הנחת האינדוקציה: מניחים (בלי להוכיח) שהטענה נכונה עבור $n = k$ כלשהו.
מטרת שלב המעבר: להשתמש בהנחה כדי להוכיח שהטענה נכונה גם עבור $n = k + 1$.
הנחת האינדוקציה היא כלי בלבד. לא מוכיחים אותה, משתמשים בה.

לאחר שלב המעבר כותבים: "מהנחה שהטענה נכונה עבור $n = k$ נובע שנכונה גם עבור $n = k + 1$, הטענה נכונה לכל $n$ טבעי".

לפעמים הטענה מוגדרת רק מ-$n = 2$ ומעלה, ואז הבסיס צריך להיות $n = 2$ ולא $n = 1$.
חשוב לזהות מהו הערך הראשון של $n$ שעבורו הטענה מוגדרת.