斐波那契数的乘积之和

本文介绍了斐波那契数的乘积之和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

由于一系列

蛋白原（1）*蛋白原第（n + 2）+蛋白原（2）*蛋白原第（n + 1）+蛋白原（3）*蛋白原（正）+ ...... +蛋白原（N-1） *蛋白原（4）

Fib(1) * Fib (n+2) + Fib(2) * Fib(n+1) + Fib(3) * Fib(n) + ...... + Fib(n-1) * Fib(4)

或求和纤维蛋白原（X）*纤维蛋白原（N-X + 3）其中x为从1到n-1 其中，纤维蛋白原（n）是斐波那契数列的第n个号

or Summation Fib(x) * Fib (n-x+3) where x varies from 1 to n-1 where Fib(n) is nth number of Fibonacci series

要评估这一系列纤维蛋白原（N）可以用矩阵幂计算。

to evaluate this series Fib(n) can be calculated using matrix exponentiation .

但是，对于这种复杂性是LOGN和的n而言这将是nlogn

But the complexity for this is logn and for the n terms it would be nlogn .

我想这个系列得到简化为单一期限或其他一些优化，以提高 *的的时间复杂度。的*

任何建议？

推荐答案

我不能减少的总和到单一术语，但它可以降低到一个总和五个方面，从而降低了复杂性，以 O（log n）的算术运算。

I can't reduce the sum to a single term, but it can be reduced to a sum of five terms, which reduces the complexity to O(log n) arithmetic operations.

不过，纤维蛋白原（N）的Θ（N）位，因此位运算的数量不是对数。有一些的大小蛋白原（N）乘法与 N-1 ，所以比特的数量-operations是 M（N，日志N），其中 M（A，B）是位操作的复杂性的乘法的比特数与 B 比特数。对于天真的算法， M（A，B）= A * B ，所以位操作都必须在下面的算法数量为O（n * log n）的。

However, Fib(n) has Θ(n) bits, so the number of bit-operations is not logarithmic. There is a multiplication of a number the size of Fib(n) with n-1, so the number of bit-operations is M(n,log n), where M(a,b) is the bit-operation complexity of a multiplication of an a-bit number with a b-bit number. For the naive algorithm, M(a,b) = a*b, so the number of bit-operations in the below algorithm is O(n*log n).

这允许这种减小的事实是，斐波纳契数（如在由一个线性递推限定的序列的所有数值）可以写为纯指数项的和，特别是

The fact that allows this reduction is that Fibonacci numbers (like all numbers in a sequence defined by a linear recurrence) can be written as the sum of pure exponential terms, in particular

Fib(n) = (α^n - β^n) / (α - β)

其中

α = (1 + √5)/2; β = (1 - √5)/2.

在除斐波那契数，我也用了Lucas数，它遵循相同的复发的斐波那契数，

In addition to the Fibonacci numbers, I also use the Lucas numbers, which follow the same recurrence as the Fibonacci numbers,

Luc(n) = α^n + β^n

所以卢卡斯数列（从索引0开始）以

so the sequence of Lucas numbers (starting from index 0) begins with

2 1 3 4 7 11 18 29 47 ...

关系吕克（N）=纤维蛋白原（N + 1）+纤维蛋白原（N-1）允许Fibonacci - Lucas数之间的简单转换，并计算吕克（N）在 O（log n）的步骤可重复使用的斐波那契code。

The relation Luc(n) = Fib(n+1) + Fib(n-1) allows an easy conversion between Fibonacci and Lucas numbers, and computation of Luc(n) in O(log n) steps can reuse the Fibonacci code.

因此​​，与斐波那契数的再presentation上面给出，我们发现

So with the representation of Fibonacci numbers given above, we find

(α - β)^2 * Fib(k) * Fib(n+3-k) = (α^k - β^k) * (α^(n+3-k) - β^(n+3-k)) = α^(n+3) + β^(n+3) - (α^k * β^(n+3-k)) - (α^(n+3-k) * β^k) = Luc(n+3) - ((-1)^k * α^(2k) * β^(n+3)) - ((-1)^k * α^(n+3) * β^(2k))

使用关系α*β= -1 。

现在，因为α - β=√5的总和 K = 1，...，N-1 收益率

Now, since α - β = √5 the summation k = 1, ..., n-1 yields

n-1 n-1 n-1 5 * ∑ Fib(k)*Fib(n+3-k) = (n-1)*Luc(n+3) - β^(n+3) * ∑ (-α²)^k - α^(n+3) * ∑ (-β²)^k k=1 k=1 k=1

几何款项可以写成封闭形式，有点杂耍得到式

The geometric sums can be written in closed form, and a bit of juggling yields the formula

n-1 ∑ Fib(k)*Fib(n+3-k) = [5*(n-1)*Luc(n+3) + Luc(n+2) + 2*Luc(n+1) - 2*Luc(n-3) + Luc(n-4)]/25 k=1