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 2019-06-20-thinking-recursively %}) 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// Recursive definition
int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n-1);
}

// Proof by induction
Base case: factorial(0) = 1 
Inductive step: Assume factorial(k) = k!
           factorial(k+1) = (k+1) * factorial(k) 
                            = (k+1) * k! // by inductive hypothesis
                            = (k+1)!

C++ - Fibonacci sequence property:

1
2
3
4
5
6
7
8
// Recursive definition
int fib(int n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2);
}

// Inductive proof
// fib(n) is even iff n is divisible by 3 

Python - Binary search correctness:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Recursively defined
def binary_search(lo, hi):
  if lo > hi:
    return False
  
  mid = (lo + hi) // 2
  if match(mid): 
    return True
  elif less(mid):
    return binary_search(lo, mid - 1)
  else:
    return binary_search(mid + 1, hi)

# Proof by induction on recursion depth  

Recursion and induction provide complementary techniques for definition and proof over recursively defined objects.