A simple test for whether some integer N is a Fibonacci number is as follows:
N is a Fibonacci number iff either (5 * n^2 + 4) or (5 * n^2 - 4) is a square number.
See here for the ingenious proof (page 417): http://www.fq.math.ca/Scanned/10-4/advanced10-4.pdf
If it turns out that N is not a Fibonacci number, then the simplest method is just to keep trying with smaller numbers until you find one, although this could take a very long time for large N.
solved Determine whether N is fibonacci or not, if not find the largest fibonacci number smaller than N