Η μαθηματική επαγωγή είναι ένας ειδικός τρόπος απόδειξης μιας μαθηματικής αλήθειας. Μπορεί να χρησιμοποιηθεί για να αποδειχθεί ότι κάτι ισχύει για όλους τους φυσικούς αριθμούς (όλους τους θετικούς ακέραιους αριθμούς). Η ιδέα είναι ότι
- Κάτι ισχύει για την πρώτη περίπτωση
- Το ίδιο πράγμα ισχύει πάντα και για την επόμενη περίπτωση
τότε
- Το ίδιο πράγμα ισχύει για κάθε περίπτωση
Στην προσεκτική γλώσσα των μαθηματικών:
- Δηλώστε ότι η απόδειξη θα γίνει με επαγωγή επί του n {\displaystyle n}
. ( n {\displaystyle n} είναι η επαγωγική μεταβλητή.) - Δείξτε ότι η δήλωση είναι αληθής όταν το n {\displaystyle n} είναι 1.
- Υποθέστε ότι η δήλωση είναι αληθής για κάθε φυσικό αριθμό n {\displaystyle n} . (Αυτό ονομάζεται βήμα επαγωγής).
- Δείξτε τότε ότι η δήλωση είναι αληθής για τον επόμενο αριθμό, n + 1 {\displaystyle n+1}
.
Επειδή είναι αληθές για το 1, τότε είναι αληθές για το 1+1 (=2, από το βήμα επαγωγής), τότε είναι αληθές για το 2+1 (=3), τότε είναι αληθές για το 3+1 (=4), και ούτω καθεξής.
Ένα παράδειγμα απόδειξης μέσω επαγωγής:
Αποδείξτε ότι για όλους τους φυσικούς αριθμούς n:
1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)} 
Απόδειξη:
Πρώτον, η δήλωση μπορεί να γραφεί: για όλους τους φυσικούς αριθμούς n
2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} 
Με επαγωγή στο n,
Πρώτον, για n=1:
2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} 
,
έτσι αυτό είναι αλήθεια.
Στη συνέχεια, υποθέστε ότι για κάποια n=n0 η δήλωση είναι αληθής. Δηλαδή,:
2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} 
Τότε για n=n0+1:
2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k} 
μπορεί να ξαναγραφεί
2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)} 
Δεδομένου ότι 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ), {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} 
2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} 
Επομένως, η απόδειξη είναι σωστή.
