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

Mathematical Induction


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

Μαθηματικά Γεωμετρία Άλγεβρα Μαθηματική Λογική Μαθηματική Ανάλυση Διακριτά Μαθηματικά Τοπολογία Γραμμική Άλγεβρα Στατιστική Οικονομικά Μαθηματικά

- Μία Μαθηματική Μέθοδος

Ετυμολογία[επεξεργασία | επεξεργασία κώδικα]

Η ονομασία "επαγωγή" σχετίζεται ετυμολογικά με την λέξη "αγωγή".

Ορισμός[επεξεργασία | επεξεργασία κώδικα]

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

Εισαγωγή[επεξεργασία | επεξεργασία κώδικα]

Η μαθηματική επαγωγή είναι λογικά ισοδύναμη με την αρχή Καλής Διάταξης.

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

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

Η πρώτη γνωστή απόδειξη με τη μέθοδο της μαθηματικής επαγωγής εμφανίζεται στο έργο Arithmeticorum libri fuo του Ιταλού μαθηματικού και αστρονόμου Franciscus Maurolycus του 16ου αιώνα. Συγκεκριμένα χρησιμοποίησε τη μέθοδο για να αποδείξει ότι το άθροισμα των ν πρώτων περιττών αριθμών είναι ν2.

Περιγραφή της μεθόδου[επεξεργασία | επεξεργασία κώδικα]

Είναι βολικό να ομιλούμε για την πρόταση προς απόδειξη συμβολίζοντας την με P(ν) και αντικαθιστώντας όπου ν τον αριθμό που θέλουμε.

Η πιο απλή και πιο συνήθης μορφή της μεθόδου είναι αυτή που αποδεικνύει ότι μια πρόταση P(ν) είναι αληθής για όλους τους φυσικούς αριθμούς ν και αποτελείται από τα παρακάτω τρία βήματα:

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

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

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

  • Αν ωθήσου το πρώτο ντόμινο στη σειρά, αυτό θα πέσει.
  • Όταν ένα οποιοδήποτε από τα ντόμινο πέσει τότε πέφτει και το επόμενο.

Έτσι μπορούμε να είμαστε απόλυτα βέβαιοι ότι αν σπρώξουμε το πρώτο ντόμινο για να πέσει τότε όλα τα ντόμινο θα πέσουν.

Παράδειγμα[επεξεργασία | επεξεργασία κώδικα]

Ας υποθέσουμε ότι θέλουμε να αποδείξουμε την πιο κάτω μαθηματική πρόταση (την οποία θα συμβολίσουμε με P(ν)) :

για κάθε

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

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

Το κάνουμε αυτό χρησιμοποιώντας την επαγωγική υπόθεση.

Έχουμε δεχθεί ότι ισχύει:

Προσθέτουμε και στα δύο μέλη της εξίσωσης τον όρο κ + 1, που είναι ο επόμενος του κ φυσικός αριθμός, και έχουμε διαδοχικά:

Έτσι έχουμε:

Αυτό που έχουμε καταφέρει είναι να δείξουμε ότι, αν η P(κ) είναι αληθής, τότε είναι αληθής και η P(κ + 1). Συμβολικά:

Έτσι το μόνο που απομένει για να ολοκληρωθεί η απόδειξη είναι να βρούμε ένα φυσικό αριθμό κ για τον οποίο η P(κ) είναι αληθής. Τον αριθμό αυτό όμως τον έχουμε ήδη βρει και είναι ο αριθμός ν = κ = 1 για τον οποίο αποδείξαμε από την αρχή ότι ισχύει η P(1). Έτσι:

  1. Ισχύει η P(1), δηλαδή η πρόταση είναι αληθής αν το ν έχει την τιμή 1.
  2. Η P(ν) είναι αληθής αν ν = 1, επομένως η P(κ) είναι αληθής για κ = 1. Έχουμε όμως αποδείξει ότι, αν για κάποιο κ η P(κ) είναι αληθής, τότε είναι αληθής και η P(κ +1). Επομένως και η P(2) είναι αληθής.
  3. Αν είναι αληθής η P(2) τότε είναι αληθής και η P(3), άρα και η P(4) και ούτω καθεξής.
4. Η πρόταση P(ν) είναι αληθής για όλους τους φυσικούς αριθμούς ν.

Επαγωγή ξεκινώντας από κάποιο άλλο αριθμό[επεξεργασία | επεξεργασία κώδικα]

Αν θέλουμε να αποδείξουμε μια Μαθηματική Πρόταση όχι για όλους τους φυσικούς αριθμούς αλλά μόνο για αυτούς που είναι μεγαλύτεροι ή ίσοι με ένα συγκεκριμένο φυσικό αριθμό ν0, τότε είναι αρκετό να δείξουμε ότι:

  1. Η πρόταση ισχύει για κάποιο φυσικό αριθμό ν0,
  2. Αν η πρόταση ισχύει για κάποιο κ ≥ ν0 ισχύει και για το κ + 1,

για να έχουμε την πλήρη απόδειξη της πρότασης.

Για παράδειγμα, αυτή την μέθοδο χρησιμοποιούμε όταν θέλουμε να αποδείξουμε ότι: ν2 > 2ν για ν ≥ 3.

Πλήρης ή Ισχυρή Επαγωγή[επεξεργασία | επεξεργασία κώδικα]

Μια άλλη, ισχυρότερη αλλά ισοδύναμη, μορφή της επαγωγής είναι η εξής:

  1. Αν η πρόταση ισχύει για κάθε , για κάποιο m ισχύει και για το m + 1.

Υποσημειώσεις[επεξεργασία | επεξεργασία κώδικα]

Εσωτερική Αρθρογραφία[επεξεργασία | επεξεργασία κώδικα]

Βιβλιογραφία[επεξεργασία | επεξεργασία κώδικα]

Ιστογραφία[επεξεργασία | επεξεργασία κώδικα]


Ikl.jpg Κίνδυνοι ΧρήσηςIkl.jpg

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

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

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



Επίσης,
Οι διάφοροι "Εξωτερικοί Σύνδεσμοι (Links)"
(όχι μόνον, της Sciencepedia
αλλά και κάθε διαδικτυακού ιστότοπου (ή αλλιώς site)),
αν και άκρως απαραίτητοι,
είναι αδύνατον να ελεγχθούν
(λόγω της ρευστής φύσης του Web),
και επομένως είναι ενδεχόμενο να οδηγήσουν
σε παραπλανητικό, κακόβουλο ή άσεμνο περιεχόμενο.
Ο αναγνώστης πρέπει να είναι
εξαιρετικά προσεκτικός όταν τους χρησιμοποιεί.

- Μην κάνετε χρήση του περιεχομένου της παρούσας εγκυκλοπαίδειας
αν διαφωνείτε με όσα αναγράφονται σε αυτήν

IonnKorr-System-00-goog.png



>>Διαμαρτυρία προς την wikia<<

- Όχι, στις διαφημίσεις που περιέχουν απαράδεκτο περιεχόμενο (άσεμνες εικόνες, ροζ αγγελίες κλπ.)


Community content is available under CC-BY-SA unless otherwise noted.