Μια επαγωγική απόδειξη αποτελείται από δύο περιπτώσεις. Η πρώτη, η βασική περίπτωση (ή η βάση), αποδεικνύει τη δήλωση για n=0 χωρίς να υποθέσει καμία γνώση άλλων περιπτώσεων. Η δεύτερη περίπτωση, το βήμα επαγωγής, αποδεικνύει ότι αν η πρόταση ισχύει για οποιαδήποτε δεδομένη περίπτωση n=k, τότε πρέπει να ισχύει και για την επόμενη περίπτωση n=k + 1.
Τι είναι απόδειξη με επαγωγή και απόδειξη με αντίφαση;
Στην απόδειξη, επιτρέπεται να υποθέσετε το X και, στη συνέχεια, να δείξετε ότι το Y είναι αληθές, χρησιμοποιώντας το X. • Μια ειδική περίπτωση: εάν δεν υπάρχει X, εσείς απλά πρέπει να αποδείξετε το Y ή το αληθινό ⇒ Y. Εναλλακτικά, μπορείτε να κάνετε μια απόδειξη με αντίφαση: Υποθέστε ότι το Y είναι ψευδές και δείξτε ότι το X είναι ψευδές. • Αυτό ισοδυναμεί με απόδειξη.
Είναι έγκυρη η επαγωγική απόδειξη;
Το
ισχύει για όλους τους φυσικούς αριθμούς k. Αν και αυτή είναι η ιδέα, η επίσημη απόδειξη ότι η μαθηματική επαγωγή είναι μια έγκυρη τεχνική απόδειξης τείνει να βασίζεται στην αρχή της καλής διάταξης των φυσικών αριθμών. Δηλαδή, ότι κάθε μη κενό σύνολο θετικών ακεραίων περιέχει ένα ελάχιστο στοιχείο. Δείτε, για παράδειγμα, εδώ.
Γιατί η επαγωγή είναι έγκυρη απόδειξη;
Η μαθηματική επαγωγή είναι μια έγκυρη τεχνική απόδειξης επειδή χρησιμοποιούμε φυσικούς αριθμούς και το κάνουμε εδώ και πολύ καιρό. Η μαθηματική επαγωγή είναι μια μέθοδος για τον συλλογισμό και την απόδειξη ιδιοτήτων σχετικά με τους φυσικούς αριθμούς.
Γιατί η επαγωγή είναι μια έγκυρη τεχνική απόδειξης;
Η επαγωγή λέει απλώς ότι το P(n) πρέπει να ισχύει για όλους τους φυσικούς αριθμούςγιατί μπορούμε να δημιουργήσουμε μια απόδειξη σαν την παραπάνω για κάθε φυσικό. Χωρίς επαγωγή, μπορούμε, για οποιοδήποτε φυσικό n, να δημιουργήσουμε μια απόδειξη για το P(n) - η επαγωγή απλώς το επισημοποιεί και λέει ότι μας επιτρέπεται να μεταπηδήσουμε από εκεί στο ∀n[P(n)].
