Μαθηματική επαγωγή

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

Η αρχή

Η βασική αρχή είναι ότι την πρόταση την αποδεικνύουμε για κάποιο πρώτο στοιχείο, στους φυσικούς αριθμούς αυτό είναι συνήθως το ν = 1. Αυτό το αποδεικνύουμε με απλή αντικατάσταση. Στο επόμενο, επαγωγικό βήμα αποδεικνύουμε τη συνεπαγωγή «αν η πρόταση ισχύει για ν = κ, τότε ισχύει και για ν = κ + 1».

Από αυτά τα δύο βήματα μπορούμε να συμπεράνουμε ότι η δοσμένη πρόταση ισχύει για όλα τα ν (από κάποιο σύνολο με το οποίο δουλεύουμε εκείνη τη στιγμή). Γιατί συμβαίνει αυτό; Στην αρχή αποδεικνύουμε ότι η πρόταση ισχύει για ν = 1. Ταυτόχρονα ξέρουμε ότι αν η πρόταση ισχύει για ν = κ, ισχύει και για ν = κ + 1. Επιλέγουμε λοιπόν κ = 1. Ξέρουμε ότι για κ = 1 η πρόταση ισχύει και ξέρουμε επίσης ότι ισχύει για κ + 1 = 2. Αυτή τη στιγμή ξέρουμε ότι η πρόταση ισχύει για κ = 2. Αλλά επειδή ισχύει και για κ + 1, πρέπει να ισχύει και για 2 + 1 = 3. Και ούτω καθεξής.

Πρώτο παράδειγμα

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

$$2\mid 2\nu$$

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

$$2\mid 2\nu +2;\nu \in {\mathbb{N}}^{\ast }$$

Αυτό πρέπει να αποδείξουμε στο πρώτο παράδειγμα, δηλαδή ότι το δύο διαιρεί την παράσταση 2ν + 2 – ακριβώς αυτό αντιστοιχεί στην αρχική διατύπωση με λόγια «αν σε οποιονδήποτε άρτιο αριθμό προσθέσουμε το δύο, παίρνουμε πάλι άρτιο αριθμό».

Στο πρώτο βήμα της επαγωγής το αποδεικνύουμε για το πρώτο στοιχείο, για το ένα. Αντικαθιστούμε στην παράσταση ν = 1:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

Το δύο διαιρεί ακριβώς το τέσσερα, άρα για το πρώτο στοιχείο ισχύει. Στη συνέχεια έρχεται το επαγωγικό βήμα, όπου πρέπει να αποδείξουμε ότι αν ισχύει για το κ-οστό στοιχείο, τότε ισχύει και για το (κ + 1)-οστό στοιχείο. Στην αρχή υποθέτουμε ότι ισχύει η υπόθεσή μας, δηλαδή ν = κ:

$$2\mid 2\kappa +2$$

Για αυτή την πρόταση υποθέτουμε ότι είναι αληθής – θα τη χρησιμοποιήσουμε στην κατασκευή της απόδειξης. Θέλουμε τώρα να αποδείξουμε ότι

$$2\mid 2(\kappa +1)+2.$$

Τι κάναμε; Στη θέση του κ γράψαμε (κ + 1). Σημασία έχουν οι παρενθέσεις, αυτή η παράσταση θα ήταν λάθος: 2κ + 1 + 2. Δεν προσθέτουμε ένα σε ολόκληρη την παράσταση, αλλά πράγματι αντικαθιστούμε το κ με την κατά ένα μεγαλύτερη παράσταση (κ + 1). Μετασχηματίζουμε την παράσταση εφαρμόζοντας την επιμεριστική ιδιότητα.

$$\begin{array}{rcl}2& \mid & 2(\kappa +1)+2\\ 2& \mid & 2\kappa +2+2\end{array}$$

Τώρα μια μικρή παρέκβαση για τη διαιρετότητα. Αν έχουμε δύο αριθμούς, ας πούμε p και q, που διαιρούνται με κάποιον αριθμό, ας πούμε r, τότε ισχύει ότι και το άθροισμά τους διαιρείται με τον αριθμό r. Ισχύει λοιπόν:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Μπορούμε να αντικαταστήσουμε για παράδειγμα τους αριθμούς p = 8, q = 20 και r = 4. Βλέπουμε ότι το τέσσερα διαιρεί και το οκτώ και το είκοσι. Και το ίδιο διαιρεί και το άθροισμά τους 8 + 20 = 28.

