Day 29: CM, Page 15

Day 29: I've skipped a couple of days. This is the last page of chapter one - one more page of the Josephus problem. The authors do one final generalization of the Josephus problem. Suppose we take our previous recurrence:

f(1) = alpha
f(2n+j) = 2f(n) + BetaSubJ

And generalize it to:

f(j) = alphaSubJ where 1 <= j <= d
f(dn+j) = cf(n) + betaSubJ where 1 < = j <= d and n >= 1

Given any recurrence that fits this pattern, we can solve it by converting from a number in base d to a number in base c (as we did yesterday for the base 2 to base 2 conversion). For example, suppose we have the recurrence:

f(1) = 1
f(2) = 2
f(3n) = 10f(n) + 1
f(3n+1) = 10f(n) - 2
f(3n+2) = 10f(n) + 3

To calculate f(10):
10 = 101 base 3
f(10) = f((101)b3) = (1 1 -2)b10 = 100 + 10 - 2 = 108

Pretty neat. That's it for chapter 1.

Day 28: CM, Page 15

Day 28: The authors continue to generalize the Josephus problem. We noticed a few days ago that the Josephus problem can be represented as cyclic left bit shift. Can we generalize that observation to our more general equations with alpha, beta, and gamma? Yes, we can...

First, rewrite our recurrences as:
f(1) = alpha
f(2n + j) = 2f(n) + betaSubJ for j=0,1 and n>=1

For j=0, betaSubJ = beta and for j=1, betaSubJ = gamma. Then by the equations above:

Sure enough, if we consider the original problem with alpha=1, beta=-1, gamma=1, we have something like:

100 = (1100100)
f(1100100) = alpha gamma beta beta gamma beta beta
f(1100100) = (1 1 -1 -1 1 -1 -1) = 64 + 32 - 16 - 8 + 4 - 2 - 1 = 73

We've had to "relax" the binary representation to allow betas and gammas that are not equal to 0 or 1. But this is still and interesting result.

One more page of the Josephus problem tomorrow and then it's on to the exercises.

Day 27: CM, Page 14

Day 27: The authors introduce the repertoire method by an example with the Josephus problem. Recall from yesterday that we believe:

A(n) = 2^m
B(n) = 2^m - 1 - l
C(n) = l

How can we prove this? One way is to find a series of equalities based on specific data points, then to solve those equalities. No hints yet on how to find the specific data points to form the equalities. The authors make a few clever observations to find their data points. We'll assume that f(n) = A(n)(alpha) + B(n)(beta) + C(n)(gamma).

What happens in the case where alpha=1, beta=0, gamma=0? We have f(n) = A(n) or:

A(1) = 1
A(2n) = 2A(n)
A(2n+1) = 2A(n)

We want to show that A(n) = 2^m. This follows from the equations above by induction. A(1) = 1 since A(1) = alpha. Assume A(n/2) = 2^(m-1). Then:

A(n) = A(2^m + l) = 2A((2^m + l)/2) = 2(2^(m-1)) = 2^m.

Next we want some other interesting data points. What are some other values for alpha, beta, and gamma that make it easy to solve our recurrences? How about f(n) = 1:

1 = alpha
1 = 2*1 + beta
1 = 2*1 + gamma

For this to be true, alpha=1, beta=-1, and gamma=-1. Plugging that back in, we get:

A(n) - B(n) - C(n) = f(n) = 1

What happens if f(n) = n? In that case:

1 = alpha
2n = 2n + beta
2n+1 = 2n + gamma

So in this case, alpha=1, beta=0, and gamma=1. Plugging that back in, we get:

A(n) + C(n) = n

Now that we have three inequalities, we can solve them. From our first observation, we directly have A(n) = 2^m

That gives us:
A(n) + C(n) = n
C(n) = n - A(n) = 2^m - l - 2^m = l

Which matches what we expect. And finally:

A(n) - B(n) - C(n) = 1
B(n) = A(n) - C(n) - 1
B(n) = 2^m - l - 1

And that matches all our observations for A(n), B(n), and C(n) of:

A(n) = 2^m
B(n) = 2^m - l - 1
C(n) = l

