Inequalities approach in determination of convergence of recurrence sequences

1. Introduction

Sequences could be defined in many forms, however, most sequences may be quite difficult to establish closed formulas for their forms. Nonetheless, it is often easier or much preferable to express sequences by recursive definitions. It is essential to note that some recursive relations are adaptive and could be converted into closed formulas devoid of a recurrence relation. By [1,2,3,4,5,6,7] a recurrence relation is an equation that inductively defines a successive term of a sequence in terms of one or more preceding term(s) of the sequence. Notably, some useful applications of recurrence relation can be seen in the study of models involving population growth, investments, depreciation, algorithm analysis, digital signal processing, and cryptography.

In this paper, we shall consider the following special sequences;

• (I)   \( u_{n+1} = \dfrac{a}{b} u_{n} + c \),
• (II)   \( u_{n+1} = \dfrac{1}{2} \left( u_{n} + \dfrac{a}{u_{n}} \right) \),
• (III)   \( u_{n+1} = \sqrt{a + \sqrt{u_{n}}} \).

These sequences are all defined by a recursion relation with \( a, b, \) and \( c \) being positive real numbers. Each of the above sequences has a special name connected to it. The first is generally called a first-order difference equation or an arithmetico-geometric sequence, the second type in contemporary times is called the Newton-Raphson algorithm, and the last is referred to as the nested radical sequence.

The consideration of the sequence (I) is its usefulness. This will afford us the advantage of thoroughly illustrating its flexibility in drumming home the processes involve in showing that a given sequence is convergent. Also, due to the practicality of the sequence (II) we will demonstrate and prove a general bound for this important sequence without inferring from the monotone convergence theorem, although it is always implied. The determination of a supremum or an infimum could be a daunting prospect. Such a theorem is invoked because it asserts that, if by some means we are able to know just the upper (lower) bound and along with a possible fact that a sequence is monotonic increasing(decreasing), then convergence is guaranteed and the limit exists, as is often the case in literature [8,9,10,11]. Similarly, for the nested recurrence sequence (III), we shall meticulously demonstrate how one could use arithmetic arguments and bi-quadratic equation rather than mathematical induction to prove their boundedness, monotone property, and the general limit to which they converge to. The motivation is garnered to challenge and encourage real analysis students that, there is no one size fit approach in tackling convergence and to introduce some flavor of using basic inequalities of algebra and equations to achieve convergence for a given well-defined recursive sequence. This is neither to downplay the applications of the monotone convergence theorem that is usually adopted without necessarily having to obtain a bound and to prove it for the particular sequence being investigated upon, nor to discourage the use of mathematical induction, but rather to logically use arguments involving inequalities to explore monotonic properties and boundedness especially for sequences defined recursively under the radical symbol.

2. Literature review

The concept we seek to explore is deeply rooted in the qualitative research paradigm, and hence the need to review the works of earlier authors at least on the convergence of a sequence and in particular sequences that are defined inductively by a recurrence relation.

The sequence of the form \( u_{n} = au_{n-1} + b \) is a first-order difference equation, in the sense that we are looking back one unit in time to \( u_{n-1} \) with its exponentiation being unity. This sequence has two main characterizations as far as the nomenclature of their classification is concerned. For instance when \( a = 1 \) the resulting recurrence relation leads to \( u_{n} = u_{0} + nb \) a closed-form formula of a special class of sequence referred to as arithmetic progression, and when \( a \ne 1 \), it transforms into another special class of sequence known as geometric progression with a closed formula given by \( u_{n} -k = a^{n} (u_{0}-k) \) with \( k = b/(1-a) \).

One can observe that if the initial preceding term \( u_{0} = k \), then the geometric characterization collapses and the sequence fall into a different classification altogether known as a constant sequence.

A careful study of this type of difference equation provides a qualitative insight into the convergence of many other types of sequences. It is because of this instance that such an important recurrence algorithm has earned the name, the arithmetico-geometric sequence. Such a sequence posses the same intrinsic properties in connection with the general case of the sequence type (I). As such we shall develop a contractive sequence for their kind to enable us to investigate it further.

