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

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

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

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

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

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

Περιγραφή της μεθόδου

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

1. Βασικό βήμα: δείχνουμε ότι η πρόταση P(ν) ισχύει για ν = 1,

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

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

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

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

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

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

Παράδειγμα

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

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

για κάθε $\nu \in \mathbb {N}$

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

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

$1+1={\frac {1(1+1)}{2}}=1$

• Στη συνέχεια υποθέτουμε ότι η πρόταση είναι αληθής για κάποιο φυσικό αριθμό ν = κ [δηλαδή ότι η P(κ) είναι αληθής].

$1+2+3+\cdots +\kappa ={\frac {\kappa (\kappa +1)}{2}}$, (επαγωγική υπόθεση)

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

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

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

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

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

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

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

$={\frac {(\kappa ^{2}+3\kappa +2)}{2}}$

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

Έτσι έχουμε:

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

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

$P(\kappa )\Rightarrow P(\kappa +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ν για ν ≥ 3.