This is an illustration of the repertoire method. There are still some questions to work out - how do we choose the right specific data points to use for our equalities? I suspect we'll return to this in the exercises. More on the Josephus problem tomorrow.

Day 26: CM, Page 13

Day 26: The Josephus problem continued. The authors generalize the Josephus problem even further. They ask the question: how would we find a closed form for the recurrence if the pattern had been more complex? What if the coefficients on the recurrence were something besides -1 and +1? To generalize the recurrence:


By expanding the recurrence, we can build a table of values for f(n):


If we write f(n) as:
Then, it appears that:
More on these equations tomorrow.

Day 25: CM, Page 12

Day 25: I've missed a couple of days. I'm now on pace for Nov 5, 2016.

The authors continue to examine the binary representation of the Josephus function. They observe that since the solution to the Josephus problem is a cyclic left bit shift, you might expect that m iterations of the function would return to the original number. However, this is not true because zeros are removed from the number during the shifting process. For example:

J(1101) = 1011
J(1011) = 0111 = 111
J(111) = 111

For a given number, you can find the convergent number by counting the number of 1's in the original number's binary representation. The point of convergence can be defined as 2^v(n) - 1 where v(n) is the numbers of 1's in n.

More on the Josephus problem tomorrow. The authors continue to generalize it even further.

Day 24: CM, Page 11

Day 24: The authors prove the closed form of the Josephus problem by induction. They prove the odd and even cases separately.

Base case: J(1) = J(2^0 + 0) = 2(0) + 1 = 1
Assume: J(2n) = 2(J(n)) - 1 and J(2n + 1) = 2(J(n)) + 1
Inductive Hypothesis Even: J(n/2) = J(2^(m-1) + l/2) = 2l/2 + 1
Inductive Hypothesis Odd: J((n-1)/2) = J(2^(m-1) + (l-1)/2) = 2(l-1)/2 + 1

This a different twist on the normal induction process. Rather than assuming n-1 is true, we are assuming n/2 is true for all even numbers. Then:

And a similar proof for odd numbers:


Together, the two proofs cover all even and odd numbers. Next the authors suggest trying to generalize the problem. There seems to be a relationship in the problem between powers of 2, so let's represent the problem in binary.


That last step follows because J(n) = 2l + 1 and b sub m = 1. This is a pretty interesting result. J(n) can be calculated by doing a one bit cyclic left shift on n. More details from the CM authors tomorrow about this new observation tomorrow.

Day 23: CM, Page 10

Day 23: The Josephus problem continued. Yesterday we found a recursive solution for the Josephus problem with an even number of people. With an odd number of people, the recursive solution is similar.

Consider J(2n + 1). If you start with 1 2 3 4 5 6 7 8 9, after the first round of elimination you have 1 3 5 7 9. But wait! This isn't right. To continue the elimination process, we would need to eliminate 1 next, so new sequence isn't quite correct - it's off by one if we want to skip the first member of the sequence on the second iteration. To keep the iteration consistent (always skipping the first element in a sequence), we need to eliminate one more element. So 1 2 3 4 5 6 7 8 9 is actually the same as 3 5 7 9 where 1 is included in the first round of elimination. Now on the second round of iteration we start with 5 as expected. 3 5 7 9 is the same problem as 1 2 3 4 except that each number is doubled and incremented by 1. So J(2n + 1) = 2(J(n)) + 1.

So we have:
J(1) = 1
J(2n) = 2(J(n)) - 1
J(2n + 1) = 2(J(n)) + 1

And with that we have a recursive formula to describe a solution to the problem. The authors use the recursive formula to describe the pattern we saw a couple of days ago, but they find a better notation to represent the closed form.

J(n) = J(2^m + l) = 2l + 1

Where 2^m <= n < 2^(m+1) and l is the remainder (or leftover) of n/2^m. Also note: l < 2^m

With this we have a closed form representation of the Josephus problem. Tomorrow we'll need to prove it, and authors have some additional interesting observations about the problem.

Day 22: CM, Page 9

Day 22: The authors examine the Josephus problem. They start by looking at small examples. When they fail to find a pattern, they try to find a recurrence. Rather than finding a single equation, they break the problem into even and odd numbers of people.

