Day 20: CM, Page 7

An expression for a quantity f(n) is in closed form if we can compute it using at most a fixed number of "well known" standard operations, independent of n.
Concrete Mathematics, p.7

Day 20: The authors point out that we haven't really proven that our closed form matches the recurrent equations for lines in plane. How do we prove it? We can use the same technique that was used for the Tower of Hanoi.

Trying to prove: L(n) = n(n+1)/2 + 1
Base case: L(0) = 1 (with no lines, we have one region - matches recursive form).
Inductive Hypothesis: Assume the closed form (n(n+1)/2)+1 holds for n-1.
Assume L(n) = L(n-1) + n is true

Then:
So by induction, L(n) = n(n+1)/2 + 1 is true.

The authors go on to discuss closed forms. The general idea is that a closed form cannot have "..."s in it. We must be able to use a fixed number of "well known" operations to solve a closed form equation. Some recurrences don't have closed forms. In those cases, if the recurrences are important, we can invent new notation that allows us to treat them as closed form. For example, n! is considered closed form even though it is defined recursively. It is important enough and simple enough that we allow it to be part of our closed form equations.

Finally, a variation on the "lines in a plane" problem is presented: "zigs in a plane". A zig in plane is like a ">" - two lines that meet at a point and stop. One zig creates two regions - one region on one side of the zig and one on the other side. So Z(1) = 2.

Before reading ahead I took a stab at the problem. The authors come up with a much simpler solution on the next page, but here's one way to approach the problem.

First, look at easy cases.
Z(0) = 1 (no zigs, one region)
Z(1) = 2 (one zig, two regsions)
Z(2) = 7
Z(3) = 16

After n=3, it gets hard to draw the picture. From the small cases above, it's hard to find a definite pattern. Let's see if we can find a recursive equation. I approached this problem roughly the same way I approached lines in a plane. I tried to understand how many regions were formed as lines crossed one another. For n=1, there are no lines to cross, so I take n=0 and n=1 as base cases. Next, I look at n=2. For n=2, the first line in the zig crosses both lines from n=1. Each time it hits a line it forms a new region (2 new regions). The zig crosses the two lines again. It forms a new region when it hits each line plus one new region when it crosses the last line (3 new regions). So we have a total of 2 + 3 new regions or 2(n-1) + 2(n-1) + 1 regions.

So the recursive formula looks like:
Z(0) = 1
Z(1) = 2
Z(n) = Z(n-1) + 4n - 3

Testing on a few small numbers, this works.
Z(2) = 2 + 4(2) - 3 = 7
Z(3) = 7 + 4(3) - 3 = 16

Now, let's see if we can find a closed form. We'll try the same method we used last time and unwind the recursive formula.

Z(n) = Z(1) + ... + Z(n-3) + (4(n-2) -3) + (4(n-1) - 3) + (4n - 3)

There is a lot of repetition here. We should be able to pull out some of the common patterns. -3 appears n-1 times. It is n-1 rather than n because Z(1) is part of our base case and we do not expand it. 4n also appears n-1 times. What we have left is ... - 4(2) - 4(1) - 4(0). This look like a triangular number times -4. The sum only goes to n-2 because Z(1) is not expanded and and the nth term in the expansion has 4(0). Putting it all together we have:


Now let's see if we can prove it by induction.

Base case - we'll do a few just for extra confirmation:
Z(0) = 2(0^2) - 0 + 1 = 1
Z(1) = 2(1^2) - 1 + 1 = 2
Z(2) = 2(2^2) - 2 + 1 = 7

We'll assume our recursive formula is correct Z(n) = Z(n-1) + 4n - 3
And we'll assume our inductive hypothesis is true - that our closed form is correct for n-1.

So the formula is true by induction. One curious thing about these inductive proofs is that we need to assume the recursive form is correct, but we have not rigorously proved that it is correct. The authors currently seem more concerned with problem solving tools than giving a rigorous proof, so we won't worry about it for now.

Tomorrow, we'll look at a different approach to the zig problem.