# Recursive Sequence Convergence (Not Monotonic)

I have the following sequence (derived from law of cosines):

$$d_{n+1}^2 = d_n^2 + r^2 - 2rd_n \cos \theta$$

such that $$r, d_n>0$$ and $$\theta < \frac{\pi}{2}$$.

I would like to show that the limit exists for this sequence. I believe the limit to be $$\frac{r}{2\cos \theta}$$.

Attempt: I originally tried to show that the sequence is bounded and monotonic. While it is bounded, it is not monotonic. So I thought maybe I could try to show that the sequence is Cauchy. But I am having trouble showing that as well.

Any hints/ideas? Thanks.

edit: If $$\theta = 0$$ the limit does not exist in general. So the restriction on $$\theta$$ is $$0<\theta<\frac{\pi}{2}$$.

edit 2: Example configuration to make $$d_n - \frac{r}{2 \cos \theta}$$ alternate +/-:

$$d_0 = 1$$, $$r=4$$, $$\theta = \frac{\pi}{6}$$

• Just checking: is it $d_n^2\color{red}{+}r^2-..$ or $d_n^2-r^2-..$ on the RHS? Apr 26 '20 at 22:24
• @anuragA yes! Thanks for catching that. Apr 26 '20 at 22:26
• I don't think it matters, but what is $d_0$? Apr 26 '20 at 22:33
• @VVejalla, $d_0 > 0$ only condition. I don't think it should matter. Apr 26 '20 at 22:38
• It seems that the seequence is alternately increasing and decreasing. That is, $d_{2n}$ and $d_{2n+1}$ are both monotonic. They approach their common limit in geometric progression. Apr 27 '20 at 0:41

Let us rewrite the problem as follows.

$$d_{n+1}^2 = d_n^2 + r^2 - mrd_n,\space where \space m := 2 cos(\theta), \space r > 0, \space\forall n (d_n > 0)$$

We can see that $$m \in (0;2)$$ as $$cos(\theta) \in (0;1)$$ for $$\theta \in (0;\frac \pi 2)$$.

It will be easier to consider the sequence $$(a_n) := (\frac {d_n} r)$$ as it only depends on $$m$$ and, possibly, $$d_0$$.

As we can see, $$a_{n+1}^2 = a_n^2 + 1 - ma_n$$

Now, we can observe that if the limit exists, it is equal to $$\frac 1 m$$.

If $$\exists L (\lim_{n\to\infty} {a_n} = L) \space \Rightarrow \exists L (\lim_{n\to\infty} {a_n} = L \wedge \lim_{n\to\infty} {a_{n+1}^2} = \lim_{n\to\infty} {a_n^2 + 1 - ma_n} = L^2 + 1 - mL = L^2) \Rightarrow \exists L (\lim_{n\to\infty} {a_n} = L \wedge L = \frac 1m) \Rightarrow \lim_{n\to\infty} {a_n} = \frac 1m \space (*)$$

It is also easy to derive the formula for the $$n$$-th term, by recursively applying the formula.

$$a_n^2 = a_0^2 + n - m\sum_{i=0}^{n-1}{a_i}$$

Now we will show that if an element of the sequence is below $$\frac 1 m$$, then every element after it is above the element in question.

$$a_n < \frac 1m \Rightarrow ( k = n + 1 \Rightarrow a_k^2 = a_{n+1}^2 = a_n^2 + 1 - ma_n > a_n^2 )$$

$$a_n < \frac 1m \Rightarrow ( \forall t ( n < t < k \Rightarrow a_t > a_n) \Rightarrow a_k^2 - a_n^2 = (k - n) - m\sum_{i=n}^{k-1}{a_i} > (k - n) - m\sum_{i=n}^{k-1}{a_n} = (k - n) - m(k - n)a_n > (k - n) - m(k - n)\frac 1m > 0 \Rightarrow a_k > a_n )$$

$$\therefore a_n < \frac 1m \Rightarrow( k > n \Rightarrow a_k > a_n )$$

Similarly, if an element is above $$\frac 1 m$$, then the sequence will always be below it.

$$a_n > \frac 1m \Rightarrow ( k = n + 1 \Rightarrow a_k^2 = a_{n+1}^2 = a_n^2 + 1 - ma_n < a_n^2 )$$