From a practical viewpoint, a successive approximation method or iteration that comes up in the area of numerical analysis is in the evaluation of the square root of a given real number '\( a \)'. Such a procedure is developed upon the fact that if \( x \) is exactly equal to \( \sqrt{a} \), so is the quotient of \( a/x \). On the contrary, regardless of how \( x \) and \( a/x \) are less or greater than \( \sqrt{a} \), the square root of the real number '\( a \)' will always lie between \( x \) and \( a/x \) [12,13,14]. Thus, the arithmetic mean of these two uniquely defined numbers can fairly be expressed as a fixed point equation or a recursive sequence with an initial guess \( x_{1} = x_{0} \) assumed to be a good approximate to \( \sqrt{a} \) which gets better and better to any decimal place of our choice as we progress further away from our initial guess using the resulting recursive sequence. Such an ingenious way of computing the square root predates Newton and was known in Mesopotamia (1,500 B.C.) as well as the Greeks ( A.D) [15,16]. Unfortunately, these nameless Babylonian mathematicians and Greeks did not receive credit for their useful fast convergence technique which has successfully been incorporated into programmable calculators or graphing utility and microcomputers as an algorithm for the calculation of the square root of positive real numbers [12,17]. Interestingly enough, by subjecting the simple equation of the form \( x^{2}-a = 0 \) to the Newton-Raphson's method [18], one is led to the sequence type (II) \( u_{n+1} = 1/2(u_{n} + a/u_{n}) \), the precise form of the fixed point intervention explored and used by the Babylonian much earlier than Newton and his compatriots. It is in the light of this coincidence that such an important sequence has come to bear their names instead. We shall demonstrate and prove a general bounded interval that satisfies the convergence criteria for such a sequence using AM-GM relations and the inequality of basic algebra.

The study of nested radicals do not date back into a very distant past, and for what it worth, it was until the 1800s, and in the early 1900s, that mathematicians in that era such as Galois and Ramanujan brought such intriguing continued squares to the center stage [19].

Recurrence relations under a radical sign are best handled using prove by induction [20]. Despite these claims, Ramanujan offers a way of handling such problems and even much more so, on the corridors of analysis, a single radical involving their definition results in a polynomial of degree two, which is easily solved with effortless ease. The situation is quite different, in fact, the level of complexity increases exponentially and becomes more complicated [21] when the radical goes beyond unity. The sequence type (III) falls into this category and hopefully, we shall use the reduced form of a bi-quadratic to determine a general expression to which such a sequence turns to, as one goes infinitely far in the sequence [13].

Besides, the monotone convergence theorem [22,23] is usually invoked and assumed if a limit of a sequence can be determined beforehand, but getting an upper bound or a lower bound is nearly impossible for a monotonically decreasing or increasing sequence. The sequence cannot go pass its infimum or supremum and so depending on the directions to which the terms are gradually clustering toward, the infimum or supremum may pass for its limit of convergence.

3. Analysis and results

The limit of a recursive sequence can easily be developed from a fixed point consideration, that is, by going out far enough in the sequence away from the initial term, the terms of the sequence get sufficiently closer and closer to each other [13]. A fix point equation could be adopted from the defining recursive sequence, however, this does not guarantee convergence. The sufficient and necessary condition needed to conclude convergence is to demonstrate that the sequence is bounded and monotonic.

3.1. Prove of convergence for recursive sequence type I

An attempt is made in proving the convergence of the real sequence defined by One could convert the sequence \( u_{n} \) of Equation (1) into a contractive sequence of the form where \( x \) is to be determined. We can do this by grouping the quantity \( x \) in Equation (2) and comparing the resulting expression with the original form of the sequence of equation (1) [24]. It turns out that \( x = bc/(b-a) \) and by implication, Equation (2) becomes Equation (3) is qualitatively informative for three main reasons.

The first being that, the quantity \( x = bc/(b-a) \) serves as an equilibrium point with regard to the stability of the sequence type (I). This may play the row of either an upper bound or a lower bound, depending on how the initial pre-defined term \( u_{1} \) is less or greater than it.

Secondly, it is susceptible to the derivation of a closed-form formula for all integral values of \( n \).

Thirdly, since the fraction \( a/b \) is clearly less than unity, it follows that the contraction sequence is convergent.

Now we shall show boundedness and monotonic characterization of the sequence by making the conjecture that

then Observe that with the given condition for the inequality, \( 0 < a < b < c \) associated with the problem, we may write, \( c-a > b-a > 0 \), so that By combining Equation (5) with Equation (6), we get \[ \dfrac{ab}{b-a} < \dfrac{a(a-c)+bc}{b-a} < u_{n+1} < \dfrac{bc}{b-a} .\] Since \[ \dfrac{ab}{b-a} \le \dfrac{ab}{b-a} = u_{1} < \dfrac{bc}{b-a}, \quad \forall\;\; n \ge 1 \] so the claim is proved and \( u_{n} \) is bounded by Equation (4).

