Recursion and Mathematical Induction
Recursion and Mathematical Induction are closely related concepts. This article looks at how they are related. These are the notes from the paper Computational Recursion and Mathematical Induction by Uri Leron, Rina Zazkis.
Mathematical induction provides a powerful tool for proving the correctness of certain useful formulae. Recursive thinking has a parallel in mathematics which is called mathematical induction.
In both techniques, one must:
Determine a set of simple cases for which the proof or calculation is easily handled
Find an appropriate rule which can be repeatedly applied until the complete solution is obtained.
In recursive applications, this process begins with the complex cases and the rule successively reduces the complexity of the problem until only simple cases are left. When using induction, we tend to think of this process in the opposite direction. We start by proving the simple cases and then use the inductive rule to derive increasingly complex results.
A good way to learn mathematical induction is to tackle a problem that admits naturally of an inductive solution. Take for example the problem of how many regions are formed in the plane by n straight lines. Assume no two lines are parallel and no three are concurrent. Since the answer is difficult to see directly from the problem, there is need for investigating.
What is the answer for one line? Two lines? And so on. From here on the investigation may branch into two main routes. The more common one is to look for a pattern in the cases investigated (e g., by arranging the results in a table) and generalize This way one comes to perceive the answer but not the reasons for it.
The second route is to look for a pattern not merely in the sequence of numbers, but in the way they are generated. Rather than the original question:
 How many regions for n lines?
We switch our attention slightly but significantly to the question:
 How many more regions are generated by the addition of one more line?
This is where [inductive thinking]({% post_url 20190620thinkingrecursively %}) begins. This approach is very powerful and potentially very satisfying, for it leads to perceiving the answer as well as the reasons for it, so that it can lead to the feeling that one has really understood the solution.
Didactically, we would tackle this revised question starting with small numbers, and watch for the emerging pattern as we gradually increase n.
Thus suppose we already have 3 lines. How many new regions are formed by adding a fourth line? Can you do that without counting the regions? We would then repeat for 4, 5, etc, until the class is bored.
This boredom is welcome and can be put to good use, for what it expresses  “why do we keep playing the same game over and over?”  is what we are after.
From here, the final step of playing the same game once and for all is not too big to take. That is, we can give the general argument for going from n lines to n + 1 lines even though we do not know the answer for n.
Thus, to summarize, mathematical induction captures the pattern of the argument as we go up from one number to its successor.
References
 Computational Recursion and Mathematical Induction by Uri Leron, Rina Zazkis
 Thinking Recursively by Eric S Roberts
Claude Explanation
Here is content on the relationship between recursion and mathematical induction with the requested structure:
Recursion and mathematical induction are closely connected proof techniques for defining and reasoning about recursive mathematical objects.
The key ideas linking recursion and induction are:
Recursive definitions define objects in terms of simpler instances of themselves, similar to inductive definitions.
Proving a property holds for all cases of a recursively defined object mirrors inductive proof by showing the property holds for base cases and is maintained through recursive calls.
Strong induction extends to inducting on the recursion structure itself, using the inductive hypothesis to show recursive calls maintain the property.
Java  proving correctness of factorial function:


C++  Fibonacci sequence property:


Python  Binary search correctness:


Recursion and induction provide complementary techniques for definition and proof over recursively defined objects.
Recursion and Mathematical Induction
Recursion and Mathematical Induction are closely related concepts. This article looks at how they are related. These are the notes from the paper Computational Recursion and Mathematical Induction by Uri Leron, Rina Zazkis.
Induction
A set of elements can be defined inductively. A inductive definition consists of the following:
 A base clause. A list of one or more initial elements of the set.
 One or more inductive clauses. Rules on how to generate new elements of the set from old ones.
 A final clause. It simply states that no other element is part of the set.
Weak Mathematical Induction
To prove a property by mathematical induction, we proceed as follows:
Base Case
Show that the property holds for the initial elements of the set.
Induction Step
Assume the property hold for some element 𝑛. This is the Induction Hypothesis.Show that the property also holds for any element generated from 𝑛 using the inductive clauses.
Conclusion
The property holds for all elements.
Mathematical Induction
Mathematical induction provides a powerful tool for proving the correctness of certain useful formulae. Recursive thinking has a parallel in mathematics which is called mathematical induction.
In both techniques, one must:
Determine a set of simple cases for which the proof or calculation is easily handled
Find an appropriate rule which can be repeatedly applied until the complete solution is obtained.
In recursive applications, this process begins with the complex cases and the rule successively reduces the complexity of the problem until only simple cases are left. When using induction, we tend to think of this process in the opposite direction. We start by proving the simple cases and then use the inductive rule to derive increasingly complex results.
A good way to learn mathematical induction is to tackle a problem that admits naturally of an inductive solution. Take for example the problem of how many regions are formed in the plane by n straight lines. Assume no two lines are parallel and no three are concurrent. Since the answer is difficult to see directly from the problem, there is need for investigating.
What is the answer for one line? Two lines? And so on. From here on the investigation may branch into two main routes. The more common one is to look for a pattern in the cases investigated (e g., by arranging the results in a table) and generalize This way one comes to perceive the answer but not the reasons for it.
The second route is to look for a pattern not merely in the sequence of numbers, but in the way they are generated. Rather than the original question:
 How many regions for n lines?
We switch our attention slightly but significantly to the question:
 How many more regions are generated by the addition of one more line?
This is where [inductive thinking]({% post_url 20190620thinkingrecursively %}) begins. This approach is very powerful and potentially very satisfying, for it leads to perceiving the answer as well as the reasons for it, so that it can lead to the feeling that one has really understood the solution.
Didactically, we would tackle this revised question starting with small numbers and watch for the emerging pattern as we gradually increase n.
Thus suppose we already have 3 lines. How many new regions are formed by adding a fourth line? Can you do that without counting the regions? We would then repeat for 4, 5, etc, until the class is bored.
This boredom is welcome and can be put to good use, for what it expresses  “why do we keep playing the same game over and over?”  is what we are after.
From here, the final step of playing the same game once and for all is not too big to take. That is, we can give the general argument for going from n lines to n + 1 lines even though we do not know the answer for n.
Thus, to summarize, mathematical induction captures the pattern of the argument as we go up from one number to its successor.
References
 Computational Recursion and Mathematical Induction by Uri Leron, Rina Zazkis
 Thinking Recursively by Eric S Roberts