Number of Regions in the Plane defined by $n$ Zig-Zag Lines 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!
 A: $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.

A: 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.
A: What also works is:
When you assume first assume that, for every zig zag line, there are two parallel infinite lines and one infinite line intersecting both (so we extend our line segments). 
Now, for the case of the zig zag lines, every parallel line stops at the intersection with the third line, so you have to subtract 2 regions from $L_{3n}$ for every zig zag line. The third line is bounded in two directions, so you have to subtract two additional regions for each zig zag line. The last step is to subtract 1 region because the two parallel lines don't intersect. 
So $$ZZ_n = L_{3n} - 5n = \frac{9n^2+3n}{2}-5n+1 = \frac{9n^2+3n}{2} - \frac{10n}{2} +1 = \frac{9n^2-7n}{2} + 1$$
A: I figured a different approach. We all know by now, 


*

*Finding 1: Each new zig-zag will intersect each old zig-zags at $9$ points.

*Finding 2: When two zig-zags intersect, they create $8$ finite regions around intersections (see colored regions from the picture of bryanj's answer).


Let's assume each zig-zag is so thin that it can be drawn as a line (two parallel lines are too close to each other) and the segment connecting two parallels is quite long. Now to draw the $n$ zig-zags on a plane, first we will draw $n$ lines on that plane intersecting each other. Then we will replace $n$ lines with $n$ 'thin' zig-zags I was talking about. 
For example, if $n = 3$, we draw 'simple lines' first, and we get 7 regions (See the picture below). It has $L_3 = 7$ regions and $\binom{3}{2} = 3$ intersections. 

Now replacing 'simple lines' with zig-zags, we get, this picture. 

So, $L_3 = 7$ regions are still there. For each of $\binom{3}{2} = 3$ intersections, we get $8$ regions (from finding 2). Total $L_3 + 8\times\binom{3}{2}$ regions. 
Finally, for $n$ zig-zags, $ZZ_n = L_n + 8\times\binom{n}{2}$
