Chapter 05 - Induction and Recursion

Induction and Recursion

Mathematical Induction

Introduction

In general, mathematical induction can be used to prove statements that assert that is true for all positive integers , where is a propositional function.

• PRINCIPLE OF MATHEMATICAL INDUCTION : To prove that is true for all positive integers , where is a propositional function, we complete two steps:
  • Basis Step : We verify that is true.
  • Inductive Step : We show that the conditional statement is true for all positive integers .

To complete the inductive step of a proof using the principle of mathematical induction, we assume that is true for an arbitrary positive integer and show that under this assumption, must also be true. The assumption that is true is called the inductive hypothesis. Expressed as a rule of inference, this proof technique can be stated as when the domain is the set of positive integers.

Why Mathematical Induction Is Valid ?

The reason comes from the well-ordering property.

• Axiom : The Well-Ordering Property Every nonempty subset of the set of positive integers has a least element.

So, suppose we know that is true and that the proposition is true for all positive integers . To show that must be true for all positive integers , assume that there is at least one positive integer for which is false. Then the set of positive integers for which is false is nonempty. Thus, by the well-ordering property, has a least element, which will be denoted by . We know that cannot be , because is true. Because is positive and greater than , is a positive integer. Furthermore, because is less than , it is not in , so must be true. Because the conditional statement is also true, it must be the case that is true. This contradicts the choice of . Hence, must be true for every positive integer .

Guidelines For Proofs by Mathematical Induction

Before we give these proofs, we will provide some useful guidelines for constructing correct proofs by mathematical induction.

Template for Proofs by Mathematical Induction

• Express the statement that is to be proved in the form “for all ” for a fixed integer .
• For statements of the form ” for all positive integers ,” let , and
• for statements of the form ” for all non-negative integers ,” let .
• For some statements of the form , such as inequalities, you may need to determine the appropriate value of by checking the truth values of for small values of .
• Write out the words “Basis Step.” Then show that is true, taking care that the correct value of is used. This completes the first part of the proof.
• Write out the words “Inductive Step” and state, and clearly identify, the inductive hypothesis, in the form “Assume that is true for an arbitrary fixed integer .”
• State what needs to be proved under the assumption that the inductive hypothesis is true. That is, write out what says.
• Prove the statement making use of the assumption . (Generally, this is the most difficult part of a mathematical induction proof. Decide on the most promising proof strategy and look ahead to see how to use the induction hypothesis to build your proof of the inductive step. Also, be sure that your proof is valid for all integers with , taking care that the proof works for small values of , including .)
• Clearly identify the conclusion of the inductive step, such as by saying “This completes the inductive step.”
• After completing the basis step and the inductive step, state the conclusion, namely, “By mathematical induction, is true for all integers with “.

Strong Induction and Well-Ordering

Strong Induction

Strong induction is sometimes called the second principle of mathematical induction or complete induction. When the terminology “complete induction” is used, the principle of mathematical induction is called incomplete induction. In a proof by strong induction, the inductive step shows that if is true for all positive integers not exceeding , then is true. That is, for the inductive hypothesis we assume that is true for .

• STRONG INDUCTION : To prove that is true for all positive integers , where is a propositional function, we complete two steps:
  • Basis Step : We verify that the proposition is true.
  • Inductive Step : We show that the conditional statement is true for all positive integers .

Using Strong Induction in Computational Geometry

A polygon is a closed geometric figure consisting of a sequence of line segments called sides. Each pair of consecutive sides, and , as well as the last side and the first side , of the polygon meet at a common endpoint, called a vertex. A polygon is called simple if no two nonconsecutive sides intersect. Every simple polygon divides the plane into two regions: its interior, consisting of the points inside the curve, and its exterior, consisting of the points outside the curve. A polygon is called convex if every line segment connecting, two points in the interior of the polygon lies entirely inside the polygon. (A polygon that is not convex is said to be non-convex.) A diagonal of a simple polygon is a line segment connecting two nonconsecutive vertices of the polygon, and a diagonal is called an interior diagonal if it lies entirely inside the polygon, except for its endpoints.

One of the most basic operations of computational geometry involves dividing a simple polygon into triangles by adding non-intersecting diagonals. This process is called triangulation.

• Lemma : Every simple polygon with at least four sides has an interior diagonal.

