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

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

Κάτι ισχύει για την πρώτη περίπτωση
Το ίδιο πράγμα ισχύει πάντα και για την επόμενη περίπτωση

τότε

Το ίδιο πράγμα ισχύει για κάθε περίπτωση

Στην προσεκτική γλώσσα των μαθηματικών:

Δηλώστε ότι η απόδειξη θα γίνει με επαγωγή επί του n {\displaystyle n} . ( n {\displaystyle n} είναι η επαγωγική μεταβλητή.)
Δείξτε ότι η δήλωση είναι αληθής όταν το n {\displaystyle n} είναι 1.
Υποθέστε ότι η δήλωση είναι αληθής για κάθε φυσικό αριθμό n {\displaystyle n} . (Αυτό ονομάζεται βήμα επαγωγής).

Δείξτε τότε ότι η δήλωση είναι αληθής για τον επόμενο αριθμό, n + 1 {\displaystyle n+1} $n+1$ .

Επειδή είναι αληθές για το 1, τότε είναι αληθές για το 1+1 (=2, από το βήμα επαγωγής), τότε είναι αληθές για το 2+1 (=3), τότε είναι αληθές για το 3+1 (=4), και ούτω καθεξής.

Ένα παράδειγμα απόδειξης μέσω επαγωγής:

Αποδείξτε ότι για όλους τους φυσικούς αριθμούς n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)} $1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

Απόδειξη:

Πρώτον, η δήλωση μπορεί να γραφεί: για όλους τους φυσικούς αριθμούς n

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} $2\sum _{k=1}^{n}k=n(n+1)$

Με επαγωγή στο n,

Πρώτον, για n=1:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} $2\sum _{k=1}^{1}k=2(1)=1(1+1)$ ,

έτσι αυτό είναι αλήθεια.

Στη συνέχεια, υποθέστε ότι για κάποια n=n0 η δήλωση είναι αληθής. Δηλαδή,:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

Τότε για n=n0+1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k} $2\sum _{k=1}^{{n_{0}}+1}k$

μπορεί να ξαναγραφεί

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)} $2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

Δεδομένου ότι 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ), {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Επομένως, η απόδειξη είναι σωστή.

Παρόμοιες αποδείξεις

Η μαθηματική επαγωγή δηλώνεται συχνά με αρχική τιμή 0 (αντί για 1). Στην πραγματικότητα, λειτουργεί εξίσου καλά με μια ποικιλία αρχικών τιμών. Ακολουθεί ένα παράδειγμα όταν η αρχική τιμή είναι 3. Το άθροισμα των εσωτερικών γωνιών ενός πολυγώνου με n {\displaystyle n} πλευρές είναι ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ μοίρες.

Η αρχική αρχική τιμή είναι 3 και οι εσωτερικές γωνίες ενός τριγώνου είναι ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ μοίρες. Υποθέστε ότι οι εσωτερικές γωνίες ενός πολυγώνου με n {\displaystyle n} πλευρές είναι ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ μοίρες. Προσθέστε ένα τρίγωνο που κάνει το σχήμα ένα n + 1 {\displaystyle n+1} $n+1$ πολύγωνο, και αυτό αυξάνει τον αριθμό των γωνιών κατά 180 μοίρες ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\displaystyle (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ μοίρες. Αποδεικνύεται.

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

Επαγωγικός ορισμός

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

Ορίστε n {\displaystyle n} ξαδέλφια ου βαθμού:

Ένας 1 {\displaystyle 1} $1$ ξάδελφος 1ου βαθμού είναι το παιδί του αδελφού ενός γονέα.
Ένας n + 1 {\displaystyle n+1} $n+1$ ξάδελφος δευτέρου βαθμού είναι το παιδί του n {\displaystyle n} ξαδέλφου τρίτου βαθμού ενός γονέα.

Υπάρχει ένα σύνολο αξιωμάτων για την αριθμητική των φυσικών αριθμών που βασίζεται στη μαθηματική επαγωγή. Αυτό ονομάζεται "Αξιώματα του Peano". Τα απροσδιόριστα σύμβολα είναι | και =. Τα αξιώματα είναι

| είναι ένας φυσικός αριθμός
Αν ο n {\displaystyle n} είναι φυσικός αριθμός, τότε ο n | {\displaystyle n|} $n|$ είναι φυσικός αριθμός.
Αν n | = m | {\displaystyle n|=m|} $n|=m|$ τότε n = m {\displaystyle n=m} $n=m$

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

m + | = m | {\displaystyle m+|=m|} $m+|=m|$
m + n | = ( m + n ) | {\displaystyle m+n|=(m+n)|} $m+n|=(m+n)|$

Ερωτήσεις και απαντήσεις

Ερ: Τι είναι η μαθηματική επαγωγή;

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

Ερ: Πώς γίνεται η απόδειξη μέσω επαγωγής;

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

Ερ: Τι σημαίνει να υποθέσουμε κάτι σε ένα επαγωγικό βήμα;

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

Ερ: Τι είδους αριθμοί χρησιμοποιούνται στη μαθηματική επαγωγή;

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

Ερ: Πώς αποδεικνύεται ότι κάτι είναι αληθές για τον επόμενο αριθμό (n+1);

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