Optimization of parameter for recursive Cauchy sequence

Question

I have the following recursive sequence I'm analyzing:

$$V_0 = 50, V_1 = (1-10k)V_0,$$

$$V_{n+1} = (1-10k)V_n - 5kV_{n-1}$$

where $k > 0$ is a parameter that I'm investigating by running simulations in R.

(This is from the "docking problem" in Meerschaert's "Mathematical Modeling").

$\langle V \rangle$ isn't Cauchy for all $k$. The sequence seems to diverge if $k > 0.18$ or so.

My analysis is to examine how fast the sequence converges as $k$ varies. I did this by simulating the sequence and picking the first $n$ for which $|V_n| < 0.1$

Here's a plot of said $n$ as a function of $k$. The horizontal axis are various $k$'s, and the vertical axis is the first $n$ for which $|V_n| < 0.1$ with that $k$ as the parameter.

My question is: What is this function? Why does it behave the way it does?

How do I find local minima of this function other than by simulation?

And what is the exact $k$ at which the sequence $\langle V \rangle$ stops being Cauchy?

Answer 1

It seems the following.

In despite of your graphs suggest detrministic chaotic behavior, like the sequence generated by the logistic map, but this is not the case, because it is a usual second order recurrence, so your graphs show an effect of the computational approach.

It is clear that the sequence $\{V_n\}$ is uniquely determined by the recurrent formulas and the initial conditions. Consider the characteristic polynomial $$p(\lambda)=\lambda^2+(10k-1)\lambda+5k$$ of the recurrence. It has discriminant

$D=100k^2-40k+1$ (with roots $k=\frac{2\pm \sqrt{3}}{10}$)

and roots

$\lambda_1=\frac{1-10k+\sqrt{D}}2$ and $\lambda_2=\frac{1-10k-\sqrt{D}}2$.

If $D\ne 0$ then $\lambda_1\ne\lambda_2$, so we should search the formula for a sequence $\{V_n\}$ in the form

$$V_n=C_1\lambda_1^n+ C_2\lambda_2^n,$$

where $C_i$ are (complex) constants. The set of the solutions of the recurrence is a two-dimensional linear space, with the basis consisting of the geometric progressions $\{\lambda_1^n\}$, $\{\lambda_2^n\}$. So we search the sequence $\{V_n\}$ as a linear combination of the basis sequences in order to satisfy the initial conditions:

$\cases{V_0=C_1\lambda_1^0+ C_2\lambda_2^0=C_1+C_2\\ (1-10k)V_0=V_1=C_1\lambda_1^1+ C_2\lambda_2^1= C_1\lambda_1+ C_2\lambda_2}$.

This system has a unique solution $C_1=\frac{V_0\lambda_1}{\sqrt{D}}$ and $C_2=\frac{-V_0\lambda_2}{\sqrt{D}}$. So

$$V_n=V_0\frac{\lambda_1^{n+1}-\lambda_2^{n+1}}{\sqrt{D}}.$$

Now we examine the convergence of the sequence $\{V_n\}$ and we even drop the restriction $k>0$.

If $D>0$ (that is if $k<\frac{2-\sqrt{3}}{10}\approx 0.03$ or $k>\frac{2+\sqrt{3}}{10}\approx 0.37$) then both roots $\lambda_i$ are real and different. So the sequence $\{V_n\}$ converges iff

both $-1<\lambda_1, \lambda_2\le 1$ iff

$-2<1-10k-\sqrt{D}<1-10k+\sqrt{D}\le 2$ iff

$\sqrt{D}<1+10k$ and $\sqrt{D}\le 3-10k$ iff

$100k^2-40k+1<(1+10k)^2$ and $k<0.3$ and $100k^2-40k+1\le (3-10k)^2$ iff

$k>0$ and $k<0.3$ and $k\le 0.4$ iff

$0<k<0.3$.

Since $0.3<\frac{2+\sqrt{3}}{10}\approx 0.37$, the sequence $\{V_n\}$ converges iff $0<k<\frac{2-\sqrt{3}}{10}\approx 0.03$.

If $D<0$ (that is if $0.03\approx\frac{2-\sqrt{3}}{10}<k<\frac{2+\sqrt{3}}{10}\approx 0.37$) then both roots $\lambda_i$ are not real. Since $\lambda_2=\overline{\lambda_1}$, then

$$V_n=C\operatorname {Im} \lambda_1^{n+1},$$ where $C$ is a constant which does not depend on $n$. So the sequence $\{V_n\}$ diverges if $|\lambda_1|\ge 1$ and converges if $|\lambda_1|<1$. Since $|\lambda_1|=|\lambda_2|$ and $|\lambda_1\lambda_2|=|5k|=5k$, the sequence $\{V_n\}$ diverges iff $0.2=\frac 15 \le k<\frac{2+ \sqrt{13}}{20}\approx 0.28$ and converges iff $0.03\approx\frac{2-\sqrt{3}}{10}<k<\frac 15=0.2$.

If $D=0$ (that is if $k=\frac{2\pm \sqrt{3}}{10}$) then $\lambda_1=\lambda_2=\lambda=\frac{1-10k}2\ne 0$, so we should search the formula for a sequence $\{V_n\}$ in the form

$$V_n=C_1\lambda^n+ C_2n\lambda^n,$$

where $C_i$ are (complex) constants. The set of the solutions of the recurrence is a two-dimensional linear space, with the basis consisting of the sequences $\{\lambda^n\}$, $\{n\lambda^n\}$. So we search the sequence $\{V_n\}$ as a linear combination of the basis sequences in order to satisfy the initial conditions:

$\cases{V_0=C_1\lambda^0+ C_2\cdot 0\cdot \lambda^0=C_1\\ (1-10k)V_0=V_1=C_1\lambda^1+ C_2\cdot 1\cdot \lambda^1= C_1\lambda+ C_2\lambda}$.

This system has a unique solution $C_1=C_2=\frac{V_0}2$. So

$$V_n= \frac{V_0(1+n)\lambda^n}2.$$

Equality $D=0$ implies $\lambda=\frac{-1\mp\sqrt{3}}2$. If $\lambda=\frac{-1+\sqrt{3}}2$, then $|\lambda|<1$ and the sequence $\{V_n\}$ converges to the zero. If $\lambda=\frac{-1-\sqrt{3}}2$, then $|\lambda|>1$ and the sequence $\{V_n\}$ diverges.

Final answer: The sequence $\{V_n\}$ converges iff $0<k<\frac 15=0.2$

Added. Yes, I can investigate this situation more precisely. So, it seems the following.

I recall that if the sequence polynomial has two different (real) roots $\lambda_1$ and $\lambda_2$ that is if $D>0$ that is if $k<\frac{2-\sqrt{3}}{10}\approx 0.03$ or $k>\frac{2+\sqrt{3}}{10}\approx 0.37$ then

$$V_n=V_0\frac{\lambda_1^{n+1}-\lambda_2^{n+1}}{\sqrt{D}}.$$

As we showed, the sequence $\{V_n\}$ converges iff $0<k<\frac{2-\sqrt{3}}{10}\approx 0.03$. In the latter case we have the following.

Since $0<\lambda_1\lambda_2=5k<1$, we have that both roots have the same sign. So

$\lambda=\lambda_1=\frac{1-10k+\sqrt{D}}2$ and $\mu=\lambda_2\frac{1-10k-\sqrt{D}}2$. Since $10k<1$, we have $1>\lambda>\mu>0$.

So $\{V_n\}$ is a sequence of positive numbers and it is a difference of two geometric progressions with positive quotients. Empirical evidence suggests that the sequence $\{V_n\}$ monotonically and quickly decreases. See, for instance the following graph for $k=0.01$:

To prove the monotony of the sequence $\{V_n\}$ we differentiate $V_n$ with respect to $n$:

$$\frac{\partial{V}}{\partial{n}}=\frac{V_0}{\sqrt{D}}\left(\lambda^n\ln\lambda-\mu^n\ln\mu\right).$$

So $\frac{\partial{V}}{\partial{n}}<0$ iff $\lambda^n\ln\lambda<\mu^n\ln\mu$ iff $\left(\frac{\lambda}{\mu}\right)^n\log_\mu \lambda<0$, which is true, because $1>\lambda>\mu>0$.

Answer 2

Do you remember: Given $${x^2} + p \cdot x + q = 0$$ and $$D = {p^2} - 4q$$ we have the roots $$x = \left\{ {\begin{array}{*{20}{c}} {\frac{{ - p - \sqrt D }}{2}} \\ {\frac{{ - p + \sqrt D }}{2}} \end{array}} \right.$$

As an application, we consider Fibbonacci-numbers: $$\begin{gathered} {f_0} = 1,{f_1} = 1 \hfill \\ {f_n} = {f_{n - 1}} + {f_{n - 2}} \hfill \\ \end{gathered} $$ and $${f_n} = {f_{n - 1}} + {f_{n - 2}} \Leftrightarrow {f_n} - {f_{n - 1}} - {f_{n - 2}} = 0$$ We build qudratic $${x^2} = x + 1 \Leftrightarrow {x^2} - x - 1 = 0$$ with $$p = - 1,q = - 1,D = {p^2} - 4 \cdot q = 1 + 4 = 5$$ and get roots $$x = \left\{ {\begin{array}{*{20}{c}} {\frac{{1 - \sqrt D }}{2}} \\ {\frac{{1 + \sqrt D }}{2}} \end{array}} \right.$$ With these roots we can write: $${f_n} = \frac{1}{{\sqrt D }} \cdot \left( {{{\left( {\frac{{1 + \sqrt D }}{2}} \right)}^{n + 1}} - {{\left( {\frac{{1 - \sqrt D }}{2}} \right)}^{n + 1}}} \right) = \frac{1}{{\sqrt 5 }} \cdot \left( {{{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)}^{n + 1}} - {{\left( {\frac{{1 - \sqrt 5 }}{2}} \right)}^{n + 1}}} \right)$$ We resolved the reccurence!

We are now going to apply this to your problem. Steps are exactly the same. Given: $$\begin{gathered} A(k) = 1 - 10 \cdot k,{V_0} = P \hfill \\ {V_1}(k) = A(k) \cdot {V_0} \hfill \\ {V_n}(k) = A(k) \cdot {V_{n - 1}}(k) - 5 \cdot k \cdot {V_{n - 2}}(k) \hfill \\ \end{gathered} $$ Then $${V_n}(k) - A(k) \cdot {V_{n - 1}}(k) + 5 \cdot k \cdot {V_{n - 2}}(k) = 0$$ with quadratic $${x^2} - A(k) \cdot x + 5 \cdot k = 0$$ Here $$p = - A(k),q = 5 \cdot k,D(k) = A{(k)^2} - 20 \cdot k$$ With the roots $$x = \left\{ {\begin{array}{*{20}{c}} {\frac{{A(k) - \sqrt D }}{2}} \\ {\frac{{A(k) + \sqrt D }}{2}} \end{array}} \right.$$ Now we set, like before: $${p_k}(n) = \frac{1}{{\sqrt {D(k)} }}\left( {{{\left( {\frac{{A(k) + \sqrt {D(k)} }}{2}} \right)}^{n + 1}} - {{\left( {\frac{{A(k) - \sqrt {D(k)} }}{2}} \right)}^{n + 1}}} \right)$$ and we have got: $${V_n}(k) = {p_k}(n) \cdot {V_0}$$ We resolved the reccurence. So far. What to with this? Perfect answer is given by @Alex Ravsky!