How do i compute $f_n = 3f_{n-1} + 2\sqrt{2f_{n-1}^2 - 2}$ for $n$ around $10^{18}$?

Question

So I have the recurrence $$f_n = \begin{cases} 3f_{n-1} + 2\sqrt{2f_{n-1}^2 - 2}, &n > 1\\ 3, &n = 1\\ \end{cases}$$ and I need to compute it in $O(\lg n)$, for $n$ as big as $10^{18}$. I tried to reduce it to a closed form equation but I don't see how that could be achieved.

Answer 1

This should help:

Let $x=f_{n+1}$, $y=f_n$ and $z=f_{n-1}$, then we have after squareing $$x^2-6xy+y^2=-8$$ and $$y^2-6yz+z^2 =-8$$ If we substract these two we get $$(x-z)(x-6y+z)=0$$ Since clearly these sequance is increasing, we can't have $x=z$, so $$x =6y-z$$ or $$f_{n+1}=6f_n-f_{n-1}$$

Answer 2

For an integer $n\geq 1$, let $a_n$ and $b_n$ be integers such that $(3+2\sqrt{2})^n=a_n+b_n\sqrt{2}$. Prove by induction that $f_n=a_n$ for every $n=1,2,3,\ldots$. This shows that $$f_n=\frac{(3+2\sqrt{2})^n+(3-2\sqrt{2})^n}{2}=\left\lceil\frac{(3+2\sqrt{2})^n}{2}\right\rceil$$ for all integers $n\geq 1$. Taking $n$-th powers can be computed with time complexity $\mathcal{O}\big(\log_2(n)\big)$.

Answer 3

In the programming contest this is apparently taken from, you may want to use (long long) integer arithmetic only to compute $f_n$. This will come in handy:

Suppose we know $f_{n+1}=af_n+bf_{n-1}$ for all $n$. Then $$ \begin{pmatrix}f_{n+1}\\f_n\end{pmatrix}=\begin{pmatrix}a&b\\1&0\end{pmatrix}\begin{pmatrix}f_{n}\\f_{n-1}\end{pmatrix}$$ and consequently by induction $$ \begin{pmatrix}f_{n+1}\\f_n\end{pmatrix}=\begin{pmatrix}a&b\\1&0\end{pmatrix}^n\begin{pmatrix}f_{1}\\f_{0}\end{pmatrix}.$$ Then recall that computing $n$th powers can be done in $O(\log n)$ by square-and-multiply. Also, if you know that $f_n$ fits into your favourite integer type on a two's complement machine, you need not worry about any overflows in the computations above.