$$a_n > \frac 1m \Rightarrow ( \forall t ( n < t < k \Rightarrow a_t < a_n) \Rightarrow a_k^2 - a_n^2 = (k - n) - m\sum_{i=n}^{k-1}{a_i} < (k - n) - m\sum_{i=n}^{k-1}{a_n} = (k - n) - m(k - n)a_n < (k - n) - m(k - n)\frac 1m < 0 \Rightarrow a_k < a_n )$$

$$\therefore a_n > \frac 1m \Rightarrow( k > n \Rightarrow a_k < a_n )$$

We will partition the sequence $$(a_n)$$ into three other, depending on the relative positions of the elements and $$\frac 1 m$$.

$$(b_n)$$ - subsequence of $$(a_n)$$, such that $$\forall n (b_n > \frac 1m)$$

$$(c_n)$$ - subsequence of $$(a_n)$$, such that $$\forall n (c_n < \frac 1m)$$

$$(w_n)$$ - subsequence of $$(a_n)$$, such that $$\forall n (w_n = \frac 1m)$$

Observe that if $$a_n = \frac 1m\Rightarrow a_{n+1} = \frac 1m$$.

This implies, that once the sequence reaches $$\frac 1 m$$ it stays there.

$$\therefore a_k\in(w_n) \Rightarrow \lim_{n\to\infty}{a_n} = a_k = \frac 1m\blacksquare$$

We will, therefore, consider the other possibility, i.e. $$(w_n)\equiv\emptyset$$.

Thus every element is either strictly below or strictly above $$\frac 1 m$$.

$$(b_n)\cup(c_n) \equiv (a_n)$$

Now, if some subsequence is finite, the other one dominates on large indices. Additionally, each subsequence is monotone and bounded by $$\frac 1 m$$. Therefore, in this case, the infinite subsequence converges, implying the convergence of the sequence as a whole.

$$|(b_n)| < \aleph_0 \Rightarrow \exists N \forall n > N (a_n < \frac 1m \wedge \forall i \forall j (n < i < j \Rightarrow a_i < a_j)) \Rightarrow \exists L (\lim_{n\to\infty}{a_n} = L)\blacksquare$$

$$|(c_n)| < \aleph_0 \Rightarrow \exists N \forall n > N (a_n > \frac 1m \wedge \forall i \forall j (n < i < j \Rightarrow a_i > a_j)) \Rightarrow \exists L (\lim_{n\to\infty}{a_n} = L)\blacksquare$$

In these cases, we have only shown that the limit $$L$$ exists and $$L\ge\frac 1m$$ and $$L\le\frac 1m$$ respectively. The proof is completed by $$(*)$$.

We will now consider the case, when both subsequences are infinite, i.e. $$|(b_n)| = |(c_n)| = \aleph_0$$.

We will call their limits $$G_1$$ and $$G_2$$. The limits exist because both sequences are monotone and bounded.

$$G_1 := \lim_{n\to\infty} {b_n}$$

$$G_2 := \lim_{n\to\infty} {c_n}$$

Notice that $$\nexists n (b_n = G_1)$$ and $$\nexists n (c_n = G_2)$$, because the sequences are strictly monotone, and, therefore, cannot attain their respective limits.

$$\therefore \forall n > 0 (c_0 < c_n < G_2 \le \frac 1m \le G_1 < b_n < b_0)$$

If $$G_1 = G_2 \Rightarrow \lim_{n\to\infty} {a_n} = G_1 = G_2 = \frac 1m\blacksquare$$

Otherwise $$G_1 > G_2$$. We will consider this case next.

From the definition of a limit for a sequence of real numbers,

$$\forall \rho > 0 \exists N \forall n > N ((G_1 < b_n < G_1 + \rho) \wedge (G_2 - \rho < c_n < G_2))$$

We will now consider a function

$$f(x) := x^2 + 1 - mx$$

It is a polynomial and, therefore, it is continuous.

Also $$\forall n (f(a_n) = a_{n+1}^2)$$.

From the definition of a limit of a real-argument-real-valued function,

$$\therefore \forall \epsilon > 0 \exists \delta \forall y (|x - y| < \delta \Rightarrow |f(x) - f(y)| < \epsilon)$$

If it is the case, that the sequence infinitely often switches from being close to $$G_2$$ several times in a row to being close to $$G_1$$, then it will have "big" jumps for "small" differences in the initial values, which would mean, that $$f(x)$$ is not continuous.