Starting with an even number of people, after the first round we're left with exactly half as many people.

1 2 3 4 5 6 7 8 9 10
1 3 5 7 9

1 3 5 7 9 is the same as 1 2 3 4 5 except that each person's number is double and decreased by 1. So:

J(2n) = 2(J(n)) - 1

In other words 1 2 3 4 5 6 7 8 9 10 will have the same solution as 1 2 3 4 5 where each number is doubled (2 4 6 8 10) and decreased by 1 (1 3 5 7 9) since we know all the even numbers in the first sequence will be eliminated. The key here is that the authors have found a notation that allows the problem to be expressed as a sub-problem of itself. Pretty ingenious!

We'll take a look at odd numbers tomorrow.

Day 21: CM, Page 8

Day 21: The authors find a cleaner solution to zig problem. Rather than derive the closed form by expanding a recurrent form, they notice a relationship between zigs and lines in a plane. A zig is the same as two intersecting lines except that the lines don't continue after they meet. Since the lines in both problem only intersect one another once, we don't need to worry about intersection after the zig if we always ensure the lines intersect before the zig. And if the lines intersect before the zig, we'll have the same number of regions as lines in plane minus the regions after the zig. For each zig, we only loose two regions (one for each line that is lost). So zigs are related to lines in a plane as follows:

Z(n) = 2(L(n)) - 2n

If we expand that we have:

2(n(n+1))/2 + 1 - 2n =
n^2 + n + 1 - 2n =
n^2 -n + 1

Which matches what we found yesterday.

Next the author introduces the Josephus problem. There is a story behind this problem. Josephus was a famous historian of the first century. During the Jewish-Roman war, Josephus was trapped in a cave with 40 other Jewish rebels. They decided to kill themselves rather than surrender. They got in a circle and had every third person kill himself. Josephus and a conspriator decided they didn't want to kill themselves and quickly calculated where to position themselves in the circle so that they were the last ones standing. How did Josephus perform the calculation?

Reading ahead a little authors begin by looking at the same problem, but hop two people instead of three. Lets look at some small examples where every second person is killed.
J(1) = 1
J(2) = 1
J(3) = 3
J(4) = 1
J(5) = 3
J(6) = 5
J(7) = 7
J(8) = 1
J(9) = 3
J(10) = 5
J(11) = 7
J(12) = 9
J(13) = 11
J(14) = 13
J(15) = 15
J(16) = 1

So it appears that the solution depends on n's position relative to the most recent power of 2. It looks like J(n) = 1 + 2(n - "last power of 2")

J(3) = 1 + 2(3-2) = 3
J(4) = 1 + 2(4-4) = 1
J(11) = 1 + 2(11 - 8) = 7
J(15) = 1 + 2(15 - 8) = 15

Tomorrow, we'll see how the authors approach the problem. Here's a statue of Josephus:

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.

Day 19: CM, Page 6

We can often understand a recurrence by "unfolding" or "unwinding" it all the way to the end.
- Concrete Mathematics, p. 6

Day 19: More discussion of lines in the plane. The authors suggest that the recurrence that defines the max number of regions defined by n lines in a plane is:

L(0) = 1
L(n) = L(n-1) + n

See yesterday's post for more background on the problem.

The authors point out a new technique for finding the closed form solution: unwind a recursive formula.

L(n) = L(n-1) + n
L(n) = L(n-2) + (n-1) + n
L(n) = L(n-3) + (n-2) + (n-1) + n
...
L(n) = L(0) + 1 + 2 + ... + (n-2) + (n-1) + n

We know from earlier posts, that the sequence 1 + 2 + ... + (n-1) + (n-1) + n is equal to n(n-1)/2.

That's it for today. Not too much new. More on lines in the plane tomorrow.

Day 18: CM, Page 5

Day 18: We're done with the Tower of Hanoi. The authors look at a different problem that will us practice the analytical skills we just learned. The question is: "What is the maximum number L(n) of regions defined by n lines in the plane?" First we look at small cases:


