交點個數、分割的區域個數的遞迴關係式

這裡有幾道常見的問題，我列出遞迴關係式，雖然都可以寫出一般項(第n項)的通式，但不是這裡的重點，所以就不寫出來了。

1.          在平面上有n條直線，任三條相異直線皆可圍成三角形(即任兩條直線不平行，任三條直線不共點)，則共有a_n個交點，且可將平面分割成b_n個區域。

很容易可以看出來，第n條直線可以與前n－1條直線各交於一點，故交點的總數可寫出遞迴關係式a_n＝a_n－1＋n－1，其中n＞1，邊界條件(boundary condiction)為a₁＝0；第n條直線可被前n－1條直線截成n個線段或射線，這n個線段或射線分別在前n－1條直線所分割成的b_n－1個區域中的n個區域，且將所在的區域一分為二，故b_n比b_n－1多出n，即b_n＝b_n－1＋n，其中n＞1，邊界條件為b₁＝2。

2.          在平面上有n個圓或橢圓，且任兩個圓或橢圓均相交於兩點，任三個不會相交於同一點，則可將平面分割成c_n個區域。

考慮第n個圓 (或橢圓) O_n與其他圓(或橢圓) O₁, O₂,…, O_n－1相交的情形，因為O_n與O₁, O₂,…, O_n－1共交於2(n－1)個點，故O_n截成2(n－1)個弧，這些弧落在原本前n－1個圓所分割成的c_n－1個區域中的2(n－1)個區域，並將所在的區域一分為二，故c_n比c_n－1多出2(n－1)，即c_n＝c_n－1＋2(n－1)，其中n＞1，邊界條件為c₁＝2。

3.          在空間中有n個相異平面，任四個平面皆可圍成一個四面體(即任兩個平面不平行，任三個平面都會有交點，但任四個平面不共點)，則可將空間分割成d_n個區域。

設第n個平面E_n與前(n－1)個平面相交於(n－1)條直線，且這些直線任取三條，皆可在E_n上圍出三角形，這(n－1)條直線可將E_n分割成b_n－1個部份，這裡的b_n－1滿足b_n－1＝b_n－2＋n－1，其中n＞1，邊界條件為b₁＝2，因此可以算出b_n－1＝(n²－n＋2)∕2。這b_n－1塊落在原本的(n－1)個平面分割出的d_n－1個區域中的b_n－1個區域，且將所在的區域一分為二，故d_n比d_n－1多出2b_n－1，即d_n＝d_n－1＋2b_n－1＝d_n－1＋(n²－n＋2)∕2，其中n＞1，邊界條件為d₁＝2。

4.          一圓上有n個點，由這n個點，可構成x­_n條弦，這x_n條弦最多可以交於y_n個點(即任三條弦在圓內不共點)，最多可將圓切割成z_n個區域。

很容易可以看出，第n個點P_n，可以和其餘的n－1個點連成弦，故弦的個數即等於前n－1個點連出的弦的數量再加上n－1，即x_n＝x_n－1＋n－1，其中n＞1，邊界條件為x₁＝0。

假設圓上的n個點逆時針排列依序為P₁、P₂、…、P_n，則P_n介於P₁和P_n－1之間，考慮P_n與P_k所連成的弦s_k，與其他弦的交點個數：對於i＝1~ k－1，觀察P_i與P_k＋1、P_k＋2、…、P_n－1所連成的n－k－1條弦，都會與弦s_k有一個交點，所以弦s_k上共有(n－k－1)×(k－1)個點(不含端點)，所以從點P_n所拉出的(n－1)條弦上，共有Σ(n－k－1)×(k－1)個點，這裡的Σ為從k＝1到k＝n－1的和。故y_n＝y_n－1+Σ(n－k－1)×(k－1)，這裡的Σ為從k＝1到k＝n－1的和，其中n＞1，且邊界條件為y₁＝0。

因為弦s_k上有(n－k－1)×(k－1)個點，故弦s_k被其他弦截成(n－k－1)×(k－1)＋1個線段，每一個線段都落在前n－1個點連成的弦切割出的z_n－1個區域的(n－k－1)×(k－1)＋1個區域中，並且把這些區域一分為二，這裡的k從1到n－1，故z_n比z_n－1多出Σ[(n－k－1)×(k－1)＋1]，即y_n＝y_n－1+Σ[(n－k－1)×(k－1) ＋1]，這裡的Σ為從k＝1到k＝n－1的和，其中n＞1，且邊界條件為z₁＝1。


還有一些遞迴式的題目在＜利用遞迴式解幾道常見的題目＞這一篇中。