Theorem: Let F(n) be the sequence defined by the recurrence
F(n) = F(n - 1) + F(n - 2)
subject to the initial conditions
F(0) = 0, F(1) = 1
Let G(n) be the sequence that is its Binomial Transform
In other words, the sequence defined by
n
-----
\
G(n) = ) binomial(n, i) F(i)
/
-----
i = 0
then G(n) satisfies the recurrence
G(n) = 3 G(n - 1) - G(n - 2)
subject to the initial conditions
G(0) = 0, G(1) = 1
This took, 0.060, seconds .