Next, we prove monotonic property for \( u_{n} \) by noting that

Thus, \( u_{n+1}-u_{n} > 0 \), showing \( u_{n} \) is a monotonic increasing sequence. Since the sequence \( u_{n} \) exhibits monotonicity and boundedness, we are guaranteed of convergence and the recurrence sequence converges to a limit \[ L = \dfrac{a}{b} L + c \implies L = \dfrac{bc}{b-a} .\] It can be readily shown that for successively putting integral values of \( n \) into the contractive sequence of Equation (3), we get a closed-form formula that satisfies the difference equation by

3.2. Prove of convergence for recursive sequence type II

Given the sequence for the evaluation of the square root of some general real number '\( a \)' by \[ u_{n+1} = \dfrac{1}{2} \left( u_{n} + \dfrac{a}{u_{n}}\right), \mbox{ where } u_{1} > 0, \, a > 0, \, n \ge 1, \] we show convergence as follows.

Firstly, it can be seen that the arithmetic geometric mean of

\[ u_{n+1} = \dfrac{1}{2} \left( u_{n} + \dfrac{a}{u_{n}} \right) \ge \sqrt{a} .\] Since this algorithm evaluates the square root of a positive real number '\( a \)', it is plausible to assert that the root of a number cannot be equal or greater than the number itself except 1. Thus, the choice of an upper bound for the sequence type (II) is taken to be the positive real number '\( a \)' itself and hence we shall claim that By finding half the sum of Equation (9) and its reciprocal, we obtain But Also Equation (12) holds true by imposing AM-GM relation on the RHS of the sequence type (II). Combining Equations (10)-(12), it follows that indeed \( \sqrt{a} < u_{n} < a \). Since \( u_{1} > 0 \), then \( \forall n \le 1 \) the boundedness of \( u_{n} \) is proved.

Next, to show that \( u_{n} \) is monotonic non-increasing sequence, we may infer from our claim that

Next on dividing both sides of the resulting inequality of Equation (13) by 2, we see that \[ u_{n+1} = \dfrac{1}{2} \left( u_{n} + \dfrac{a}{u_{n}} < u_{n} \right) .\] Hence, the result is established.

Once \( u_{n} \) meets the litmus test of being monotonic and bounded, it converges to a limit which is exactly the same as its fixed point, thus from the recurrence relation, it is readily shown as

\[ L^{2} -a = 0 \implies L = \pm \sqrt{a} \implies L = \sqrt{a} .\] Observe that the negative fixed point is discarded mainly for two reasons; the first being that the sequence \( u_{n} > 0 \), and secondly, it is outside the defining bound for the sequence \( u_{n} \).

3.3. Prove of convergence for recursive sequence type III

To determine the convergence of the nested square root sequence, defined inductively by \[ u_{n+1} = \sqrt{a + \sqrt{u_{n}}}, \mbox{ where } u_{1} = \sqrt{a}, \, a > 2, \, n \ge 1, \] we must show that the sequence is bounded and also posses monotone property. To help achieve this, we first claim and prove that \( u_{n} \) is bounded in the interval \( 0 < u_{n} < a \). By this claim, we must demonstrate that the successive term \( u_{n+1} \) also lies in this bound and satisfies this claim. The implication of such a claim leads to the following inequalities By using the algebra of inequality to combine these inequalities we obtain Again, finding the square root of Equation (15), we see that \[ 0 < u_{n+1} = \sqrt{a + \sqrt{u_{n}}} < a .\] Since \( 0 < u_{1} = \sqrt{a} < a \), it follows that for all \( n\ge 1 \), the claim \( 0 < u_{n} < a \) holds true.

Next to show that \( u_{n} \) is monotonic, one may be able to equally write down

It can also be observed by the triangular inequality for the terms of the inequality of Equation (16) that Furthermore, by taking at least one arithmetic mean for the real numbers \( \sqrt{u_{n}}, \, u_{n} \), and '\( a \)' in ascending order of magnitude of the interval bounding \( u_{n} \), Equation (17) also holds true in the sense that Now, since \( a > 2 \), we can write \( 0 < 2 \le u_{n} < a \), so that Thus, on considering equality by combining Equations (18) and (19) Finally, by taking square root on each side of Equation (20), it follows that \[ u_{n} < \sqrt{a+ \sqrt{u_{n}}} = u_{n+1} \] and the result is proved.

