Μαθηματική επαγωγή: θεωρία για μαθηματικούς διαγωνισμούς

Η επαγωγή αποδεικνύει προτάσεις που ισχύουν για κάθε φυσικό \(n\): αθροίσματα, διαιρετότητες, ανισότητες με \(n\).

τα βασικά

Αρχή: δείχνεις ότι η πρόταση ισχύει για το πρώτο \(n\), συνήθως \(n=1\).
Βήμα: υποθέτεις ότι ισχύει για \(n=k\) και αποδεικνύεις ότι ισχύει για \(n=k+1\).
Ισχυρή επαγωγή: στο βήμα υποθέτεις ότι ισχύει για όλα τα \(n\le k\). Χρήσιμη όταν το \(k+1\) εξαρτάται από περισσότερους προηγούμενους όρους.
Συχνή χρήση: αποδείξεις του τύπου \(m\mid a_n\) για κάθε \(n\), π.χ. \(3\mid 4^n-1\).

Να δείξετε ότι \(1+3+5+\dots+(2n-1)=n^2\).

Λύση. Για \(n=1\): \(1=1^2\). Αν ισχύει για \(n=k\), τότε \(1+3+\dots+(2k-1)+(2k+1)=k^2+2k+1=(k+1)^2\), άρα ισχύει και για \(k+1\).

Βήμα που δεν δουλεύει για τα μικρά \(k\). Το γνωστό «όλα τα άλογα έχουν το ίδιο χρώμα» αποτυγχάνει ακριβώς στο πέρασμα από 1 σε 2.