You certainly can prove it by induction, but it is more easily proved by solving the difference equation:

E^{2}f_{n} - Ef_{n} - f_{n} = 0 using appropriate initial conditions.

The general solution is immediate:

f_{n} = A P^{n} + B Q^{n} where P=[1+√5)/2 and Q=[1-√5)]/2.