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

Η (μαθηματική) επαγωγή είναι µία απλή αλλά ισχυρή και ευέλικτη μέθοδος απόδειξης προτάσεων που αφορούν, άµεσα ή έµµεσα, ακεραίους. Έχει χρησιµοποιηθεί µε επιτυχία σε σχεδόν όλο το φάσµα των µαθηµατικών: την συναντάµε σε μεγάλο εύρος κλάδων όπως στην Άλγεβρα, στην Γεωµετρία, στην Τριγωνοµετρία, στην Ανάλυση, στην Συνδυαστική, στην Θεωρία Γραφηµάτων και σε πολλούς άλλους κλάδους.

Η αρχή της επαγωγής έχει µακρά ιστορία στα µαθηµατικά. Κατ΄ αρχάς, παρ’ όλο που η ίδια η αρχή δεν διατυπώνεται µε σαφήνεια σε κανένα αρχαίο ελληνικό κείµενο, υπάρχουν αρκετά σηµεία όπου γίνεται χρήση ενός πρόδροµου σταδίου της. Άλλωστε ορισµένοι ιστορικοί αναγνωρίζουν στο ακόλουθο χωρίο από τον διάλογο Παρµενίδη (§147a7-c3) του Πλάτωνα (427-347 BC) ως την αρχαιότερη χρήση επαγωγικού συλλογισµού:

Και πρέπει να υπάρχουν τουλάχιστον δύο όροι, εάν πρόκειται να υπάρχει επαφή. – Πρέπει – Εάν δε στους δύο όρους προστεθεί τρίτος διαδοχικά, τότε αυτοί µεν θα είναι τρεις, οι δε επαφές δύο. – Ναι – Και έτσι αν ένας όρος προστίθεται συνέχεια, και µία επαφή θα προστίθενται, και έπεται ότι οι επαφές θα είναι µία λιγότερες από το πλήθος των όρων. ∆ιότι µε όποιον αριθµό τα δύο πρώτα υπερέχουν του πλήθους των επαφών, µε το ίδιο αριθµό το µετέπειτα πλήθος των όρων θα υπερβαίνει το πλήθος των επαφών. ∆ιότι κατόπιν όταν προστίθεται ένας όρος, προστίθεται και µία επαφή στο πλήθος των επαφών. – Σωστά – Όσο λοιπόν είναι το πλήθος των όρων, πάντα οι επαφές θα είναι κατά µία λιγότερες. –Σωστά -.

Το προηγούµενο χωρίο είναι, βέβαια, από φιλοσοφικό κείµενο. Υπάρχουν όµως και διαφορά µαθηµατικά έργα τα οποία περιέχουν µια πρώιµη µορφή επαγωγικού συλλογισµού. Ένα τέτοιο, παραδείγµατος χάριν, είναι στα Στοιχεία του Ευκλείδη (~330 – ~ 265 π.Χ.) Πρόταση 31 του βιβλίου VII, όπου αποδεικνύεται ότι κάθε φυσικός αριθµός είτε είναι πρώτος είτε διαιρείται από κάποιον πρώτο. Μία απόδειξη κάπως πιο κοντά στη σύγχρονη µορφή της επαγωγής περιέχεται στην Συναγωγή του Πάππου (~290-~350 µ.Χ.). Εκεί αποδεικνύεται το ακόλουθο γεωµετρικό θεώρηµα:

Έστω AB ένα ευθύγραµµο τµήµα και C ένα σηµείο του. Θεωρούµε από την ίδια πλευρά του AB τρία ηµικύκλια µε διαµέτρους AB, AC και CB, αντίστοιχα. Κατασκευάζουµε τώρα κύκλους Cn ως εξής: ο C1 εφάπτεται των τριών παραπάνω ηµικυκλίων. Ο Cn+1 εφάπτεται του Cn και των ηµικυκλίων επί των AB και AC. Αν dn το µήκος της διαµέτρου του Cn και hn η απόσταση του κέντρου του από την AB. Τότε hn = n dn.

Ο τρόπος µε τον οποίο αποδεικνύει το θεώρηµα ο Πάππος είναι να δείξει γεωµετρικά την αναδροµική σχέση hn+1/dn+1 = (hn + dn)/dn. Κατόπιν επικαλείται ένα αποτέλεσµα του Αρχιµήδη (287 – 212 π.Χ.) από το έργο του Λήµµατα (Πρόταση 6) η οποία δείχνει την ορθότητα του παραπάνω θεωρήµατος στην περίπτωση n=1. Χρησιµοποιώντας την τελευταία σε συνδυασµό µε την αναδροµική σχέση, συνάγει το αποτέλεσµα για το γενικό n.