Fellows of Math.SE, I have been scratching my head at a solution to an exercise in Donald Knuth's Concrete Math. Here is the problem:
Here is the solution (I hid it in case someone wants to solve this on their own)
Given $n$ straight lines that define $L_n$ regions, we can replace them by extremely narrow zig-zags with segments sufficiently long that there are nine intersections between each pair of zig-zags. This shows that $ZZ_n = ZZ_{n−1} +9n−8$, for all $n > 0$; consequently $ZZ_n = 9S_n −8n+1 = \frac{9n^2 − 7n}{2} +1$.
$L_n$ is the number of regions definable by $n$ lines, which is solved as an example earlier in the text. It equals $S_n + 1$, where $S_n = \sum_{k=1}^n k$. I am having difficulty understanding the recurrence solution. I'll hide my question, just to be extra careful I don't spoil this wonderful problem for anyone.
Where does the "$-8$" come from? Is the recurrence better understood as $ZZ_n = ZZ_{n−1} +9(n-1)+1$? Or does that further convolute the meaning of the recurrence? I figure there must "-8" must have to do with "lost regions" due to the half-lines, but I am having trouble putting my finger on it.
I really love this problem and would love to understand the solution in its entirety! Thank you!
Your observation is correct. If you believe the first step, then there are $9(n-1)$ intersections of the new zigzag with the existing constelation. Now any two consecutive intersection points cut an existing bounded region into two regions, resulting in a total of $9(n-1)-1$ regions. Similarly the line segment between the first intersection and infinity and the line segment bewteen the last intersection and infinity each cut an existing unbounded region into two. So there are $9(n-1)-1+2$ new regions.