HMMT November, 2017

Solution:

We write everything in base $\phi$. Notice that
$$\frac{\phi^{48 n}-1}{\phi^{48}-1}=10\ldots 010\ldots 01\ldots 10\ldots 01$$
where there are $n-1$ blocks of 47 zeros each. We can prove that every valid base-$\phi$ representation comes from replacing a consecutive string $100$ with a $011$ repeatedly. Using this, we can easily classify what base-$\phi$ representations are counted by $f(n)$.

Notice that $10000000=01100000=01011000=01010110$ and similar, so that in each block of zeros we can choose how many times to perform a replacement. It turns out that we can do anywhere from $0$ to $24$ such replacements, but that if we choose to do $24$ then the next block cannot have chosen $0$ replacements. (An analogy with lower numbers is $10001000=01101000=01100110=01011110$, with the first block "replaced twice," which was only allowed since the second block had "replaced once," opening up the slot which was filled by the last $1$ in the final replacement $011$).

Thus we have a bijection from $f(n)$ to sequences in $\{0, \ldots, 24\}^{n-1}$ such that (a) the sequence does not end in $24$ and (b) the sequence never has a $24$ followed by a $0$.

We let $a_{n}$ denote the number of length-$n$ sequences starting with a $0$, $b_{n}$ for the number of such sequences starting with any of $1$ to $23$, and $c_{n}$ for the number of such sequences starting with $24$. We know $a_{1}=1$, $b_{1}=23$, $c_{0}=0$ and that $f(n)=a_{n-1}+b_{n-1}+c_{n-1}$.

Now,
$$\begin{aligned} a_{n} & =a_{n-1}+b_{n-1}+c_{n-1} \\ b_{n} & =23\left(a_{n-1}+b_{n-1}+c_{n-1}\right) \\ c_{n} & =b_{n-1}+c_{n-1} \end{aligned}$$
so $b_{n}=23 a_{n}$ for all $n$. Substituting gives $a_{n}=24 a_{n-1}+c_{n-1}$, $c_{n}=23 a_{n-1}+c_{n-1}$. Solving for $c_{n}=a_{n+1}-24 a_{n-1}$ and plugging in gives
$$a_{n+1}-24 a_{n}=a_{n}-a_{n-1}$$
which gives a characteristic polynomial of $\lambda^{2}-25 \lambda+1=0$. We easily find that $a_{n}$ grows as $\lambda^{n}$ (where $\lambda$ is the larger solution to the quadratic equation) and thus $b_{n}$, $c_{n}$ do as well, implying that $f(n)$ grows as $\lambda^{n}$, where
$$\lambda=\frac{25+\sqrt{25^{2}-4}}{2}=\frac{25+3 \sqrt{69}}{2}$$
which is our answer.