Quadratic Equation Recurrence?

Question

So I was playing around with the following:

Let $f_0(x) = x^2 - bx + c$.

If $f_n(x)$ has roots $p$ and $q$ with $p > q$, then let $f_{n+1}(x) = x^2 - px + q$.

The recurrence relation is rather simple: if we let $f_n(x) = x^2 - b_nx + c_n$, then $b_{n+1} + c_{n+1} = b_n$ and $b_{n+1}c_{n+1} = c_n$.

I wrote a program to iteratively find these quadratics until the discriminant is less than zero: in the case they do not terminate, the values of $b_n$ and $c_n$ always seem to converge such that $c_n = 0$. However, I couldn't figure out what $b_n$ converges to by inspection. Anyone has any ideas on how this works? I couldn't solve the recurrence relation very easily.

Here is the code: http://ideone.com/42sqow. For example, for $b_0 = 5$ and $c_0 = 1$, $b_n$ and $c_n$ converge to $4.7355610384$ and $0$, respectively.

Answer 1

Here's a start, I may figure some more things out and post here.

Take the two recurrence relations. $$(1) \quad b_{n+1}+c_{n+1}=b_{n}$$ and $$(2) \quad b_{n+1} \cdot c_{n+1}=c_{n}$$

Assume that both $b$ and $c$ converge as the number of iterations tends to infinity. This means that $b_{n+1}=b_{n}$ and $c_{n+1}=c_{n}$. Using this in the system of equations, we get.

$$b+c=b$$ $$\Rightarrow c=0$$ and $$b \cdot c=c$$ $$\Rightarrow b=k$$ Where $k$ is a constant. This is important because it means that I have half of the answer to this problem. $b$ equals something, but we now know that $c=0$ as the number of iterations approaches infinity. Of course, I assume that system of difference equations converges, but I don't think that's too big of an assumption to yield the above analysis invalid.

Perturbation Theory

I doubt this problem has an exact solution, however, given that we know the solution for $c_0=0$ and $b_0=b$ we can perturb $c_0$ to get a better estimate. Firstly, (1) and (2) are equivalent to

$$(3) \quad b_{n+1}={{b_n+\sqrt{{b_n}^2-4 \cdot c_n}} \over 2}$$ and $$(4) \quad c_{n+1}={{b_n-\sqrt{{b_n}^2-4 \cdot c_n}} \over 2}$$

Since we're assuming $c_0$ is small, at least for now, we can take (3) as an approximation for $b_{\infty}$...

For $b_0=5$ $c_0=x$, the graph looks like this...

And for $c_0=1$ we get $b_{\infty} \sim 4.79...$. Not bad for a first approximation. You can keep making better approximations, but the graph displayed above, is very representative of the general behavior. Also, if you expand the above out in series form, and keep iterating, the series should converge to the correct perturbation series. For instance, for the above first iteration, the first two terms for the Taylor expansion are $$b-{c \over b}$$ So these are most likely the first two terms of the perturbation series for the solution.

Let's look at the second convergent for $b_{\infty}$. I've already taken the liberty of simplifying the expression. $$b_{\infty} \sim b_2={{\sqrt{2 \cdot \left((b+4) \cdot \sqrt{b^2-4 \cdot c}+b^2-4 \cdot b-2 \cdot c \right)}+\sqrt{b^2-4 \cdot c}+b} \over 4}$$

As long as b is positive, the perturbation series for $b_{\infty}$ is now approximated by.

$$b_{\infty} \sim b-{c \over b}-{c \over {b^2}}-{{c^2} \over {b^3}}-{{2 \cdot c^2} \over {b^4}}-O(c^3)$$

For $b=5$ and $a=1$ we'll get $4.747... \ $ as an approximation to $b_{\infty}$, that's only about a $0.24$% error. I should also stress that this series expansion for $b_2$ contains terms from $b_1$. Thus, we can intuitively expect the series for $b_n$ to converge to the series for $b_{\infty}$ as n approaches infinity. In addition, most other answers miss the fact that you need a lot series terms to get a good estimate for the recursion. However, I've only used two iterations so far. Sometimes the easiest way to approximate something is just by using what's already given to you.