If $$\forall N \exists n > N (a_n < G_2 \wedge a_{n+1} < G_2 \wedge a_{n+2} > G_1) \Rightarrow \forall \rho > 0 \exists N \exists n > N (|a_n - a_{n+1}| < \rho \wedge |a_{n+1} - a_{n+2}||a_{n+1} + a_{n+2}| > (G_1 - G_2) 2c_0 ) \Rightarrow \exists \epsilon > 0 \forall \rho > 0 \exists y (|G_2 - y| < \rho \wedge |f(G_2) - f(y)| > \epsilon)\Rightarrow\Leftarrow$$

A similar argument applies if we interchange $$G_1$$ and $$G_2$$.

If $$\forall N \exists n > N (a_n < G_1 \wedge a_{n+1} < G_1 \wedge a_{n+2} > G_2) \Rightarrow \forall \rho > 0 \exists N \exists n > N (|a_n - a_{n+1}| < \rho \wedge |a_{n+1} - a_{n+2}||a_{n+1} + a_{n+2}| > (G_1 - G_2) 2c_0 ) \Rightarrow \exists \epsilon > 0 \forall \rho > 0 \exists y (|G_1 - y| < \rho \wedge |f(G_1) - f(y)| > \epsilon)\Rightarrow\Leftarrow$$

This means that after a certain point, the sequence has to change between closeness to $$G_1$$ and $$G_2$$ at each step.

$$\therefore \exists N \forall n > N ((a_n < G_2 \Rightarrow a_{n+1} > G_1)\wedge (a_n > G_1 \Rightarrow a_{n+1} < G_2))$$

Thus after some point $$(b_n)$$ and $$(c_n)$$ alternate with some constant difference in indices.

$$\exists p \exists q \exists N \forall n > N (b_{n+1+p}^2 = c_{n+q}^2 + 1 - mc_{n+q} \wedge c_{n+1+q}^2 = b_{n+p}^2 + 1 - mb_{n+p})$$

If we take the limits of the equations, we will be left with equations in terms of $$G_1$$ and $$G_2$$.

$$\therefore \lim_{n\to\infty} {b_n^2} = \lim_{n\to\infty} {c_n^2 + 1 - mc_n} \wedge \lim_{n\to\infty} {c_n^2} = \lim_{n\to\infty} {b_n^2 + 1 - mb_n}$$

$$G_1^2 = G_2^2 + 1 - mG_2$$

$$G_2^2 = G_1^2 + 1 - mG_1$$

We can solve this system as follows.

$$G_1^2 + G_2^2 = (G_2^2 + 1 - mG_2) + (G_1^2 + 1 - mG_1)$$

$$0 = 2 - m (G_1 + G_2)$$

Now we know the sum of $$G_1$$ and $$G_2$$.

$$\therefore G_1 + G_2 = \frac 2m$$

$$G_1^2 - G_2^2 = (G_2^2 + 1 - mG_2) - (G_1^2 + 1 - mG_1)$$

$$G_1^2 - G_2^2 = G_2^2 - G_1^2 - mG_2 + mG_1$$

$$2(G_1^2 - G_2^2) = m(G_1 - G_2)$$

$$2(G_1 - G_2)(G_1 + G_2) = m(G_1 - G_2)$$

We have already established that $$G1 > G2$$, therefore, $$G_1 - G_2 \neq 0$$ and as such

$$2(G_1 + G_2) = m$$

$$G_1 + G_2 = \frac m2$$

We already know another formula for the sum of $$G_1$$ and $$G_2$$. Substituting it, we get

$$\frac m 2 = \frac 2 m$$

This is only possible if $$m$$ is $$2$$ or $$-2$$.

$$m = 2 \vee m = -2 \Rightarrow\Leftarrow$$

Nevertheless, we know it is not possible, because $$m \in (0;2)$$. Therefore, our assertion that $$G_1 > G_2$$ was false.

At this point, we have exhausted the cases and have shown that each of them is either impossible or implies $$\lim_{n\to\infty} {d_n} = \lim_{n\to\infty} {r a_n} = \frac r m = \frac r {2 cos(\theta)}$$. $$\blacksquare$$

• This is a fantastically detailed answer. I admit it's taking me a while to parse exactly what is going on. In particular, it's taking me a while to understand your arguments for G1 and G2. I'm also not following how we know that the subsequences $b_n$ and $c_n$ are monotonic. I need to give this another read or two... May 15 '20 at 4:57
• @T. Fo We have proven that if $a_n > \frac 1m$ then every $a_k$ after it is smaller, therefore, if $i > j$ then $b_i > b_j$, note that $b_n > \frac 1m$. Simmilar argument applies for $(c_n)$. May 15 '20 at 22:56