Now having shown that \( u_{n} \) is bounded and monotonic, we know the sequence converges to a limit, thus \( \lim\limits_{n \to \infty} u_{n+1} = \lim\limits_{n \to \infty} u_{n} = L \). Eliminating the radicals from the recurrence sequence, we see that the value to which the limit \( L \) of the sequence \( u_{n} \) converges to is satisfied by the equation \( L^{4} - 2 aL^{2} - L + a^{2} = 0 \). To solve this equation, it can be seen that the form of the equation could be expressed as

where the unknown real constants \( k, m \), and \( n \) are to be determined by the equations By further expressing both \( m \) and \( n \) in terms of \( k \), then Equation (22) reduces to Equation (23) does not factorize easily, however, it would always have at least a root that is real. This real solution can be seen to coincide with a factorizing polynomial of the form \( k^{6} - 4 a k^{4} = 0 \). This may be shown by the triangular law in [13,25] that \[|k^{6}-4ak^{4}| - |1| \le |k^{6}- 4ak^{4} -1| = 0 \implies |k^{6}-4ak^{4}| \le 1 . \] This implies that

A sketch of the resulting Equation (23) and the approximating polynomial is shown in Figure 1.

We may infer from Equations (22) and (24) or from Figure 1 that for equality to hold Now the unknown which leads to a non-imaginary root yields \( m = (4a^{2}- \sqrt{a})/4a \). Extracting the factor \( (L^{2}-kL + m) \) being identical to zero from Equation (21) and solving for \( L \), we obtain \begin{multline*} L = \dfrac{1}{2} \left( 2 \sqrt{a} \pm \sqrt{4a - (4a^{2}- \sqrt{a})/a} \right) = \dfrac{1}{2} \left( 2 \sqrt{a} \pm \dfrac{1}{\sqrt[4]{a}} \right) \implies L = \dfrac{1}{2a} \left( 2 \sqrt{a^{3}} + \sqrt[4]{a^{3}} \right). \end{multline*} Even though both roots are positive, the choice of \( L = {1}/{2a} \left( 2 \sqrt{a^{3}} + \sqrt[4]{a^{3}} \right) \) lies within the bound for the defining sequence. For a relatively very large leading term say \( a\ge 100 \), the limit is 5 decimal places accurate to the real limit. Alternatively, for relatively small values of the leading term \( a\ge2 \), it yields favorable results to at least 2 decimal places or better.

4. Discussion of results

The discussion of the results will be narrowed down to the monotonic property and the pre-defined terms associated with the given sequences under consideration. The choice of the initial point plays the vital row of skewing a sequence to a particular direction in their classification as monotonically increasing or decreasing sequence. For instance, in the case of sequence type I, if the initial point is made bigger than the equilibrium point \( bc/(b-a) \), or on the other hand, if we take the leading term '\( a \)' of the sequence type III as its initial term, it turns out that both sequence types now becomes monotonically decreasing. There is however an exception to this rule, some recursive sequences are not affected by the choice of the initial point. A point in case is sequence type II, that is if we take the initial point to be lesser than the lower bound \( \sqrt{a} \), it will exhibit monotonic increasing behavior for finite consecutive terms of the sequence to a point, but will eventually assume its true characterization as a decreasing sequence in general, for infinitely many terms of that sequence. The underline principle of illustrating that a sequence is monotonic is hinged on comparison and so different approaches that make such conditions achievable were exploited for the various sequence types I, II, and III considered.

Finally, another observation worth noting is that sequence type I yielded a closed-form formula, while sequence types II and III did not. This is typical for most sequences due to their intricate nature. Therefore, any attempt to obtain their closed forms could be a waste of effort. Fortunately, with or without a closed-form formula, bit and pieces of qualitative information could be derived from a recurrence sequence and could be equally used to achieve the same purpose as a closed-form formula.

5. Conclusion

In the present study, convergence of the generalization of three types of sequences defined recursively, with special names given as, the first-order difference equation or the arithmetico-geometric sequence, the Newton-Raphson's algorithm, and the nested square root problem are discussed. A strict use of the algebra of inequalities and equations were applied to these recursive sequences to establish convergence. Remarkably, they were in agreement in principle with the use of mathematical induction and other techniques usually applied in proving convergence with respect to recursive sequences. The study clearly falls in line with the monotone convergence theorem and offers an alternative way of establishing boundedness, monotonicity, and convergence in connection with such special sequences.

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflicts of Interest

The authors declare no conflict of interest.