See also here.

I'll repost my solution, with a few additional comments: In the version I was given, I wasn't even told part a. It makes everything 20 times easier, but here is my solution. We first note that \[f(f(f(x)))-x=(2x^2-1)(8x^3+8x^2-2x-1)^2\]For purposes currently unknown but not for long, we shall call the polynomial \[g(x)=8x^3+8x^2-2x-1\]the magic cubic. This has three real roots (you can confirm with the Intermediate Value Theorem at $-2,-1,0,$ and $1$), so let them be $r_1<r_2<r_3$. Now, we can note that \[-\frac 98<r_1<r_2<-\frac{135}{512}<r_3<\frac{13}{32}\]so thus we consider the intervals \[\mathcal I_1=\left[-\frac 98,r_1\right]\]\[\mathcal I_2=\left[r_2,-\frac{1}{4}\right]\]\[\mathcal I_3=\left[r_3,\frac{13}{32}\right]\]Now, the magic of this problem is \[f(\mathcal I_k)\subseteq\mathcal I_{k-1}\]with $\mathcal I_k=\mathcal I_{k+3}$. We first note that as \[f^4(r_k)=f(r_k)\]that $\{r_1,r_2,r_3\}=\{r_1,f(r_1),f(f(r_1))\}$. As $r_1<-1$, and $f$ is decreasing on the interval $\left(-\infty,-\frac 98\right)$, we get $f(r_1)>f(-1)>0$. Thus, we get \[f(r_k)=r_{k-1}\]Now, we can note that \[f\left(-\frac 14\right)=-\frac 98\]\[f\left(-\frac 98\right)=\frac{13}{32}\]\[f\left(-\frac{13}{32}\right)=-\frac{135}{512}\]By tedious substitution of the final value into our magic cubic, we see that \[-\frac{135}{512}\in\left[r_2,-\frac 14\right]\]implying the intervals are as we intended. Now how in the world does any of that relate to our problem? We can note that $f(x)$ has two roots, and \[f^2(x)=x(2x+1)(4x^2+2x-3)\]which has 4 real roots. We use symmetry to get $r$ is a root if and only if $-\frac 14-r$ is a root. In particular, as $0\not\in\mathcal I_1\cup\mathcal I_2\cup\mathcal I_3$, we can deduce that exactly half of the roots of $f^n(x)$ are greater than $-\frac{135}{512}$. We shall now induct on the number $n$ to show the number of roots is $2F_n$: Base Case. $n=0,1,2$. This has been shown above. Induction Hypothesis. Assume the result for all $n\leq k$ for some $k$. We show the result for $n=k+1$. Induction Step. By what we talked about above, exactly half, or $F_{k-2}$, of the roots of $f^{k-2}(x)$ are greater than $-\frac{135}{512}$. Thus, exactly $F_{k-2}$ roots of $f^{k-1}(x)$ are greater than $\frac{13}{32}$, as \[f\left(\frac{13}{32}\right)=-\frac{135}{512}\]and since $f(x)$ is increasing and unbounded on $\left(-\frac 14,\infty\right)$. Finally, we can note this implies $F_{k-2}$ roots of $f^k(x)$ are less than $-\frac 98$, as \[f\left(-\frac 98\right)=\frac{13}{32}\]and since $f(x)$ is decreasing and unbounded on $\left(-\infty,-\frac 14\right)$. Now, any such root carries over no more solutions to $f^{k+1}(x)$, as by our above discussion. Thus there are $2F_k-F_{k-2}$ roots that each give 2 solutions (as $-\frac 98$ is not a root), implying that the number of roots is \[2(2F_k-F_{k-2})=2(F_k+F_{k-1})=2F_{k+1}\]completing the proof. This was sort of inspired by two problems. The first of which was from the MAST Diagnostic Quiz of Season 1 and read: Dennis Chen wrote: Let $f(x)=x^2-12x+36$. In terms of $k$, for $k\geq 2$, find the sum of all real $n$ such that $f^k(n)=f^{k-1}(n)$. This problem gives the vibe of "I must try to bound the roots, otherwise I can't do anything", which is a key component to my problem. In this case, however, we're looking at the exact opposite version. The second is the following, from SIME Problem 14: SIME Problem 14 wrote: Let $P(x) = x^3 - 3x^2 + 3$. For how many positive integers $n < 1000$ does there not exist a pair $(a, b)$ of positive integers such that the equation \[ \underbrace{P(P(\dots P}_{a \text{ times}}(x)\dots))=\underbrace{P(P(\dots P}_{b \text{ times}}(x)\dots))\]has exactly $n$ distinct real solutions? This problems is slightly different in nature, but it still was an inspiring point for this problem. It was many people's reactions to when they first saw this problem, and I believe it was because the key idea of this was to once again look at where the roots could be. The idea of finding $f^3(x)=x$ actually came from trying to bound where things could not be. In particular, if we were looking to shave off roots, we would look to shave off $F_{n-2}$ roots to get to $f^{n+1}(x)$. Trying small cases, these seemed to be roots that were greater than -1, and a bit of precision with quadratics yielded greater than $-\frac 98$. To get those, we would need a root greater than $\frac{13}{32}$ in $f^{n-1}(x)$, which meant we had $F_{n-1}$ of those. That in turn meant we had to have $F_{n-2}$ of the roots of the roots of $f^{n-2}(x)$ greater than $-\frac{135}{512}$. This meant that there was no root in between $-\frac{135}{512}$ and $-\frac 14$. This was surprising because: $f^3(x)~x$ at $x=-\frac 14$ There was a really good bound on the roots if the problem was true. I kept trying to make a good interval, but if you tries to shrink the interval $\left(-\frac{135}{512},-\frac 14\right)$, after applying $f^3(x)$, you would get something slightly to the right. You could keep going to the right, but it had to converge when $f^3(x)=x$. That's when I saw the factorization and knew I was on the intended solution, and finished it up.