Given the recurrence

$\begin{cases} F_n = 2F_{n-1}^2 H_{n-1} \\H_n = 2F_{n-1} H_{n-1}^2 \end{cases} \text{ for }n\geq 3$

and $F_2 = 1$, $H_2 = 3$.

How can I find an explicit expression for $F_n$?

My approach so far was applying the logarithm, writing it in matrix/vector form an use linear algebra (via eigenvalue/eigenvectors). Then I got the result $$F_n = 3^{\frac{3^{n-2}-1}{2}} + 2^{\frac{3^{n-2}-1}{2}}.$$

Are there easier methods for solving this recurrence relation? I think one should be able to use the symmetry of $F_n$ and $H_n$.

  • $\begingroup$ You could try multiplying and dividing both equations to see what you can get out of the symmetry present. $\endgroup$
    – Yiyuan Lee
    Commented Dec 21, 2015 at 14:47

1 Answer 1


Note that $$ \frac{F_n}{H_n}=\frac{2F_{n-1}^2 H_{n-1}}{2 F_{n-1}H_{n-1}^2}=\frac{F_{n-1}}{H_{n-1}}; $$ i.e., the ratio is constant. So $H_n = 3 F_n$ always. Then the first recurrence becomes $$ F_{n}=2 F_{n-1}^2 H_{n-1} = 6 F_{n-1}^3, $$ and you can proceed with the logarithm / linear recursion approach.

  • $\begingroup$ Oh right, now I feel so stupid not having seen this, thank you very much! $\endgroup$
    – flawr
    Commented Dec 21, 2015 at 14:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .