How to solve this nonlinear recurrence relation?

I'm trying to solve the following recurrence relation (all values are real): $$g(n+1) = \frac{a_n + g(n)}{k\cdot g(n)}$$

With:

• $a_n,g(n) > 0$ for all n, and $g(0)$ is arbitrary.
• $k \in \mathbb{N}\setminus\{0,1\} $, (At this moment you can assume that $k=2$ but it'll be interesting to see results with a general $k$).

This comes from my research, which I can't elaborate on at this point.

I don't have much experience with solving these kind of relations. For the past days I've tried reading about generating functions and other techniques but couldn't manage to solve it.

Any help will be much appreciated.

Solution 1:

We can also write your relation as $g(n)=\dfrac1k+\dfrac{a_{n-1}}{kg(n-1)}$. By expanding out the definition of $g(n-1)$ similarly, we see a direct analogy with continued fractions: $$\begin{align} g(n)&=\dfrac1k+\dfrac{a_{n-1}}{kg(n-1)}\\ \\ &= \dfrac1k+\dfrac{a_{n-1}}{1+\dfrac{ka_{n-2}}{g(n-2)}}\\ \\ &= \dfrac1k+\dfrac{a_{n-1}}{1+\dfrac{ka_{n-2}}{1+\dfrac{ka_{n-3}}{g(n-3)}}}\\ \\ &= \ldots \end{align} $$ While canonically 'simple' continued fractions have $1$ as the numerator of every fraction and varying addends, there's been plenty of theory on the more general case that you should be able to apply to your problem. This also suggests that you shouldn't expect a general theory of such sequences without more information on your sequence $a_i$, since many many different functions have continued fraction expansions much like this.

Solution 2:

Following this answer to a similar problem, we can get asymptotics on $g_n$ in terms of $a_n$ provided $a_n$ "does not grow too quickly" in a sense to be made precise soon. If you want to stop reading here, the punchline will be

$$g_n \approx \sqrt{a_n}$$

First, let's tidy up the problem. Write $h_n = k g_n$ and $b_n = k a_n$. We'll solve for the asymptotics of $h_n$ in terms of $b_n$, but obviously this is only a cosmetic difference from your problem.

Now, since $h_n$ and $h_{n+1}$ are similar, we're led to turn our actual recurrence $h_{n+1} = \frac{b_n}{h_n} + 1$ into $h_n^2 \approx h_{n+1} h_n = b_n + h_n$.

In fact, if we write $j_n = \frac{1}{2} + \sqrt{b_n + \frac{1}{4}}$ is the solution of $j_n^2 = b_n + j_n$, then we might expect $h_n \approx j_n$, and this will be true. This is where the above estimate comes from, as (playing fast and loose with constants) $g_n \approx h_n \approx j_n \approx \sqrt{b_n} \approx \sqrt{a_n}$.

Let's make this precise.

Formally, we'll show that

$$j_n \leq h_{n+1} \leq j_{n+1}$$

which is the formal version of the $\approx$ formula I wrote at the top of this answer. By induction, we know:

$$ j_n = 1 + \frac{b_n}{j_n} \overset{IH}{\leq} 1 + \frac{b_n}{h_n} = h_{n+1} $$

and

$$ h_{n+1} = 1 + \frac{b_n}{h_n} \overset{IH}{\leq} 1 + \frac{b_n}{j_{n-1}} \overset{(\star)}{\leq} j_{n+1} $$

So if we can prove the inequality $(\star)$ we'll be done!

This is slightly annoying, but notice $x^2 - x - b_n$ is monotone increasing on $x \geq 1/2$. In particular, as long as everything in sight is $\geq 1/2$ (which is surely satisfied in your special case) we'll know that $x \leq y$ if and only if $x^2 - x - b_n \leq y^2 - y - b_n$.

In particular, to show that

$$1 + \frac{b_n}{j_{n-1}} \leq j_{n+1}$$

we'll show that

$$ \left ( 1 + \frac{b_n}{j_{n-1}} \right )^2 - \left ( 1 + \frac{b_n}{j_{n-1}} \right ) - b_{n+1} \leq j_{n+1}^2 - j_{n+1} - b_{n+1} = 0 $$

But a computation shows that

$$ \begin{aligned} \left ( 1 + \frac{b_n}{j_{n-1}} \right )^2 - \left ( 1 + \frac{b_n}{j_{n-1}} \right ) &= b_n \left ( \frac{j_{n-1} + b_n}{j_{n-1}^2} \right ) \\ &= b_n \left ( \frac{j_{n-1} + b_n}{j_{n-1} + b_{n-1}} \right ) \\ &= b_n \left ( \frac{j_{n-1} + b_{n-1} + (b_n - b_{n-1})}{j_{n-1} + b_{n-1}} \right ) \\ &= b_n + \frac{b_n - b_{n-1}}{j_{n-1} + b_{n-1}} \end{aligned} $$

So we finally come to the "does not grow too quickly" condition. If

$$ \frac{b_n - b_{n-1}}{j_{n-1} + b_{n-1}} \leq b_{n+1} - b_n $$

then this whole sum is $\leq b_{n+1}$, and so we've proven $(\star)$. Of course, we can expand out the definition of $j_{n-1}$ to get this in terms of just the $b_n$s, which I'll do in the next section.

To summarize:

Let $h_n = kg_n$ and $b_n = k a_n$.

If

$$\frac{b_n - b_{n-1}}{\frac{1}{2} + \sqrt{b_{n-1} + \frac{1}{4}} + b_{n-1}} \leq b_{n+1} - b_n$$

then

$$ \frac{1}{2} + \sqrt{b_{n-1} + \frac{1}{4}} \leq h_n \leq \frac{1}{2} + \sqrt{b_n + \frac{1}{4}} $$

I'll leave it to you to cash this out in terms of $g_n$, $a_n$, and $k$.

I hope this helps ^_^