Μέθοδος της Μαθηματικής Επαγωγής

🎯 Γιατί χρειαζόμαστε τη Μαθηματική Επαγωγή;

Ας υποθέσουμε ότι θέλουμε να υπολογίσουμε το άθροισμα των $\nu$ πρώτων διαδοχικών περιττών ακεραίων αριθμών:

1 + 3 + 5 + \cdots + (2\nu - 1)

Υπολογίζοντας για μικρές τιμές:

$\nu = 1:\ 1 = 1^2$
$\nu = 2:\ 1 + 3 = 4 = 2^2$
$\nu = 3:\ 1 + 3 + 5 = 9 = 3^2$
$\nu = 4:\ 1 + 3 + 5 + 7 = 16 = 4^2$
$\nu = 5:\ 1 + 3 + 5 + 7 + 9 = 25 = 5^2$

Παρατηρούμε ότι τα αθροίσματα ακολουθούν ένα μοτίβο και μας οδηγούν στην εικασία:

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

Πρόβλημα

Οι θετικοί ακέραιοι είναι άπειροι. Δεν μπορούμε να επαληθεύσουμε τον τύπο για κάθε $\nu$ ξεχωριστά — χρειαζόμαστε μια μέθοδο που να μας εξασφαλίζει αλήθεια για όλους τους $\nu$ συγχρόνως!

📜 Η Αρχή της Μαθηματικής Επαγωγής

Αρχή της Μαθηματικής Επαγωγής

Αν $p(\nu)$ μια πρόταση με σύνολο αναφοράς το σύνολο των φυσικών αριθμών $\mathbb{N}$ και οι ακόλουθες δύο συνθήκες ικανοποιούνται:

🏗️ Η $p(1)$ είναι αληθής, δηλαδή η πρόταση ισχύει για $\nu = 1$ , και
🔄 Αν η $p(\kappa)$ είναι αληθής, τότε και η $p(\kappa + 1)$ είναι αληθής, $\forall \kappa \in \mathbb{N}$

τότε η πρόταση $p(\nu)$ είναι αληθής για όλους τους φυσικούς αριθμούς $\nu$ .

🧠 Γιατί λειτουργεί — Η διαίσθηση

Η ιδέα του «ντόμινο»

Φαντάσου μια άπειρη σειρά από ντόμινο:

🎯 Ρίχνουμε το πρώτο ντόμινο (Βήμα 1ο — Βάση)
🎯 Κάθε ντόμινο, αν πέσει, ρίχνει το επόμενο (Βήμα 2ο — Επαγωγικό Βήμα)

Τότε όλα τα ντόμινο πέφτουν! 🎲

Μαθηματικά: αν $p(1)$ αληθής και $p(\kappa) \Rightarrow p(\kappa+1)$ , τότε:

p(1) \Rightarrow p(2) \Rightarrow p(3) \Rightarrow p(4) \Rightarrow \cdots

Άρα η $p(\nu)$ είναι αληθής για κάθε $\nu \in \mathbb{N}$ .

🔧 Τα Δύο Βήματα της Απόδειξης

Βήμα 1ο — Βάση της Επαγωγής 🏗️

Αποδεικνύουμε ότι η πρόταση $p(\nu)$ ισχύει για την μικρότερη τιμή του συνόλου αναφοράς (συνήθως $\nu = 1$ , αλλά μπορεί και $\nu = 0$ ή $\nu = \kappa_0$ αν το ζητούμενο είναι «για κάθε $\nu \geq \kappa_0$ »).

Βήμα 2ο — Επαγωγικό Βήμα 🔄

📥 Επαγωγική Υπόθεση: Υποθέτουμε ότι η πρόταση ισχύει για κάποιο τυχαίο $\nu = \kappa$ , δηλαδή η $p(\kappa)$ είναι αληθής
🎯 Επαγωγικό Ζητούμενο: Αποδεικνύουμε ότι η πρόταση ισχύει και για $\nu = \kappa + 1$ , δηλαδή ότι η $p(\kappa + 1)$ είναι αληθής

Κρίσιμο σημείο

Στο Επαγωγικό Βήμα χρησιμοποιούμε υποχρεωτικά την επαγωγική υπόθεση $p(\kappa)$ . Αν μια απόδειξη δεν χρησιμοποιεί την επαγωγική υπόθεση, πιθανότατα δεν χρειαζόταν επαγωγή καθόλου!

📝 Παράδειγμα 1 — Άθροισμα περιττών

Πρόβλημα: Να αποδείξετε με τη μέθοδο της Τέλειας Επαγωγής ότι:

p(\nu):\ 1 + 3 + 5 + \cdots + (2\nu - 1) = \nu^2,\ \nu \in \mathbb{N}

