Fibonacci 数列的几个有趣的公式和 O(log(n)) 计算方法

如此定义 Fibonacci 数列：fib(1) = fib(2) = 1，fib(n) = fib(n-1) + fib(n-2)。

公式一：数列和（1~n）

令 S(n) = sum{fib(1), fib(2), ..., fib(n)}，可以证明 S(n) = fib(n+2) - 1。归纳法如下：
(1) 假定，S(n) = fib(n+2) - 1；

(2) 则
  S(n) + fib(n+1)
= fib(n+2) - 1 + fib(n+1)
= (fib(n+2) + fib(n+1)) - 1
= fib(n+3) - 1
= S(n+1)；

(3)
  S(1)
= fib(1+2) - 1
= fib(3) - 1
= 2 - 1
= 1
= fib(1)。
证毕。


公式二：数列和（a~b）
这样的话，计算从 fib(a) 到 fib(b) 的和，可以转换成计算
S(b) - S(a-1) = fib(b+2) - fib(a+1)。


公式三：两倍下标
fib(2*n) 可以由 fib(n) 和 fib(n+1) 求出。初算了一下，似乎有如下公式：
fib(2*n) = fib(n-1) * fib(n) + fib(n) * fib(n+1)
         = (2 * fib(n+1) - fib(n)) * fib(n)

同理可以算出 fib(2*(n+1)) 的值，再减去 fib(2*n)，则可以知道 fib(2*n+1) 的值。
fib(2*n + 1) = fib(n+1)^2 - fib(n)^2

以此，可以从 fib(n)、fib(n+1) 计算出所有的 fib(n*2^k) (k > 0)。
（关于此公式的证明……以后再写，也是很简单的，应该）


O(log(n)) 的时间复杂度求 Fibonacci 数列的某一个元素的方法。
在知道变两倍下标的公式后，我们有两种工具：乘二，加一。这样
我们像可以处理二进制那样来计算 Fibonacci 数列的值。
代码如下：

inline void __fib (int& p, int& q)
{
  q += p;
  p = q - p;
}

int __fib_2n (int f1, int f2, int& f2n1, int& f2n2)
{
  f2n1 = 2 * f1 * f2 - f1 * f1;
  f2n2 = f2 * f2 + f1 * f1;
  return f2n1;
}

int __fib2 (int n, int& f1, int& f2)
{
  if (n <= 0)
    return 0;
  else if (n == 1)
    return f1;
  else
    {
      __fib2 (n / 2, f1, f2);
      __fib_2n (f1, f2, f1, f2);
      if (n % 2 == 1)
        __fib (f1, f2);
    }
  return f1;
}

int fib2 (int n)
{
  int f1 = 1, f2 = 1;
  return __fib2 (n, f1, f2);
}