Find the sum of Fibonacci Series

Question

I have given a Set A I have to find the sum of Fibonacci Sum of All the Subsets of A.

Fibonacci(X) - Is the Xth Element of 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 there any way I can find the sum without generating the subset?

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

Answer 1

There surely is.

First, let's recall that the nth Fibonacci number equals

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

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

Next, let's notice that a sum of Fibonacci numbers is a sum of powers of A and B:

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

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

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

But hey, there's a simpler expression for this:

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

Now, it is time to get the whole result.

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

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 as there's no relation between n_i. However, there could be some room for computative optimization of this expression. In fact, I'm not sure at all if this (using real numbers) will work faster than the "straightforward" summing, but the question was about avoiding subsets generation, so here's the answer.

Answer 2

I tested the answer from YakovL using Python 2.7. It works very well and is plenty quick. I cannot imagine that summing the sequence values would be quicker. 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]