Answer 2

Last month there was a similar problem, but with time in the opposite direction.
What are the solutions for $a(n)$ and $b(n)$ when $a(n+1)=a(n)b(n)$ and $b(n+1)=a(n)+b(n)$?
EDIT: Boundary of the points that end up complex:
Let $A$ be the region bounded by the curves $(x,y)=(t,t)$ and $(x,y)=(2t,t^2)$. Those points all end up complex in the next iteration.
Let $B$ be the region bounded by the curves $(x,y)=(2t,t^2)$ and $(x,y)=(2t+t^2,2t^3)$. Those points all end up in Region A, and then complex in the following iteration.
Region C is one step back in time again, and ends up complex in three steps. Repeat it to get a region of starting points that end up complex. OP noted that the backward iteration replaces $(x,y)$ with $(x+y,xy)$. If these backward iterations of the line between $(0,0)$ and $(4,4)$ settle down to a curve $y=f(x)$, (and it looks like they do), then $(x,f(x))$ goes to $(x+f(x),xf(x))$, so $f(x+f(x))=xf(x)$.
I observed that the limit curve is $y=0$ for $x\leq a$, and then $f(a+z)\approx Kz^n$ to leading order for small $z>0$, for some $K$ and $n$. Then to leading order, $$f(x+f(x))\approx xf(x)\\ f(a+z+Kz^n)\approx (a+z)(Kz^n)\\ K(z+Kz^n)^n\approx aKz^n+Kz^{n+1}\\ Kz^n(1+Kz^{n-1})^n\approx aKz^n+Kz^{n+1}\\ (1+Kz^{n-1})^n\approx a+z\\ a=1,n=2,K=1/2\\ f(1+z)\approx \frac12z^2$$ So $(p,q)=(1.1,0.005)$ is near the edge. Assuming $f$ has a Taylor series, Maple tells me it is $$f(1+z)\approx\frac{z^2}2-\frac{z^3}{12}+\frac{z^4}{24} -\frac{7z^5}{240} +\frac{103z^6}{4320}...$$
The function $f(x+f(x))=xf(x)$ seems to cut $x=f(x)$ at around $x\approx4.4$, so the procedure gives real answers if $p$ is greater than that.
Other solutions of the equation are $n=1,K=a-1$, for which $$(x,y)\approx(a+t,a+(a-1)t+t^2/(a+1)+...)$$

Answer 3

This is just another approach to the problem, not sure if it gets anywhere.

If the limit of $b_n$ is $f(b,c)$, then we have (in an appropriate range) $$ f(b+c,bc)=f(b,c). $$ Assuming that $c$ is small, it is plausible that this $f$ will be given by a convergent power series in $c$, so (since $f(b,0)=b$) $$ f(b,c) = b + \sum_{k>0} a_k(b)c^k. $$ Then the above functional equation becomes $$ b+c+\sum_{k>0}a_k(b+c)b^kc^k=b+\sum_{k>0}a_k(b)c^k. $$ In particular, assuming various convergences, we get: $$ 1+a_1(b)b=a_1(b) $$ so $a_1(b) = \frac 1{1-b}$. Then looking at the coefficients by $c^2$ one gets, by expanding $a_1(b+c)=\frac 1{1-b-c}$ around $c=0$ (if I am not mistaken): $$\frac b{(1-b)^2} + a_2(b)b^2=a_2(b) $$ and $$ a_2(b)=\frac{b}{(1-b)^2(1-b^2)}. $$ This can be continued, but I don't know if there will be a nice formula for the rational function $a_k(b)$. Perhaps, someone can try a few more steps and search for a pattern.

P.S. The second order approximation for $f(5,1)$ is $$ 5+\frac 1{1-5} + \frac{5}{(1-5)^2(1-5^2)} = 4.736979166\ldots $$ which is reasonably close to the correct value.