Mathematical Induction
Η Μαθηματική Επαγωγή είναι μία από τις πιο ισχυρές και κομψές μεθόδους απόδειξης. Σου επιτρέπει να αποδείξεις ότι κάτι ισχύει για άπειρα πολλές περιπτώσεις — με μόνο δύο βήματα!
Η ιδέα είναι σαν σκάλα: αν μπορείς να ανεβείς στο πρώτο σκαλοπάτι, και αν από κάθε σκαλοπάτι μπορείς να ανεβείς στο επόμενο, τότε μπορείς να ανεβείς όσο ψηλά θέλεις!
🪜 Η Αρχή της Μαθηματικής Επαγωγής:
Για να αποδείξεις ότι μια πρόταση P(n) ισχύει για κάθε φυσικό n ≥ n₀:
Να αποδείξετε με επαγωγή ότι για κάθε φυσικό n ≥ 1:
\[1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\]
Hint: Ακολούθησε τα 3 βήματα!
Βάση: Δοκίμασε για n=1
Υπόθεση: Υπόθεσε ότι ισχύει για n=k
Βήμα: Δείξε για n=k+1:
1+2+...+k+(k+1) = ?
Χρησιμοποίησε την υπόθεση!
Πρόταση P(n): \(1 + 2 + \cdots + n = \frac{n(n+1)}{2}\)
Βήμα 1 - Βάση Επαγωγής (n=1):
Αριστερά: 1
Δεξιά: \(\frac{1(1+1)}{2} = \frac{2}{2} = 1\)
Αριστερά = Δεξιά ✓
Άρα P(1) ισχύει.
Βήμα 2 - Επαγωγική Υπόθεση:
Υποθέτουμε ότι η P(k) ισχύει για κάποιο k ≥ 1:
\[1 + 2 + \cdots + k = \frac{k(k+1)}{2}\]
Βήμα 3 - Επαγωγικό Βήμα (n=k+1):
Θέλουμε να δείξουμε:
\[1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}\]
Αριστερό μέλος:
\(1 + 2 + \cdots + k + (k+1)\)
= \(\left[\frac{k(k+1)}{2}\right] + (k+1)\) (χρησιμοποιήσαμε την υπόθεση!)
= \(\frac{k(k+1)}{2} + \frac{2(k+1)}{2}\)
= \(\frac{k(k+1) + 2(k+1)}{2}\)
= \(\frac{(k+1)(k+2)}{2}\) ✓
Συμπέρασμα:
Από την αρχή της μαθηματικής επαγωγής, η πρόταση P(n) ισχύει για κάθε n ≥ 1. ✓
🔑 Κλειδί: Χρησιμοποιήσαμε την επαγωγική υπόθεση για να δείξουμε το επόμενο βήμα!
Να αποδείξετε ότι για κάθε φυσικό n ≥ 1:
\[1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}\]
Hint: Ίδια μέθοδος - 3 βήματα!
Βάση: n=1 → 1² = 1·2·3/6 = 1 ✓
Υπόθεση: Ισχύει για k
Βήμα: Πρόσθεσε (k+1)² και απλοποίησε!
Βάση (n=1):
1² = 1
\(\frac{1·2·3}{6} = 1\) ✓
Επαγωγική Υπόθεση:
\[1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}\]
Επαγωγικό Βήμα (n=k+1):
Θέλουμε:
\[1^2 + 2^2 + \cdots + k^2 + (k+1)^2 = \frac{(k+1)(k+2)(2k+3)}{6}\]
Αριστερό μέλος:
\(\frac{k(k+1)(2k+1)}{6} + (k+1)^2\)
Κοινός παρονομαστής:
\(= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6}\)
\(= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6}\)
\(= \frac{(k+1)[2k^2 + k + 6k + 6]}{6}\)
\(= \frac{(k+1)[2k^2 + 7k + 6]}{6}\)
\(= \frac{(k+1)(k+2)(2k+3)}{6}\) ✓
(Παραγοντοποίηση: 2k²+7k+6 = (k+2)(2k+3))
Συμπέρασμα: Ισχύει για κάθε n ≥ 1. ✓
🔑 Κλειδί: Η επαγωγή λειτουργεί και για πιο περίπλοκους τύπους!
Να αποδείξετε ότι για κάθε φυσικό n ≥ 1:
\[3^n > 2^n + n^2\]
Hint: Ανισότητα - πρόσεχε στο επαγωγικό βήμα!
Βάση: n=1 → 3 > 2+1 → 3>3? ΟΧΙ! Δοκίμασε n=2
Βήμα: Από 3^k > 2^k + k², δείξε 3^(k+1) > 2^(k+1) + (k+1)²
Τεχνική: 3^(k+1) = 3·3^k > 3(2^k + k²)
Βάση: Ελέγχουμε για n=1:
3¹ = 3, αλλά 2¹ + 1² = 3
3 > 3? ΟΧΙ! ✗
Για n=2:
3² = 9, και 2² + 2² = 8
9 > 8 ✓
Άρα η βάση είναι n₀ = 2.
Επαγωγική Υπόθεση:
\[3^k > 2^k + k^2\] για κάποιο k ≥ 2
Επαγωγικό Βήμα (n=k+1):
Θέλουμε: \(3^{k+1} > 2^{k+1} + (k+1)^2\)
Αριστερό μέλος:
\(3^{k+1} = 3 \cdot 3^k\)
\(> 3(2^k + k^2)\) (επαγωγική υπόθεση)
\(= 3 \cdot 2^k + 3k^2\)
Αρκεί να δείξουμε:
\(3 \cdot 2^k + 3k^2 > 2 \cdot 2^k + (k+1)^2\)
\(2^k + 3k^2 > (k+1)^2\)
\(2^k + 3k^2 > k^2 + 2k + 1\)
\(2^k + 2k^2 > 2k + 1\)
Για k ≥ 2:
• 2^k ≥ 4
• 2k² ≥ 8
• Άθροισμα ≥ 12
Ενώ 2k + 1 ≤ 5 για k=2.
Άρα ισχύει! ✓
Συμπέρασμα: \(3^n > 2^n + n^2\) για κάθε n ≥ 2. ✓
🔑 Κλειδί: Στις ανισότητες, πολλαπλασιάζουμε την υπόθεση και απλοποιούμε!
Ερώτηση: Ποια είναι τα 3 βασικά βήματα της Μαθηματικής Επαγωγής;
Ολοκλήρωσες και τις 12 στρατηγικές!
Τώρα έχεις έναν πλήρη χάρτη για την επίλυση μαθηματικών προβλημάτων!
Μην ξεχνάς: Η τέχνη δεν είναι να τις ξέρεις όλες,
αλλά να ξέρεις ποια να διαλέξεις πότε!