Λύση:

🏗️ Βήμα 1ο: Για $\nu = 1$ , έχουμε $p(1):\ 1 = 1^2$ , αληθής. ✅

🔄 Βήμα 2ο: Έστω ότι η πρόταση αληθεύει για $\nu = \kappa$ , δηλαδή:

p(\kappa):\ 1 + 3 + 5 + \cdots + (2\kappa - 1) = \kappa^2 \quad (1) \quad \text{(Επαγωγική Υπόθεση)}

Θα δείξουμε ότι η $p(\kappa+1)$ είναι αληθής, δηλαδή:

p(\kappa+1):\ 1 + 3 + 5 + \cdots + (2\kappa - 1) + (2(\kappa+1) - 1) = (\kappa + 1)^2

Έχουμε:

\begin{aligned} \text{Α΄ μέλος} &= \underbrace{\big(1 + 3 + 5 + \cdots + (2\kappa - 1)\big)}_{= \kappa^2\ \text{από (1)}} + (2(\kappa + 1) - 1) \\ &= \kappa^2 + 2\kappa + 2 - 1 = \kappa^2 + 2\kappa + 1 = (\kappa + 1)^2 = \text{Β΄ μέλος} \end{aligned}

Άρα η $p(\kappa + 1)$ είναι αληθής και συνεπώς, από την Αρχή της Μαθηματικής Επαγωγής, η $p(\nu)$ είναι αληθής για κάθε $\nu \in \mathbb{N}$ . ✅

📝 Παράδειγμα 2 — Άθροισμα φυσικών

Πρόβλημα: Να δείξετε ότι $\forall \nu \in \mathbb{N}$ :

p(\nu):\ 1 + 2 + 3 + \cdots + \nu = \frac{\nu(\nu + 1)}{2}

Λύση:

🏗️ Βήμα 1ο: Ο τύπος είναι αληθής για $\nu = 1$ : $p(1):\ 1 = \frac{1 \cdot 2}{2} = 1$ . ✅

🔄 Βήμα 2ο: Υποθέτουμε $p(\kappa)$ αληθή:

1 + 2 + 3 + \cdots + \kappa = \frac{\kappa(\kappa + 1)}{2} \quad (2)

Πρέπει να αποδείξουμε ότι $p(\kappa+1)$ αληθής:

1 + 2 + \cdots + \kappa + (\kappa + 1) = \frac{(\kappa+1)(\kappa+2)}{2}

Έχουμε:

\begin{aligned} \text{Α΄ μέλος} &= \underbrace{(1 + 2 + \cdots + \kappa)}_{=\ \frac{\kappa(\kappa+1)}{2}\ \text{από (2)}} + (\kappa + 1) \\ &= \frac{\kappa(\kappa+1)}{2} + (\kappa + 1) = \frac{\kappa(\kappa+1) + 2(\kappa + 1)}{2} = \frac{(\kappa + 1)(\kappa + 2)}{2} = \text{Β΄ μέλος} \end{aligned}

Άρα από την Αρχή της Μαθηματικής Επαγωγής, η $p(\nu)$ ισχύει για κάθε $\nu \in \mathbb{N}$ . ✅

📝 Παράδειγμα 3 — Διαιρετότητα

Πρόβλημα: Να αποδείξετε ότι το $4^{2\nu} - 1$ είναι πολλαπλάσιο του $5$ για κάθε $\nu \in \mathbb{N}$ .

Λύση: Θα δείξουμε $p(\nu): 4^{2\nu} - 1 = 5\mu,\ \mu \in \mathbb{N}$ .

🏗️ Βήμα 1ο: Για $\nu = 1$ : $4^{2} - 1 = 15 = 5 \cdot 3$ , αληθής. ✅

🔄 Βήμα 2ο: Έστω $p(\kappa): 4^{2\kappa} - 1 = 5\rho,\ \rho \in \mathbb{N}$ .

Θα δείξουμε $p(\kappa+1): 4^{2(\kappa+1)} - 1 = 5\tau,\ \tau \in \mathbb{N}$ .

\begin{aligned} 4^{2(\kappa+1)} - 1 &= 4^{2\kappa + 2} - 1 = 4^2 \cdot 4^{2\kappa} - 1 \\ &= 16(5\rho + 1) - 1 \quad \text{(από επαγωγική υπόθεση)} \\ &= 80\rho + 16 - 1 = 80\rho + 15 = 5(16\rho + 3) = 5\tau \end{aligned}

