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!
Best Answer
$ZZ_n = ZZ_{n-1} + n + 8(n-1)$.
Add one new straight line first, intersecting the previous $n-1$ lines. This gives the term $n$. Then make the small ziz-zags as suggested in the hint. This adds an additional $8$ regions at each of the $n-1$ intersections.