2

Is there an exact solution (or can we get bounds on) the recurrence $$x_{n+1}=\frac{C x_n}{1-x_n},$$ where $C\in(0,1)$ and $x_0\in[0,1-C)$?

I can quickly show that the solution degreases to $0$ as $n\rightarrow \infty$, but the best I can do it's to bound $x_{n+1}\geq C x_n \geq ... \geq C^{n}x_0$ and $x_{n+1}\leq \frac{C}{1-x_0}x_n\leq \left(\frac{C}{1-x_0}\right)^nx_0$, but I don't know a whole lot about difference equations and better bounds or an exact solution would be useful for a problem i'm working on

Niebla
  • 444
  • 2
    Yes, we can find an exact solution. The RHS is a fractional linear transformation / Mobius transformation and composition of these things works the same way as matrix multiplication; the exact solution is in terms of the eigenvalues of the matrix $\left[ \begin{array}{cc} C & 0 \ 1 & -1 \end{array} \right]$. – Qiaochu Yuan Sep 12 '22 at 19:10

1 Answers1

1

If $x_0 = 0$, then $x_n = 0$ for every $n$. So let's suppose that $x_0 \neq 0$, in which case $x_n \neq 0$ for every $n$.

Then let $y_n = \dfrac{1}{x_n}$. The equation rewrites as $$y_{n+1} = \dfrac{1}{C}(y_n-1)$$

For $z_n = y_n - \dfrac{1}{1-C}$, you get that $$z_{n+1} = y_{n+1} -\dfrac{1}{1-C} = \dfrac{1}{C}(y_n-1) - \dfrac{1}{1-C}= \dfrac{1}{C}\left(z_n + \dfrac{C}{1-C}\right) - \dfrac{1}{1-C} = \dfrac{1}{C}z_n$$

which leads to $z_n = \dfrac{z_0}{C^n}$ for every $n \geq 0$, and then to $$y_n = \dfrac{y_0 - \frac{1}{1-C}}{C^n} + \dfrac{1}{1-C} = \dfrac{y_0(1-C)+C^n-1}{C^n(1-C)}$$

and finally to $$\boxed{x_n = \dfrac{x_0C^n(1-C)}{(1-C)+x_0(C^n-1)}}$$

TheSilverDoe
  • 29,720
  • Of course, that can be cancelled to $\frac{x_0C^n}{1-x_0\sum_{k=0}^{n-1}C^k}$, according to individual preference. – J.G. Sep 12 '22 at 20:30