# Non-linear recurrence problem

How to convert $p_n$ to an expression in terms of $n$ if $3p_{n-1}^2 - p_{n-2}=p_{n}$ and $p_0=5, p_1=7$?

This is a problem I haven't been able to finish for two days, please help. This question haven't answered for a day, please help!

-
I don't know if there's any way to solve this, to be honest. –  anon Oct 23 '11 at 4:04
Why do you think it can be solved with generating functions? And didn't someone else post this problem today or yesterday? –  Thomas Andrews Oct 23 '11 at 4:37
Have you tried calculating the first few terms and seeing if there's any pattern? or seeing if those terms are in the Online Encyclopedia of Integer Sequences? –  Gerry Myerson Oct 23 '11 at 5:27
@Thomas: it definitely wasn't "someone else". ;) I tried doing something, but I think I'll let a mod deal with this now... –  J. M. is back. Oct 23 '11 at 5:40
If I start your series with $1,3$ it is not far off $3^{(2^n-1)}$. It is only a factor $100$ smaller at $n=9$ out of $10^{243}$. I got that by ignoring the $-p_{n-2}$ part. –  Ross Millikan Oct 24 '11 at 21:17

## 1 Answer

As said by others, there is no closed form expression of $p_n$ for general $n$. Nevertheless, one can show that, for any $1\leqslant k\leqslant n$, $$(3p_k-1)^{2^{n-k}}\leqslant3p_n\leqslant(3p_k)^{2^{n-k}}.$$ This already indicates roughly the growth rate of $(p_n)_n$, for example in the sense that the sequence $(q_n)_n$ defined by $q_n=2^{-n}\log p_n$ is positive and bounded. But one can have more.

To wit, $2^n(q_n-q_{n-1})\to\log3$ hence $(q_n)_n$ is ultimately increasing and converges to a finite positive limit $q$. The value of $q$ might depend on the first values of $(p_n)$ but this, and other similar elementary computations, yields the existence, for every large enough positive $p_0$ and $p_1$ ($p_0\geqslant2$ and $p_1\geqslant2$ is enough), of a finite $\color{red}{\alpha(p_0,p_1)>1}$ whose value might depend on $p_0$ and $p_1$, such that, when $n\to\infty$, $$\color{red}{p_n=3\cdot\alpha(p_0,p_1)^{2^n}\cdot(1+o(1))}.$$

-