Day 16: CM, Page 3

Day 16: We learn some basic vocabulary today.

"... a recurrence (a.k.a. recurrence relation or recursion relation)... gives a boundary value and equation of the general value in terms of earlier ones" (CM p.3).

The following equalities define a recurrence for the Tower of Hanoi problem:
T(0) = 0;
T(n) = 2(T(n-1)) + 1;

The first equation is the boundary value of the equation. The second equation is general value - it is defined in terms of earlier values.

Notice that if n is very large, it is hard to compute T(n) - you need to know all the previous values. The recurrence defines local information or relative information. What we'd like is a closed form. The authors don't define a closed form yet, but the general idea is we'd like an equation that would let us calculate T(n) directly without knowing previous values.

How do we find a closed form? The authors suggest that one way is to guess the closed form and then prove that it is true. We can guess the closed form by looking at small cases first. If we look at the first six values, we have:
T(0) = 0
T(1) = 1
T(2) = 3
T(3) = 2*3+1 = 7
T(5) = 2*7+1 = 15
T(6) = 2*15+1 = 31

It looks like T(N) = 2^n - 1. To prove it, we can use induction. "Mathematicl induction is a general way to prove that some statement about the integer n is true for all n >= n sub 0." First you prove the statement for the first integer, n sub 0. This is called the basis. Next you assume you have proven the statement for all values between n sub 0 and n-1. Then you prove the statement for n. This is called the induction.

To see how induction works, let's try to prove the closed form of the recurrent equations above. The basis in this case is n=0. It is easy to prove: T(0) = 0 since it takes no moves to move no disks. And 2^0 - 1 = 0. So the basis holds. Now let's assume our recurrence above is true and T(n) = 2(T(n-1)) + 1. Let's also assume the formula we are trying to prove is true for n-1: T(n-1) = 2^(n-1) - 1. Substituting our closed form for n-1 into our recurrence for n gives: T(n) = 2(2^(n-1) -1) + 1= 2^n - 1. Therefore the closed form is also true.

Let's get some different points of view on the terminology introduced on this page.

In mathematics, a recurrence relation is an equation that defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms... Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n.
-wikipedia

The wiki page also has a discussion of different methods for finding closed forms of recurrence relations. Here is a definition of closed forms from wikipedia:

In mathematics, an expression is said to be a closed-form expression if, and only if, it can be expressed analytically in terms of a bounded number of certain "well-known" functions. Typically, these well-known functions are defined to be elementary functions; so infinite series, limits, and continued fractions are not permitted. Similarly, an equation or system of equations is said to have a closed-form solution if, and only if, at least one solution can be expressed as a closed-form expression.
-wikipedia

And here is a description of mathematical induction:

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one
-wikipedia

Note: this is different than inductive reasoning. Inductive reasoning is drawing conclusiong based on a limited series of observations. For example: if all the ice I've touched is cold, then ice is cold.

Here is a further description of mathematical induction:

The simplest and most common form of mathematical induction proves that a statement involving a natural number n holds for all values of n. The proof consists of two steps:

1. The basis (base case): showing that the statement holds when n = 0.
2. The inductive step: showing that if the statement holds for some n, then the statement also holds when n + 1 is substituted for n.

The assumption in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for n + 1.

The description above of the basis applies when 0 is considered a natural number, as is common in the fields of combinatorics and mathematical logic. If, on the other hand, 1 is taken to be the first natural number, then the base case is given by n = 1.

This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly. It may be helpful to think of the domino effect; if one is presented with a long row of dominoes standing on end, one can be sure that:

1. The first domino will fall
2. Whenever a domino falls, its next neighbor will also fall,

so it is concluded that all of the dominoes will fall, and that this fact is inevitable.

-wikipedia