gistfile1.txt

Suppose that:

f(n)*f(n-2) - f(n-1)^2 = (-1)^(n-1)            (1)

This is the same as the assumption, but for n-1. The inductive step requires us to show that it is true for n:

f(n+1)*f(n-1) - f(n)^2 = (-1)^n                (2)
We notice that:

(-1)^n = -1*(-1)^(n-1)                         (3)

so we replace (-1)^(n-1) by the LHS of (1) and we get:

f(n+1)*f(n-1) - f(n)^2 = (-1) * [ f(n) * f(n-2) - f(n-1)^2 ]

and we distribute and rearrange to match terms, to get:

f(n-1) * [ f(n+1) - f(n-1) ] = f(n) [ f(n) - f(n-2) ]

But we know that f(n+1) - f(n-1) = f(n), and f(n) - f(n-2) = f(n-1), so we have:

f(n-1)*f(n) = f(n) * f(n-1)

which is obviously true, and therefore we have demonstrated the inductive step.