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.