问题描述
由于一系列
蛋白原（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-1where 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
这篇关于斐波那契数的乘积之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！