I have given a Set A i have to find the sum of Fibonacci Sum of All the Subset of A
Fibonacci(X) – Is the Xth Element of Fibonacci Series
For EX 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+5+3+8=20
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))
Best Answer
You can use the formula for Fibonacci numbers: $$ F_n = \frac{\phi^n - \hat\phi^n}{\sqrt{5}} $$ where $\phi = (1 + \sqrt 5)/2,\hat\phi = (1 - \sqrt 5)/2$ are roots of the equation $x^2 = x + 1$.
To calculate $F_1 + F_2 + F_3$, $$F_1 + F_2 + F_3 = \frac{\phi - \hat\phi}{\sqrt{5}} + \frac{\phi^2 - \hat\phi^2}{\sqrt{5}} + \frac{\phi^3 - \hat\phi^3}{\sqrt{5}} $$