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 .