Sum of Fibonacci numbers at even indexes upto N terms | Python3 Program to find even indexed Fibonacci Sum in O ( Log n ) time . ; Create an array for memoization ; Returns n 'th Fibonacci number using table f[] ; Base cases ; If fib ( n ) is already computed ; Applying above formula [ Note value n & 1 is 1 if n is odd , else 0 ] . ; Computes value of even - indexed Fibonacci Sum ; Driver Code ; Get n ; Find the alternating sum
MAX = 1000 ; NEW_LINE f = [ 0 ] * MAX ; NEW_LINE def fib ( n ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( n == 1 or n == 2 ) : NEW_LINE INDENT f [ n ] = 1 ; NEW_LINE return f [ n ] ; NEW_LINE DEDENT if ( f [ n ] ) : NEW_LINE INDENT return f [ n ] ; NEW_LINE DEDENT k = ( n + 1 ) // 2 if ( n % 2 == 1 ) else n // 2 ; NEW_LINE f [ n ] = ( fib ( k ) * fib ( k ) + fib ( k - 1 ) * fib ( k - 1 ) ) if ( n % 2 == 1 ) else ( 2 * fib ( k - 1 ) + fib ( k ) ) * fib ( k ) ; NEW_LINE return f [ n ] ; NEW_LINE DEDENT def calculateEvenSum ( n ) : NEW_LINE INDENT return ( fib ( 2 * n + 1 ) - 1 ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 8 ; NEW_LINE print ( " Even ▁ indexed ▁ Fibonacci ▁ Sum ▁ upto " , n , " terms : " , calculateEvenSum ( n ) ) ; NEW_LINE DEDENT