3
$\begingroup$

I have been reading on recurrence relations and I have seen that some of them are really easy to solve, for example: $$a_{n+1}=a_n^2$$ Starting from $n=0$ and substituting yields a pattern that is simple enough to take advantage of, after a proof by induction we get $a_n=a_0^{2^n}$. I have some problems with this method because, even though it provides an answer, this answer springs from pattern recognition and nothing else, we know nothing more about the relation or whether other solutions exist, but at least we know one solution.
The problem comes when, three strokes later, we get this: $$a_{n+1}=a_n^2+1$$ A single one makes the problem much harder. However, I still tried to solve it and after fruitlessly attacking it with matrices, integrals, derivatives, polynomial expansions and more pattern recognition, I tried a new method:
We set $a_n=f(n)$ such that $f(n)^2+1=f(n+1)$. To find an expression for $f(n)$ we note that $a_{n+1}-a_n^2=1$.
Assume we have a solution $(a_1,a_0)$, then $$(\sqrt{a_1}+a_0)^{g(n)}(\sqrt{a_1}-a_0)^{g(n)}=1^{g(n)}=(\sqrt{a_{n+1}}+a_n)(\sqrt{a_{n+1}}-a_n)$$

Equating coefficients and solving the system of two equations in two unknowns yields $$a_{n+1}=\frac 14 ((\sqrt{a_{1}}+a_0)^N+(\sqrt{a_{1}}-a_0)^N)^2$$ $$a_{n}=\frac 12 ((\sqrt{a_{1}}+a_0)^N-(\sqrt{a_{1}}-a_0)^N)$$ Where $N=g(n)$. We can check that these expressions satisfy the original equation but I do not know how to proceed from here. I noticed, however, that if we define $h(N)$ to be equal to the square root of the expression for $a_{n+1}$ we have $h(N)^2=\frac {h(2N)+1}{2}$. If we use the ansatz $g(n)=2^n$ then $2h(n)^2-1=h(n+1)$ which is extremely close to the function I was searching for. Furthermore, we can set $$f(n)=A(\sqrt{a_{1}}+a_0)^{2^n}+A(\sqrt{a_{1}}-a_0)^{2^n}$$ Which gives $f(n)^2-2A^2=Af(n+1)$. In some way, the above approach solved an equation similar to the one I wanted to solve. My question is twofold: "Why did I end up solving a different yet similar equation?" And "Although this approach has many holes here and there (e.g. Justifying the replacement of $1/2$ with $A$, finding $g(n)$ without using an ansatz, adjusting the values of $a_1, a_0$ for different recurrence relations, etc.) is it still a promising approach?"

Improve this question
$\endgroup$
  • 1
    $\begingroup$ One way to solve recurrence relations of this type is to use generating functions: en.wikipedia.org/wiki/Generating_function. $\endgroup$ – Mosquite Jul 28 '16 at 16:00
  • $\begingroup$ @Mosquite I tried using them but I was unable to get a closed form, could you give me a hint? $\endgroup$ – Guacho Perez Jul 28 '16 at 16:14
  • $\begingroup$ Recurrences with $a_n^2$ produce the derivative of a generating function. So will will end up with a differential equation. $\endgroup$ – Mosquite Jul 28 '16 at 16:40
3
$\begingroup$

Nonlinear recurrence relations are hard. There are very few cases where you can have a closed-form solution. In particular, quadratic recurrences have closed-form solutions only in a few cases.

This deserves to be put in a somewhat wider context. There are, up to conjugacy by linear functions, two sequences $P_n$ of polynomials of degree $n$ forming semigroups under composition (i.e. $P_{mn}(x) = P_m(P_n(x))$): the monomials $M_n(x) = x^n$ and the Chebyshev polynomials $T_n(x) = \cos(n \arccos(x))$. See e.g. this sci.math posting from 2001 for a proof. Each of these correspond to recurrences with closed-form solutions: $a_n = P_{k^n}(x)$ satisfies $a_{n+1} = P_k(a_n)$. In particular, for $k=2$ we get $a_n = x^{2^n}$ with $a_{n+1} = a_n^2$ corresponding to the monomials and $a_n = T_{2^n}(x)$ with $a_{n+1} = T_2(a_n) = 2 a_n^2 - 1$ corresponding to the Chebyshev polynomials. Conjugating this one with multiplication by a constant gives you $a_n = c T_{2^n}(x/c)$ for $a_{n+1} = 2 a_n^2/c - c$, which is the equation you ended up solving for $c = 2A$.

Improve this answer
$\endgroup$
  • $\begingroup$ Does this mean only quadratic recurrence relations of the form $ca_{n+1}=a_n^2-2c^2$ can be solved? $\endgroup$ – Guacho Perez Jul 28 '16 at 20:06
  • 1
    $\begingroup$ No. As far as I know, there might be solutions involving some completely different functions. $\endgroup$ – Robert Israel Jul 28 '16 at 22:14
2
$\begingroup$

The only other one of type $x^2 + C$ that has a closed form solution is $$ x_{n+1} = x_n^2 - 2 $$ where $x_0 > 2.$ Take real constants so $A+B = x_0$ and $AB=1,$ then $$ x_n = A^{\left( 2^n \right)} + B^{\left( 2^n \right)} $$ Worth checking yourself. Not sure what happens if $0 < x_0 < 2$

For other $x_{n+1} = x_n^2 + C$ you can still prove an approximation $x_n \approx H^{\left( 2^n \right)},$ however, I recall that you cannot get an explicit value for the constant $H,$ only estimates from calculating large $x_n.$ Meaning, of course, the you are just estimating $$ \frac{\log x_n}{2^n}$$ and calling that $\log H.$

Improve this answer
$\endgroup$
  • $\begingroup$ How did you arrive at the closed form? I would like to see your method so that I can compare it with mine. Is there something wrong with my approach or is there somewhere where it can be improved? $\endgroup$ – Guacho Perez Jul 28 '16 at 21:36
2
$\begingroup$

According to this paper (which I haven't read), for any recurrence relation of a general form including yours, there is some constant $k$ such that for all sufficiently large $n,$ $a_n$ is the nearest integer to $k^{2^n}.$

A. V. Aho and N. J. A. Sloane, "Some Doubly Exponential Sequences", http://www.fq.math.ca/Scanned/11-4/aho-a.pdf

Improve this answer
$\endgroup$
  • $\begingroup$ Nice reference. Especially since it's Sloane $\endgroup$ – Yuriy S Jul 28 '16 at 17:47
  • $\begingroup$ Yes, but you cannot find $k$ explicitly, you can only estimate it. $\endgroup$ – Will Jagy Jul 28 '16 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.