Πώς το χρησιμοποιούμε στο παράδειγμά μας; Χωρίζουμε το δεύτερο μέλος στους αριθμούς p και q ως εξής:

$$p=2\kappa +2;q=2$$

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

Άλλη μια φορά για την υπόθεση. Στην αρχή είπαμε ότι υποθέτουμε ότι ισχύει

$$2\mid 2\kappa +2.$$

Γι' αυτό, όταν κατά την κατασκευή της απόδειξης συναντήσαμε την παράσταση 2κ + 2, μπορούσαμε να πούμε γι' αυτήν ότι διαιρείται με το δύο. Ακριβώς επειδή είναι η υπόθεσή μας. Αυτό είναι συνήθως το δυσκολότερο βήμα της μαθηματικής επαγωγής – να καταλάβεις πότε και γιατί μπορείς να χρησιμοποιήσεις την επαγωγική υπόθεση.

Έτσι τελειώνει η επαγωγή, η απόδειξη έγινε με επιτυχία, η πρόταση ισχύει.

Αν ήθελες, θα μπορούσες να το αναλύσεις αλλιώς και να μη χρησιμοποιήσεις την υπόθεση. p = 2ν και q = 2 + 2. Ο αριθμός q = 4 διαιρείται τετριμμένα με το δύο και το ίδιο και ο p = 2ν, επειδή μετά τη διαίρεση με το δύο μας μένει ο αριθμός ν, που είναι φυσικός, δηλαδή ακέραιος. Πάλι λοιπόν πήραμε δύο παραστάσεις που διαιρούνται και οι δύο με το δύο, άρα και το άθροισμά τους διαιρείται με το δύο.

Και στις δύο περιπτώσεις όμως αποδείξαμε ότι

1. η δοσμένη πρόταση ισχύει για ν = 1,
2. αν η πρόταση ισχύει για ν, τότε ισχύει και για ν + 1.

Από εδώ μπορούμε να συμπεράνουμε:

• Ξέρουμε ότι η πρόταση ισχύει για ν = 1.
• Αν ισχύει για ν, πρέπει να ισχύει και για ν + 1, δηλαδή και για 1 + 1, δηλαδή η πρόταση ισχύει και για ν = 2.
• Αν ισχύει για ν, πρέπει να ισχύει και για ν + 1, δηλαδή και για 2 + 1, δηλαδή η πρόταση ισχύει και για ν = 3.
• Αν ισχύει για ν, πρέπει να ισχύει και για ν + 1, δηλαδή και για 3 + 1, δηλαδή η πρόταση ισχύει και για ν = 4.
• Αν ισχύει για ν, πρέπει να ισχύει και για ν + 1, δηλαδή και για 4 + 1, δηλαδή η πρόταση ισχύει και για ν = 5.
• …

Δεύτερο παράδειγμα

Στη συνέχεια θα αποδείξουμε με μαθηματική επαγωγή μια απλή πρόταση:

$$2^{\nu }\ge 2\nu ;\nu \in {\mathbb{N}}^{\ast }.$$

Πρώτα το πρώτο βήμα, ελέγχουμε αν η πρόταση ισχύει για ν = 1, ως το πρώτο στοιχείο των φυσικών αριθμών χωρίς το μηδέν, από τους οποίους διαλέγουμε το ν.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Αυτό ισχύει τετριμμένα. Τώρα περνάμε στο επαγωγικό βήμα, στο οποίο πρέπει να εξετάσουμε αν, όταν ισχύει για ν = κ, ισχύει και για ν = κ + 1. Η υπόθεσή μας είναι λοιπόν ότι ισχύει

$$2^{\kappa }\ge 2\kappa$$

και θέλουμε να αποδείξουμε:

$$2^{\kappa +1}\ge 2(\kappa +1)$$

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

$$2\cdot 2^{\kappa }\ge 2\kappa +2$$