• Theorem : A simple polygon with sides, where is an integer with , can be triangulated into triangles.

  Proof : Let be the statement that every simple polygon with sides can be triangulated into triangles.

  • Basic Step : is true because a simple polygon with three sides is a triangle. We do not need to add any diagonals to triangulate a triangle; it is already triangulated into one triangle, itself.

  • Inductive Step : For the inductive hypothesis, we assume that is true for all integers with . That is, we assume that we can triangulate a simple polygon with sides into triangles whenever . To complete the inductive step, we must show that when we assume the inductive hypothesis, is true, that is, that every simple polygon with sides can be triangulated into triangles. So, suppose that we have a simple polygon with sides. Because , Lemma tells us that has an interior diagonal . Now, splits into two simple polygons , with sides, and , with sides. The sides of and are the sides of , together with the side , which is a side of both and . Note that and because both and have at least one fewer side than does (after all, each of these is formed from by deleting at least two sides and replacing these sides by the diagonal ). Furthermore, the number of sides of is two less than the sum of the numbers of sides of and the number of sides of R. That is, .

    We now use the inductive hypothesis. Because both and , by the inductive hypothesis we can triangulate and into and triangles, respectively. Next, note that these triangulations together produce a triangulation of . (Each diagonal added to triangulate one of these smaller polygons is also a diagonal of .) Consequently, we can triangulate into a total of triangles. This completes the proof by strong induction.

Recursive Definitions and Structural Induction

Sometimes it is difficult to define an object explicitly. However, it may be easy to define this object in terms of itself. This process is called recursion.

Recursively Defined Functions

We use two steps to define a function with the set of non-negative integers as its domain:

• Basis Step : Specify the value of the function at zero.
• Recursive Step : Give a rule for finding its value at an integer from its values at smaller integers.

Such a definition is called a recursive or inductive definition.

• Theorem : Lamé’s Theorem Let and be positive integers with . Then the number of divisions used by the Euclidean algorithm to find gcd is less than or equal to five times the number of decimal digits in .

Recursively Defined Sets and Structures

• Definition : The set * of strings over the alphabet is defined recursively by
  • Basis Step : * (where is the empty string containing no symbols).
  • Recursive Step : If * and , then * .
• Definition : Two strings can be combined via the operation of concatenation. Let be a set of symbols and * the set of strings formed from symbols in . We can define the concatenation of two strings, denoted by , recursively as follows.
  • Basis Step : If *, then , where is the empty string.
  • Recursive Step : If * and * and , then .

Another important use of recursive definitions is to define well-formed formulae of various types.

• Well-Formed Formulae in Propositional Logic : We can define the set of well-formed formulae in propositional logic involving , propositional variables, and operators from the set .
  • Basis Step : and where is a propositional variable, are well-formed formulae.
  • Recursive Step : If and are well-formed formulae, then and are well-formed formulae.

Recursive Algorithms

• Definition : An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input.

We will now see a recursive algorithm for computing mod , where and are integers with and .

• Algorithm : Recursive Modular Exponentiation. procedure ( : integers with and , ) if then return 1 else if is even then return mod else return ( mod mod ) mod {output is mod }

Recursion and Iteration

A recursive definition expresses the value of a function at a positive integer in terms of the values of the function at smaller integers. This means that we can devise a recursive algorithm to evaluate a recursively defined function at a positive integer. Instead of successively reducing the computation to the evaluation of the function at smaller integers, we can start with the value of the function at one or more integers, the base cases, and successively apply the recursive definition to find the values of the function at successive larger integers. Such a procedure is called iterative.

• Algorithm : A Recursive Algorithm for Fibonacci Numbers. procedure ( : nonnegative integer) if then return else if then return else return {output is }

The Merge Sort

A merge sort begins by splitting the list into individual elements by successively splitting lists in two. Sorting is done by successively merging pairs of lists. At the first stage, pairs of individual elements are merged into lists of length two in increasing order. Then successive merges of pairs of lists are performed until the entire list is put into increasing order. In general, a merge sort proceeds by iteratively splitting lists into two sublists of equal length (or where one sublist has one more element than the other) until each sublist contains one element. This succession of sublists can be represented by a balanced binary tree. The procedure continues by successively merging pairs of lists, where both lists are in increasing order, into a larger list with elements in increasing order, until the original list is put into increasing order. The succession of merged lists can be represented by a balanced binary tree.

• Algorithm : A Recursive Merge Sort. procedure if then { is now sorted into elements in non-decreasing order}

• Algorithm : Merging Two Lists. procedure ( : sorted lists) empty list while and are both nonempty remove smaller of first elements of and from its list; put it at the right end of if this removal makes one list empty then remove all elements from the other list and append them to L return is the merged list with elements in increasing order

• Lemma : Two sorted lists with elements and elements can be merged into a sorted list using no more than comparisons.

• Theorem : The number of comparisons needed to merge sort a list with elements is .