Find the Fibonacci Series Sum

Question

I gave a Set A I need to find the sum of the Fibonacci sum of all subsets of A.

Fibonacci(X) - Is the Xth element of the Fibonacci series
For example, for A = {1,2,3} :

Fibonacci (1) + Fibonacci (2) + Fibonacci (3) + Fibonacci (1 + 2) + Fibonacci (2 + 3) + Fibonacci (1 + 3) + Fibonacci (1 + 2 + 3) 1 + 1 + 2 + 2 + 5 + 3 + 8 = 22

Is it possible to find the sum without generating a subset?

Since I find Sum of all subsets easily i.e. Sum of All Subset - (1+2+3)*(pow(2,length of set-1))

Answer 1

Of course have.

First, recall that the nth Fibonacci number is

φ (n) = [φ ^ n - (-φ) ^ (- n)] / √5

where φ = (√5 + 1) / 2 (Golden Ratio) and (-φ) ^ (- 1) = (1-√5) / 2. But to make it shorter, we denote φ as A and (-φ) ^ (- 1) as B.

Further, note that the sum of the Fibonacci numbers is the sum of the degrees A and B:

[φ (n) + φ (m)] * √5 = A ^ n + A ^ m - B ^ n - B ^ m

Now what is enough to calculate (in the example {1,2,3} ),

A ^ 1 + A ^ 2 + A ^ 3 + A ^ {1 + 2} + A ^ {1 + 3} + A ^ {2 + 3} + A ^ {1 + 2 + 3}.

But there is a simpler expression for this:

(A ^ 1 + 1) (A ^ 2 + 1) (A ^ 3 + 1) - 1

Now it's time to get the whole result.

Let our set {n1, n2, ..., nk} . Then our amount will be equal

Sum = 1/√5 * [(A^n1 + 1)(A^n2 + 1)...(A^nk + 1) - (B^n1 + 1)(B^n2 + 1)...(B^nk + 1)]

I think mathematically, this is the “simplest” form of the answer, since there is no connection between n_i. However, there may be room for computational optimization of this expression. In fact, I'm not sure if this (using real numbers) will work faster than the “simple” summation, but the question was to avoid generating subsets, so here is the answer.

Answer 2

I checked the answer from YakovL using Python 2.7. It works very well and very fast. I cannot imagine that summing sequence values ​​would be faster. Here's the implementation.

 _phi = (5.**0.5 + 1.)/2. A = lambda n: _phi**n B = lambda n: (-_phi)**(-n) prod = lambda it: reduce(lambda x, y: x*y, it) subset_sum = lambda s: (prod(A(n)+1 for n in s) - prod(B(n)+1 for n in s))/5**0.5 

And here are some test results:

 print subset_sum({1, 2, 3}) # 22.0 # [Finished in 0.1s] print subset_sum({1, 2, 4, 8, 16, 32, 64, 128, 256, 512}) # 7.29199318438e+213 # [Finished in 0.1s]