Στο πρώτο μέλος αντί για πολλαπλασιασμό χρησιμοποιούμε πρόσθεση, το δεύτερο το αφήνουμε χωρίς αλλαγή.

$$2^{\kappa }+2^{\kappa }\ge 2\kappa +2$$

Τώρα χρησιμοποιούμε την υπόθεση. Η υπόθεση είναι μια πρόταση για την οποία υποθέτουμε ότι ισχύει. Στην ανισότητα έχουμε και στα δύο μέλη από δύο παραστάσεις που αθροίζονται. Ταυτόχρονα όμως ξέρουμε ότι

$$\begin{array}{rcl}{2}^{\kappa }& \ge & 2\kappa \\ 2^{\kappa }& \ge & 2.\end{array}$$

Η πρώτη γραμμή μας τη λέει η υπόθεση και η δεύτερη πρόταση είναι τετριμμένη (το ελάχιστο 2^κ είναι για κ = 1 και αυτό ισούται ακριβώς με δύο). Ξέρουμε λοιπόν ότι στο πρώτο μέλος και οι δύο παραστάσεις είναι μεγαλύτερες ή ίσες από τις δύο παραστάσεις του δεύτερου μέλους. Έτσι έχουμε αποδείξει με επαγωγή ότι αν η πρόταση ισχύει για το κ, τότε ισχύει και για το (κ + 1) και επειδή η πρόταση ισχύει και για το ένα, η δοσμένη πρόταση είναι αληθής.

Τρίτο παράδειγμα

Ας δοκιμάσουμε να αποδείξουμε την ακόλουθη πρόταση:

$$3\mid \nu \Rightarrow 3\mid {\nu }^2;\nu \in {\mathbb{N}}^{\ast }$$

Με λόγια: αν το ν διαιρείται με το τρία, τότε και το ν² διαιρείται με το τρία. Αν το ν δεν διαιρείται με το τρία, τότε η πρόταση ισχύει τετριμμένα (από τον ορισμό της συνεπαγωγής), άρα θα ασχοληθούμε με τις περιπτώσεις όπου το ν διαιρείται με το τρία. Αυτό μας δημιουργεί μια ακολουθία φυσικών αριθμών α_κ=3, 6, 9, 12, 15… Από τώρα και στο εξής θα κινούμαστε μέσα σε αυτή την ακολουθία α_κ.

Την απόδειξη με επαγωγή την ξεκινάμε με το πρώτο βήμα, δηλαδή αν ισχύει για το πρώτο στοιχείο. Θυμίζω ότι κινούμαστε στην ακολουθία α_κ, άρα παίρνουμε το πρώτο στοιχείο αυτής της ακολουθίας, δηλαδή το στοιχείο α₁, που είναι το τρία. Για το τρία η πρόταση ισχύει:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Τώρα περνάμε στο επαγωγικό βήμα. Βλέπουμε ότι η ακολουθία α_κ θα μπορούσε να γραφτεί ως 3ν, όπου το ν είναι φυσικός αριθμός. Δηλαδή το δεύτερο στοιχείο είναι κατά τρία μεγαλύτερο από το προηγούμενο κ.ο.κ. Ας υποθέσουμε τώρα ότι η πρόταση ισχύει για το ν και πρέπει να εξασφαλίσουμε ότι θα ισχύει και για το (ν + 3), που είναι ο κανόνας που παράγει το επόμενο στοιχείο της ακολουθίας στην οποία κινούμαστε. Γράφουμε πρώτα την υπόθεση:

$$3\mid \nu \Rightarrow 3\mid {\nu }^2$$

και μετά αυτό που θέλουμε να αποδείξουμε

$$3\mid (\nu +3)\Rightarrow 3\mid (\nu +3{)}^2.$$

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

$$3\mid (\nu +3)\Rightarrow 3\mid {\nu }^2+6\nu +9.$$

Και σχεδόν φτάσαμε. Στο αριστερό μέρος έχουμε μια παράσταση που σίγουρα διαιρείται με το τρία, επειδή το ν σύμφωνα με την υπόθεση διαιρείται με το τρία (κινούμαστε μόνο στους αριθμούς της ακολουθίας α_κ) και το τρία διαιρείται επίσης με το τρία. Στο δεξί μέρος έχουμε πρώτα το ν², που σύμφωνα με την υπόθεση διαιρείται με το τρία. Πράγματι, ξέρουμε ότι το ν διαιρείται με το τρία και η υπόθεση λέει ότι αν το ν διαιρείται με το τρία, τότε και το ν² διαιρείται με το τρία:

