求解直线分割平面所得区域数量上限

问题：求解平面上 $n$ 条直线所界定的区域数量上限 $L_n$。

已知条件：

1. 第 $n(n>0)$ 条直线使得区域的个数增加 $k$ 个，当且仅当它对 $k$ 个已有区域进行分割；
2. 对 $k$ 个已有区域进行分割，当且仅当它在 $k - 1$ 个不同的地方与前面那些直线相交；
3. 两条直线至多相交于一点，因而这条新直线与那 $n - 1$ 条已有直线至多相交于 $n - 1$ 个不同的点。

故必有 $k ≤ n$，则

$$L_n ≤ L_{n - 1} + n \qquad (n > 0)$$

现在证明等号可达：设 $n - 1$ 条直线两两相交于不同的点，放置第 $n$ 条直线与这些直线分别交于不同的点，则第 $n$ 条直线将被 $n - 1$ 条直线分为 $n$ 段，每段都将把一个区域分为两半，则增加 $n$ 个区域。

则递推公式为

$$\begin{cases} L_0 = 1 \\[2ex] L_n = L_{n-1} + n & ( n > 0 ) \end{cases}$$

逐项展开求和

$$\begin{aligned} L_n & = L_{n-1} + n \\ & = L_{n-2} + (n - 1) + n \\ & = \cdots \\ & = L_0 + 1 + 2 + \cdots + (n-1) + n \\ & = 1 + { {n(n+1)} \over {2} } \\ & = 1 + S_n \end{aligned}$$

注：$S_n$ 称为”三角形数“，因为它是一个有 $n$ 行的三角形阵列中元素的个数。

扩展问题：求解平面上 $n$ 条折线所界定的区域数量上限 $Z_n$。

分析：这需要借助“直线”的结论。从上图可知，一条折线的两边向端点方向延伸则可补全为两条相交直线。不同的是，原折线只是把平面分割为了两部分（即区域 1 和区域 2/3/4），而两条相交直线会把平面分割为四部分。则 $n$ 条折线等价于 $2n$ 条直线相交，并除去减少的区域数 $2n$，即

$$\begin{aligned} Z_n & = L_{2n} - 2n \\ & = { {2n(2n + 1)} \over 2 } + 1 - 2n \\ & = 2n^2 - n + 1 \end{aligned}$$