Μαθηματική επαγωγή — αρχή, βήματα και παραδείγματα

Η μαθηματική επαγωγή είναι μια μέθοδος απόδειξης για να δείξουμε ότι μια πρόταση είναι αληθής για κάθε ακέραιο από ένα αρχικό σημείο και μετά. Για να αποδείξεις έναν ισχυρισμό για όλα τα $n \ge n_0$, δείχνεις ότι η πρώτη περίπτωση είναι αληθής και έπειτα ότι η αλήθεια σε έναν ακέραιο συνεπάγεται την αλήθεια στον επόμενο.

Αν και τα δύο μέρη είναι σωστά, τότε η πρόταση ισχύει για κάθε ακέραιο στο δοσμένο πεδίο. Αυτή είναι όλη η ιδέα.

Πώς λειτουργεί η μαθηματική επαγωγή

Γράψε τον ισχυρισμό ως $P(n)$. Τότε η επαγωγή έχει την εξής δομή:

1. Απόδειξε τη βάση της επαγωγής: δείξε ότι το $P(n_0)$ είναι αληθές.
2. Απόδειξε το βήμα επαγωγής: δείξε ότι αν το $P(k)$ είναι αληθές για έναν αυθαίρετο ακέραιο $k \ge n_0$, τότε και το $P(k+1)$ είναι επίσης αληθές.

Μόλις γίνουν αυτά, μπορείς να συμπεράνεις ότι το $P(n)$ είναι αληθές για κάθε ακέραιο $n \ge n_0$.

Η λογική είναι διαδοχική. Η βάση της επαγωγής ξεκινά την αλυσίδα και το βήμα επαγωγής κρατά την αλυσίδα σε κίνηση, έναν ακέραιο τη φορά.

Γιατί έχουν σημασία και η βάση και το βήμα επαγωγής

Η βάση της επαγωγής σου δίνει την πρώτη αληθή πρόταση. Το βήμα επαγωγής λέει ότι η αλήθεια περνά από έναν ακέραιο στον επόμενο.

Άρα, αν το $P(n_0)$ είναι αληθές, τότε και το $P(n_0 + 1)$ είναι αληθές. Έπειτα είναι αληθές και το $P(n_0 + 2)$, και ούτω καθεξής. Η επαγωγή δεν παραλείπει το αρχικό σημείο και δεν παραλείπει τον σύνδεσμο από τη μία περίπτωση στην επόμενη.

Λυμένο παράδειγμα: απόδειξη τύπου αθροίσματος με επαγωγή

Ένα κλασικό παράδειγμα είναι ο τύπος

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

για όλους τους ακεραίους $n \ge 1$.

Θέτουμε

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Βάση της επαγωγής

Πάρε $n = 1$. Το αριστερό μέλος είναι $1$, και το δεξί μέλος είναι

$$\frac{1(1+1)}{2} = 1$$

Άρα το $P(1)$ είναι αληθές.

Βήμα επαγωγής

Υπόθεσε ότι το $P(k)$ είναι αληθές για κάποιον αυθαίρετο ακέραιο $k \ge 1$. Αυτό σημαίνει ότι

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Τώρα απόδειξε το $P(k+1)$. Ξεκίνα από το αριστερό μέλος για το $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

Χρησιμοποιώντας την επαγωγική υπόθεση,

$$\frac{k(k+1)}{2} + (k+1)$$

Παράγοντας κοινό τον όρο $(k+1)$:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Έπειτα απλοποίησε:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

Αυτό είναι ακριβώς ο τύπος με $n = k+1$. Άρα το $P(k+1)$ είναι αληθές.

Αφού αποδείχθηκαν και η βάση και το βήμα επαγωγής, ο τύπος ισχύει για όλους τους ακεραίους $n \ge 1$.

Πότε να χρησιμοποιείς τη μαθηματική επαγωγή

Η επαγωγή είναι χρήσιμη όταν μια πρόταση εξαρτάται από μια ακέραια παράμετρο και κάθε περίπτωση συνδέεται φυσικά με μια προηγούμενη. Αυτό συμβαίνει συχνά με αθροίσματα, προτάσεις διαιρετότητας, ανισότητες, αναδρομικές σχέσεις και αποδείξεις αλγορίθμων.

Πρώτα, εντόπισε τη σωστή αρχική τιμή. Κάποιοι ισχυρισμοί ξεκινούν από $n = 0$, κάποιοι από $n = 1$, και κάποιοι έχουν νόημα μόνο για μεγαλύτερους ακεραίους.

Έπειτα έλεγξε ποια είναι η επόμενη έγκυρη περίπτωση. Το συνηθισμένο βήμα είναι από το $k$ στο $k+1$, αλλά αν η πρόταση αφορά μόνο άρτιους ακεραίους, τότε ένα βήμα από το $k$ στο $k+2$ μπορεί να είναι η σωστή εκδοχή.

Συνηθισμένα λάθη σε αποδείξεις με επαγωγή

Απόδειξη μόνο της βάσης

Η βάση της επαγωγής ελέγχει μόνο την πρώτη τιμή. Από μόνη της, δεν αποδεικνύει την πρόταση για τους επόμενους ακεραίους.

Χρήση λανθασμένης αρχικής τιμής

Αν ο ισχυρισμός προορίζεται για όλα τα $n \ge 2$, το να αποδείξεις μόνο το $P(1)$ δεν βοηθά. Η βάση πρέπει να ταιριάζει με το πραγματικό πεδίο του ισχυρισμού.

Απρόσεκτη χρήση της επαγωγικής υπόθεσης

Στο βήμα επαγωγής, υποθέτεις το $P(k)$ για έναν αυθαίρετο ακέραιο $k$ στο έγκυρο πεδίο. Δεν υποθέτεις ότι έχει ήδη αποδειχθεί όλο το θεώρημα.

Απόδειξη της λάθος επόμενης περίπτωσης

Αν το θεώρημά σου χρειάζεται βήμα $k \to k+1$, η απόδειξη ενός διαφορετικού βήματος δεν ολοκληρώνει το επιχείρημα, εκτός αν εξηγήσεις γιατί αυτό το διαφορετικό βήμα αρκεί.

Μια χρήσιμη επέκταση: ισχυρή επαγωγή

Μερικές φορές, για να αποδείξεις το $P(k+1)$ χρειάζεσαι περισσότερα από το $P(k)$. Σε αυτή την περίπτωση, η ισχυρή επαγωγή σου επιτρέπει να υποθέσεις όλες τις προηγούμενες περιπτώσεις μέχρι το $k$ και έπειτα να αποδείξεις την επόμενη.

Η ιδέα είναι στενά συγγενική, αλλά η υπόθεση είναι ισχυρότερη. Είναι χρήσιμη, για παράδειγμα, όταν μια απόδειξη εξαρτάται από τη διάσπαση ενός αριθμού σε μικρότερα μέρη.

Δοκίμασε τη δική σου εκδοχή

Πάρε τον ισχυρισμό

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

και απόδειξέ τον για όλους τους ακεραίους $n \ge 1$ χρησιμοποιώντας την ίδια δομή: πρώτα η βάση και έπειτα το βήμα από το $k$ στο $k+1$. Αν μπορείς να γράψεις αυτή την απόδειξη καθαρά, τότε συνήθως η μέθοδος έχει γίνει κατανοητή.