This picture skips n = 0 which is 1 - there is one region if there are no lines. From the sequence above, a pattern jumps out. The difference between the number of regions for each value of n is 1, 2, 3, 4. This is the same pattern as the difference between triangular numbers. In fact, the numbers look like 1 + (n(n+1)/2). But what if we didn't notice the pattern? Is there a more logical approach to this problem?

For each region that we split with a line, we make two regions - one region on one side of the line, and one region on the other side of the line. So if we split k regions, we make k new regions. So how do regions relate to the number of lines? It looks like we need to cross k-1 lines to make k regions. I'm not sure how to prove this.. but the idea is roughly as follows: when a new line hits the first line it will intersect, it has crossed one region and thus formed one new region; each line it hits after that forms one more region. As it crosses the last line and enters the final region, it forms one last region. So for each line we hit, we form one region except for the last line where we form two regions. Thus for k-1 intersected lines, we form k regions. Assuming that none of the lines we draw is parallel, the nth line will intersect all previous n-1 lines in one spot. That means it will form n new regions. So L(n) = L(n-1) + n for n > 0.

More on intersecting lines tomorrow.

Day 17: CM, Page 4

One of the main objecties of this book is to explain how a person can solve recurrences without being clairvoyant.
- Concrete Mathematics p. 4

Day 17: The authors give an outline for solving problems like the Tower of Hanoi:

1. Look at small cases...
2. Find and prove a mathematical expression for the quantity of interest...
3. Find and prove a closed form for our mathematical expression...
- CM p.4

This is the approach we just went through yesterday for the Tower of Hanoi. The authors explain that the rest of the book is focused on helping us find closed forms without brilliant leaps of insight. They give an example of one technique: change the form of an equation to reveal underlying patterns.

Suppose U(n) = T(n) + 1. Then if we add one to both sides of our recurrence, we have:
T(0) + 1 = 1
T(n) + 1 = 2(T(n-1)) + 2 = 2(T(n-1) + 1)

So:
U(0) = 1
U(n) = 2(U(n-1))

After restructuring the problem slightly, it is clear that the closed form of U(n) is 2^n. So T(n) = U(n) -1 = 2^n - 1.

To rephrase the author's suggestion, when solving a problem like this, we need to:
1. Look at small cases
2a. Find some notation that provides an answer to the problem.
2b. Try to represent the solution so that the underlying pattern or structure is more apparent.
2c. Try to find a different way to look at the problem (e.g. binomial coefficients can be looked at probabilistically or as a summation).
3. Based on the tricks above (plus any others), find a closed form.

Tomorrow we'll look how to slice a pizza to achieve maximum slices.

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

Day 15: CM, Page 2

... we'll see repeatedly in this book that it's advantageous to LOOK AT SMALL CASES first.
- Concrete Mathematics p.2

The next step in solving the problem is to introduce appropriate notation: NAME AND CONQUER.
- Concrete Mathematics p.2

Day 15: Two of the most important tools in problem solving are introduced: look at small cases and find a good notation. Looking at small cases is especially important. This is useful for problem solving in almost any context. It's often easy to spot patterns by examining the simplest cases first.

For Tower of Hanoi problem, the authors note that T(1) = 1 (it takes one move to move one disk), T(2) = 3 (it takes three moves to move two disks) and T(0) = 0 (it takes no move to move no disks). How would we move three disks? We already have a way to move 2 disk, so first we would move two disks, then we would move the third disk, and finally we would move the two disks back onto the third. This is a recursive solution. If we can solve the problem for T(n-1), we can solve it for T(n).

The authors use the observation above to show that T(n) <= 2(T(n-1)) + 1. This is true, because we can move the top n-1 disks to one peg, move the bottom disk, then move the n-1 disks onto the bottom disk. We know this solution takes 2(T(n-1)) + 1 moves, but maybe there is a solution that takes fewer moves? Nope. The authors point out that when we move the nth disk, the other n-1 disks must be on another peg. So in the best case, we still need to move n-1 pegs to the other disk. There's no other option. So T(n) >= 2(T(n-1)) + 1 (it's possible you could do worse than 2(T(n-1)) + 1 if you make bad moves).

That's it for page 2. More on the Tower of Hanoi tomorrow.