I wonder what the interviewer would have said if you'd written down Binet's formula :)
http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
Like really I don't know what to expect. I wonder what % of programmers can actually solve the problem without studying the solution (I'm sure there are many out there but I would guess most are from a mathematical field/background).