two series recurrence relation

Question

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$.

You could try multiplying and dividing both equations to see what you can get out of the symmetry present. — Yiyuan Lee, Dec 21 '15 at 14:47

score 2 · Accepted Answer · answered Dec 21 '15 at 14:44

2

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.

answered Dec 21 '15 at 14:44

mjqxxxx

41,358

Oh right, now I feel so stupid not having seen this, thank you very much! – flawr Dec 21 '15 at 14:46

two series recurrence relation

1 Answers1