3
$\begingroup$

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!

  • 6
    I don't know if there's any way to solve this, to be honest.2011-10-23
  • 3
    Why do you think it can be solved with generating functions? And didn't someone else post this problem today or yesterday?2011-10-23
  • 0
    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?2011-10-23
  • 0
    @Thomas: it definitely wasn't "someone else". ;) I tried doing something, but I think I'll let a mod deal with this now...2011-10-23
  • 0
    @Gerry: It begins $5;7;142;60,350;10,926,307,150$, grows obscenely fast, and is not in OEIS.2011-10-23
  • 0
    @Brian: the sequence is 5, 7, 142, 60485, 10975305533, 361371994628101181782, 391769155504477168149440163515824050781039, .. This all does not help much - also this sequence is not in OEIS. It grows very fast, the number of decimal digits is: 1, 1, 3, 5, 11, 21, 42, 84, 168, 337, 673, 1346, ..2011-10-23
  • 0
    @Jiri: You’re right; what did I do? Oh, I see: I inadvertently subtracted $142$ instead of $7$. Thanks.2011-10-23
  • 0
    The title of this questions seems inappropiate to me. This is just a nonlinear difference equation.2011-10-24
  • 0
    Heuristically, I feel that the series should grow like $\exp(\lambda 2^n)$. Can we try to guess the answer and check it using induction?2011-10-24
  • 0
    @SrivatsanNarayanan - i think you shouldn't guess because for different sequence(which the largest power is 2), you will need to "guess" infinite times for differnt sequence2011-10-24
  • 1
    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.2011-10-24

1 Answers 1

2

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