A Proof Theoretic Exploration of Mathematical Induction in Computational Paradigm
A. Tarek Abouelfadl Mohamed, Ahmed Alveed, Ahmed Farhan · 2023
In the world of computing, there exists a wide variety of direct and indirect proof techniques for proving new results and propositions. Among the persisting proof techniques, Mathematical Induction (MI) stands out to be a powerful one for proving propositions, theorems, as well as the new results. MI is strongly founded upon the basis, and the inductive hypothesis. The Mathematical Induction techniques may be broadly classified into three categories, such as, the Weak Induction, the Strong Induction, and the Structural Induction. In this expository paper, several variations of mathematical induction technique are explored, and the specific computational scenarios are considered where a particular variation of mathematical induction emerges as more beneficial compared to other variations. Also, the essential differences among the mathematical induction vari-ations are taken into account. The computational strategies for mathematical induction, recursion, and logical deduction are also analyzed, and the relationships among variations of recurrence relations, and mathematical induction are being established. From an application perspective, recurrence re-lations, and mathematical inductions are considered together in a single framework for analyzing codewords over a given Alphabet.