论如何n等分一条线段

· · 算法·理论

众所周知，想要二等分一条线段是比较容易的，只需要做一条中垂线即可，那么三等分、四等分甚至 n 等分，要怎么办呢？我们先从三等分看起。

观察

如图，有一条线段 AB ： 让我们在它的上面随意点上两个点 M 和 N , 就长这样： 那么我们接下来就进行如下操作：

  1. 将点 M 移至 AN 中点；
  2. 将点 N 移至 MB 中点； 重复执行以上操作，我们会发现，点 M 和点 N 竟然在一直靠近线段 AB 的三等分点，下图就是执行 5 次以后的状况：

    猜想

    那么我们于是就生发出猜想：

    是不是只要执行的次数够多 就可以得到更为准确的三等分点

    证明

    条件

    我们不妨假设上面所分的三条线段 AM、MN、NB 的长度分别是 x、y、z。
    我们这时，将一次点的移动看做一次操作，那么在第一次执行完之后的线段长度（刚刚更新的）就是 \frac{x + y}{2}，再执行一次操作后，则为 \frac{\frac{1}{2}{(x + y)} + z}{2}。
    在我们手动枚举五次后得到的结果如下( a_0 表示第一次，以此类推)：

    a_0 = \frac{x+y}{2} a_1 = \frac{\frac{1}{2}{(x + y)} + z}{2} a_2 = \frac{\frac{3}{2}{(x + y)} + z}{2^2} a_3 = \frac{\frac{5}{2}{(x + y)} + 3z}{2^3} a_4 = \frac{\frac{11}{2}{(x + y)} + 5z}{2^4}

    接着，我们发现：

    在 a 的式子中，变了的只有 (x + y) 前的系数、z 的系数和分母。

    那么我们接下来开始严格的证明。

    代数证明

    设 a_n = \frac{\frac{b_n}{2}(x + y) + c_n z}{2^n}，b_1 = 1, b_2 = 3, c_1 = 1, c_2 = 1
    则 a_{n - 1} = \frac{\frac{b_{n - 1}}{2}(x + y) + c_{n - 1} z}{2^n} = \frac{b_{n - 1}(x + y) + 2 c_{n - 1} z}{2^n},
    由此可得：

    a_{n + 1} = \frac{a_n + a_{n - 1}}{2} = \frac{\frac{\frac{b_n}{2}(x + y) + c_n z}{2^n} + \frac{b_{n - 1}(x + y) + 2 c_{n - 1} z}{2^n}}{2} =\frac{\frac{b_n + 2 b_{n-1}}{2}(x + y) + (c_n + 2 c_{n - 1})z}{2^{n + 1}}

    这时，我们发现

    b_n = b_{n - 1} + b_{n - 2} c_n = c_{n - 1} + c_{n - 2}

    又因为 c_2 = b_1, c_3 = b_2，所以， c_n = b_{n - 1}。
    所以原式化为：

    a_n = \frac{\frac{b_n}{2}(x + y) + b_{n - 1} z}{2^n}

    化到这时，我们先求一下 b_n 的通项式：

    b_n = b_{n- 1} + b_{n - 2}

    使用特征根

    x^2 = x + 2

    解得 x = -1 或 x = 2
    则 b_n 通项为 \alpha 2^n + \beta (-1)^n
    带入 b_1 和 b_2 得，