Generically, to find a polynomial with given values $f(0), f(1), \dots, f(n)$ we need a polynomial of degree $n$. More precisely, such a polynomial of degree at most $n$ can always be found as is shown e.g. by the method of Lagrange Interpolation or the non-vanishing of the corresponding Vandermonde determinant. So the actual question is: In which cases do the Fibonacci Numbers behave "generically" and in which cases are there "unexpected" dependencies? The way to get going here is the following criterion which tells us when given numbers $f(0),\dots,f(n)$ are values of a polynomial $f$ of degree strictly less than $n$: Lemma: Let $f$ be a polynomial of degree strictly less than $d$. Then \[0=\sum_{j=0}^d \binom{d}{j} (-1)^j f(j)=f(0)-\binom{d}{1}f(1)+\binom{d}{2}f(2)-\dots \pm f(d).\](For instance, four numbers $a,b,c,d$ are successive values of a quadratic polynomial iff $a-3b+3c-d=0$.) Proof of Lemma: Well-known, immediate from the theory of finite differences. So we really need to study numbers $m,n$ for which \[\sum_{j=0}^n \binom{n}{j} (-1)^j F_{m+j}=0.\quad (*)\]Whenever this is not satisfied, the smallest possible value of $d$ is just $d=n$. If it is satisfied, the minimal value of $d$ is smaller (and we still need to find out how small). There are two ways to study this identity. One systematic one would be to use the Cauchy-Binet explicit formula for the Fibonacci Numbers and compute the LHS explicitly. This is not hard but not very pleasant either. We choose a different approach and use the recurrence for the Fibonacci sequence to reduce the LHS to a linear combination of $F_m, F_{m+1}$. To do this systematically, we need to express $F_{m+j}$ in terms of $F_m$ and $F_{m+1}$. This is done by the identity $F_{m+j}=F_j \cdot F_{m+1}+F_{j-1} \cdot F_m$ which is easily proved by induction over $j$. Hence the LHS in $(*)$ is equal to \[F_{m+1} \cdot \left(\sum_{j=0}^n \binom{n}{j}(-1)^j F_j\right)+F_m \cdot \left(\sum_{j=0}^n \binom{n}{j}(-1)^j F_{j-1}\right).\]Note that the sums in the brackets do not depend on $m$ anymore. Again, it is not hard to evaluate them and show (e.g. by induction or Cauchy-Binet) that they are equal to $-F_n$ and $F_{n+1}$ respectively. But then the identity $(*)$ amounts to $F_{m+1}F_n=F_mF_{n+1}$ and hence to $m=n$. To summarize we have shown that the value $d=n$ is always possible and a smaller value of $d$ is possible if and only if $m=n$. But then a quick thought reveals that only $d=n-1$ is possible since otherwise we could apply the same argument with a smaller value of $n$. So the final answer is $d=n$ for $m \ne n$ and $d=n-1$ if $m=n$.