$$3\mid \nu \Rightarrow 3\mid {\nu }^2$$

Στη συνέχεια ακολουθεί η παράσταση 6ν, που διαιρείται τετριμμένα με το τρία. Μπορείς να το φανταστείς ως απλοποίηση κλάσματος:

$$\frac{6\nu }{3}=2\nu$$

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

Το πλήθος των παρενθέσεων σε μια παράσταση

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

• ένας φυσικός αριθμός,
• αν το p είναι απλή παράσταση, τότε και το (p²) είναι απλή παράσταση,
• αν τα p και q είναι απλές παραστάσεις, τότε και το (p + q) είναι απλή παράσταση.

Άρα απλές παραστάσεις είναι: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Και αντίθετα αυτές δεν είναι απλές παραστάσεις:

• 1 + 2 → λείπουν οι εξωτερικές παρενθέσεις,
• (1 + 2 → λείπει η δεξιά παρένθεση,
• 13² → λείπουν οι εξωτερικές παρενθέσεις,
• (1 + 2 + 3) → λείπουν παρενθέσεις, σωστά θα έπρεπε να γραφτεί (1 + (2 + 3))

Μια απλή παράσταση μπορεί να προκύψει για παράδειγμα ως εξής. Στην αρχή διαλέγουμε μια απλή παράσταση (a + b). Τώρα στη θέση του a βάζουμε μια απλή παράσταση a = (c + d), οπότε παίρνουμε ((c + d) + b) και στη θέση του b βάζουμε το τρία: ((c + d) + 3). Στη θέση του c βάζουμε το δέκα: ((10 + d) + 3) και τέλος στη θέση του d βάζουμε το (5²): ((10 + (5²)) + 3). Είναι σημαντικό να τηρούμε τις παρενθέσεις, αλλιώς δεν θα λειτουργήσει.

Τώρα θα αποδείξουμε ότι μια απλή παράσταση περιέχει άρτιο πλήθος παρενθέσεων (στους άρτιους αριθμούς ανήκει και το μηδέν).

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

$$j=\nu ;\nu \in {\mathbb{N}}^{\ast }.$$

Για την παράσταση j ισχύει ότι το πλήθος των παρενθέσεων είναι μηδέν, άρα το πρώτο στοιχείο ικανοποιεί την πρόταση. Στο επαγωγικό βήμα θα υποθέσουμε ότι έχουμε δύο απλές παραστάσεις p και q και ότι και οι δύο έχουν άρτιο πλήθος παρενθέσεων. Τότε πρέπει να αποδείξουμε ότι και οι απλές παραστάσεις (p + q) και (p²) έχουν άρτιο πλήθος παρενθέσεων.

Πρώτα η πρόσθεση. Ορίζουμε επιπλέον τη συνάρτηση z(q), που επιστρέφει το πλήθος των παρενθέσεων της παράστασης q. Τότε ισχύει ότι η παράσταση (p + q) έχει z(p) + z(q) + 2 παρενθέσεις. Δηλαδή έχει δύο παρενθέσεις περισσότερες από το άθροισμα των παρενθέσεων των παραστάσεων p και q. Σύμφωνα με την υπόθεση τα z(p) και z(q) είναι άρτια, άρα αν προσθέσουμε τρεις άρτιους αριθμούς, παίρνουμε πάλι άρτιο αριθμό. Για αυτή την περίπτωση η πρόταση ισχύει.

Τώρα η δύναμη. Πάλι ισχύει η υπόθεση ότι η απλή παράσταση p περιέχει άρτιο πλήθος παρενθέσεων. Η παράσταση (p²) περιέχει τότε z(p) + 2 παρενθέσεις, δηλαδή πάλι δύο παρενθέσεις περισσότερες από την παράσταση p. Και σε αυτή την περίπτωση προσθέτουμε άρτιους αριθμούς, το αποτέλεσμα είναι λοιπόν άρτιο.

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