Recursionhard
0:00.0

The Fibonacci numbers satisfy Fn=ϕnψn5F_n = \frac{\phi^n - \psi^n}{\sqrt{5}} where ϕ=1+52\phi = \frac{1+\sqrt{5}}{2} and ψ=152\psi = \frac{1-\sqrt{5}}{2}. A related sequence GnG_n satisfies the same recurrence Gn=Gn1+Gn2G_n = G_{n-1} + G_{n-2} but with initial conditions G0=1,G1=1G_0 = 1, G_1 = 1. Compute G5G_5.