όπου $\tau = 16\rho + 3 \in \mathbb{N}$ . Άρα η $p(\kappa+1)$ είναι αληθής, και κατά συνέπεια η $p(\nu)$ ισχύει για κάθε $\nu \in \mathbb{N}$ . ✅

📐 Παρατήρηση για Γενική Βάση

Γενικευμένη Βάση

Σε κάποιες περιπτώσεις, πρέπει να αποδείξουμε ότι ένας ισχυρισμός $p(\nu)$ αληθεύει για κάθε $\nu \geq \kappa_0$ (όχι απαραίτητα από το $1$ ). Τότε:

🔸 Ως πρώτο βήμα εξετάζουμε αν η $p(\kappa_0)$ αληθεύει
🔸 Στο επαγωγικό βήμα δείχνουμε $p(\kappa) \Rightarrow p(\kappa+1)$ για κάθε $\kappa \geq \kappa_0$

Παράδειγμα: Για να αποδείξουμε ότι $p(\nu): 2^\nu > 2\nu + 1,\ \forall \nu \geq 3$ , το πρώτο βήμα είναι να αποδείξουμε ότι η ανισότητα αληθεύει για $\nu = 3$ (που είναι ο μικρότερος αριθμός του συνόλου αναφοράς).

Παράδειγμα PDF: Το πλήθος των διαγωνίων ενός πολυγώνου με $\nu$ πλευρές είναι $\frac{\nu(\nu-3)}{2}$ , αληθεύει για $\nu \geq 4$ (γιατί το τρίγωνο δεν έχει διαγώνιο).

⚠️ Προσοχή — Η ιστορία με τα άσπρα άλογα

Κλασικός παραλογισμός

Σε μία φάρμα ζουν $100$ άλογα. Οι στάβλοι είναι αριθμημένοι $1$ έως $100$ . Ο πατέρας λέει στον γιο του: «Αν σε κάποιο στάβλο βρίσκεται ένα άσπρο άλογο, τότε και στον αμέσως επόμενο στάβλο βρίσκεται επίσης ένα άσπρο άλογο.»

Ο γιος συμπεραίνει: «Όλα τα άλογά μας είναι άσπρα!» 🐴

Αυτό είναι λάθος! Γιατί; Επειδή λείπει η βάση: ο γιος δεν έχει επιβεβαιώσει ότι υπάρχει κανένα άσπρο άλογο σε κάποιον στάβλο. Χωρίς βάση, η επαγωγή δεν λειτουργεί!

🔑 Δίδαγμα: Και τα δύο βήματα είναι απαραίτητα. Ένα από τα δύο να λείπει και η απόδειξη καταρρέει!

🎯 Πότε χρησιμοποιούμε Μαθηματική Επαγωγή

Η Μαθηματική Επαγωγή χρησιμοποιείται για ισχυρισμούς που:

🔢 Αφορούν φυσικούς αριθμούς (ή θετικούς ακεραίους γενικότερα)
📊 Είναι της μορφής «για κάθε $\nu \in \mathbb{N}$ , ισχύει ...»
🎚️ Εκφράζουν τύπους αθροίσματος (π.χ. $\sum_{i=1}^{\nu} i = \frac{\nu(\nu+1)}{2}$ )
➗ Εκφράζουν διαιρετότητα (π.χ. «το $5$ διαιρεί το $4^{2\nu} - 1$ »)
⚖️ Εκφράζουν ανισότητες (π.χ. « $2^\nu > \nu^2$ για κάθε $\nu \geq 5$ »)

🔗 Σύνδεση με τη Λογική

Η Μαθηματική Επαγωγή είναι, στην ουσία, απόδειξη μιας ποσοτικοποιημένης πρότασης της μορφής $\forall \nu \in \mathbb{N},\ p(\nu)$ . Η διαφορά της από τις άλλες μεθόδους είναι ότι εκμεταλλεύεται τη διακριτή, διατεταγμένη δομή των φυσικών αριθμών.

🛠️ Συμβουλές για Σωστή Απόδειξη με Επαγωγή

✅ Γράψε ξεκάθαρα την πρόταση $p(\nu)$ που θες να δείξεις
✅ Επιβεβαίωσε τη βάση (μην την παραλείψεις!)
✅ Διατύπωσε καθαρά την επαγωγική υπόθεση
✅ Χρησιμοποίησε την επαγωγική υπόθεση στο 2ο βήμα
✅ Κατέληξε ξεκάθαρα στην $p(\kappa+1)$
❌ Μην παραλείψεις ούτε το ένα βήμα

Για περισσότερες λεπτομέρειες και παραδείγματα (διαγώνιοι πολυγώνου, τύποι αθροίσματος, διαιρετότητα), βλ. σελ. 19–23 του PDF (Α΄ Τεύχος).