Abstract
We show that a recursive relation for finding square roots of numbers is naturally obtained from an iteration process, and that the relation is solvable in closed form, explaining some results in the literature in an elegant way. We also present a class of recursive relations for finding square roots of numbers which are also solvable in closed form, considerably extending and unifying such recursive relations.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let \({{\mathbb {N}}}\), \({{\mathbb {Z}}}\), \({{\mathbb {R}}}\), \({{\mathbb {C}}}\) stand for the sets of natural, integer, real and complex numbers respectively, \({{\mathbb {N}}}_0={{\mathbb {N}}}\cup \{0\}\) and \({{\mathbb {R}}}_+=(0,\infty )\). Assume that \(s,t\in {{\mathbb {Z}}}\), then we use the notation \(j=\overline{s,t}\) instead of writing \(s\le j\le t\), \(j\in {{\mathbb {Z}}}\). By \(C^n_j\), \(n\in {{\mathbb {N}}}_0\), \(j=\overline{0,n},\) we denote the binomial coefficients.
There are many recursive relations by which square roots of numbers can be found. One of the most known ones is the following
where \(a\in {{\mathbb {R}}}_+\). It is well known that for any \(x_0\in {{\mathbb {R}}}_+\), such defined sequence \(x_n\) converges to \(\sqrt{a}\), when \(n\rightarrow +\infty \) (see, e.g., [5, 7, 8]).
Equation (1) can be obtained by choosing the function
in the Newton iteration process
A square root of a number a can be also obtained by using the recursive relation
It is interesting that (4) can be obtained by using the secant method
to the function in (2) (see, e.g., [39]).
Another recursive relation for finding a square root of a number a is the following
This relation seems not so known as (1), but also frequently appears in the literature (see, e.g., [17, 23, 30]).
Since (6) is a recursive relation of the form
where the function
for \(a\in {{\mathbb {R}}}_+\), maps \({{\mathbb {R}}}_+\) into itself, convergence of its positive solutions can be dealt with by using some standard arguments (see, e.g., [5, Problems 9.34, 9.35]) in various ways (see, e.g., the arguments in [23, 30]).
What is interesting related to recursive relations (1) and (4), is the fact that their solutions can be found in closed form (see, e.g., [7, 8, 19, 37, 39]). These are two examples of nonlinear recursive relations/difference equations solvable in closed form. Generally speaking, solvability of nonlinear difference eqations is a rare phenomena. This is one of the reasons why for nonlinear difference equations is also studied the existence of invariants. For some recent related results on solvability and invariants for nonlinear difference equations see, e.g., [3, 4, 25,26,27, 29, 31, 32, 34,35,36, 38, 40, 41] and the related references therein. Some old results on the topics can be found, e.g., in [1, 2, 6, 10, 11, 14, 20,21,22,23,24]. For some other related equations see also [13, 15, 16, 18, 28, 33, 42].
Here we show how recursive relation (6) can be obtained from an iteration process in the literature. Beside this, we show that the recursive relation is also solvable in closed form by presenting its general solution, and present a class of recursive relations for finding square roots which are also solvable in closed form, extending and unifying recursive relations (1) and (6).
2 Main results
This section presents our main results in this paper.
2.1 An iteration process forming (6)
It is a natural question if recursive relation (6) can be also obtained from a known iteration process. Here we deal with the problem.
The considerations in the previous section suggest that the requested iteration process should be related to the Newton one. To find the roots of the algebraic equation
on an interval I, where f is a given function, is the same as to find the roots of the equation
if the roots of the function g does not belong to the interval. Hence, in (3), instead of f we can use the function fg ( [9]), and obtain
By suitable choice of function g we can obtain various iteration processes.
Let
Then, by some simple calculations (7) becomes
Since we want to find a root of a number a it is natural to choose the function f as in (2). By using it in (8) we obtain
To get recursive relation (6) from (9) is only possible if
from which it follows that \(b=-1/2.\) By using such obtained b in (9) we really obtain (6).
The above consideration shows that recursive relation (6) is obtained from the iteration process in (7) with
Note that function (10) does not have a zero on \({{\mathbb {R}}}_+\), so the functions
have the same set of zeros on \({{\mathbb {R}}}_+.\)
2.2 Solvability of recursive relation (6)
The fact that recursive relations (1) and (4) are solvable in closed form naturally suggests investigation of solvability of recursive relation (6). Here we deal with the problem.
It should be pointed out that it is a quite rare situation when nonlinear recursive relation is solvable in closed form. This is why majority of authors use other methods for dealing with the nonlinear relations, which was also the case in [23] and [30], where was considered relation (6).
Let \(x^*\) be an equilibrium of (6). Then we have
from which it follows that
Hence
Since we calculate square root of a number different from zero, the equilibrium \(x^*=0\) is of no interest in the investigation.
What is interesting, is to consider the sequence
The difference is usually considered when is studied convergence of a sequence.
Simple calculation shows that
Further, similarly is obtained
from which it easily follows that
Finally, from (13) we obtain
Let
Then, (14) can be written as follows
Since
we have that the sequence defined in (14) is a solution to Eq. (6). In fact, (14) is the general solution to the equation.
From the previous detailed consideration we see that the following theorem on solvability of relation (6) holds.
Theorem 1
Assume that \(a\in {{\mathbb {R}}}_+\) and \(x_0\in {{\mathbb {R}}}_+\). Then, recursive relation (6) is solvable in closed form and its general solution is given by the formula
Remark 1
Note that in the above consideration we have not used the assumption \(x_0\in {{\mathbb {R}}}_+\). This means that formula (15) also holds if \(x_0\in {{\mathbb {R}}}\) or \(x_0\in {{\mathbb {C}}}.\) Beside this, the consideration also holds for any \(a\in {{\mathbb {C}}}\setminus \{0\}.\) Hence, formula (15) also holds in this case.
From (15) we also see that a solution to (6) is well defined if and only if
for every \(n\in {{\mathbb {N}}}.\) Note that if \(x_0, a\in {{\mathbb {R}}}_+\), then the relation in (16) holds for every \(n\in {{\mathbb {N}}}.\)
Remark 2
If \(a=0\), then (6) becomes
from which it easily follows that
when \(x_0\ne 0.\) This means that recursive relation (6) is also solvable in this case and that the general solution in this case is given by formula (18). If \(x_0=0\), then the solution to (17) is not well-defined.
Remark 3
Note that from (11) we have
from which it follows that for \(a>1\) the sequence \(x_n\) converges to \(\sqrt{a}\) very quickly. Namely, according to the standard terminology, the rate of the convergence has the third order [12].
Remark 4
By using formula (15) the convergence result in [23, 30] immediately follows. Namely, if \(a>0\), then every positive solution to (6) is convergent. Indeed, if \(x_0>0\), then we have
Hence
By letting \(n\rightarrow +\infty \) in formula (15) and using the last relation, the result easily follows.
2.3 Two other recursive relations for calculating square roots
It is a natural problem to find some other recursive relations for calculating square roots which are solvable in closed form.
Here we present two examples of such recursive relations, which are related to relations (1) and (6), and give some comments with respect to the obtained formulas for their solutions.
Consider the recursive relation
Let \(x^*\) be an equilibrium of (19). Then we have
from which it follows that
Hence
By some calculation we have
and
Hence
and consequently
As is the case of relation (6) it is verified that the last expression is a solution to relation (19).
From this we obtain the following theorem.
Theorem 2
Assume that \(a\in {{\mathbb {C}}}\setminus \{0\}\) and \(x_0\in {{\mathbb {C}}}\). Then, recursive relation (19) is solvable in closed form and its general solution is given by the formula
Remark 5
If \(a=0\), then (19) becomes
from which it follows that
when \(x_0\ne 0.\) Hence, recursive relation (19) is also solvable in this case and its general solution is given by formula (24). If \(x_0=0\), then the solution to (23) is not well-defined.
Remark 6
By using formula (22), we easily see that for \(a>0\) every positive solution to (19) converges to \(\sqrt{a}.\)
Remark 7
Recursive relation (19) could be also obtained by a known iteration process or by a modification of a known iteration process, but, at the moment, we do not see from which one.
Now we consider the recursive relation
Let \(x^*\) be an equilibrium of (25). Then we have
from which it follows that
Hence
The equilibrium \(x^*=0\) is of no special interest for calculating square roots.
We have
and
Hence
and consequently
As is the case of relation (6) it is verified that the last expression is a solution to relation (25).
So, we get the following theorem.
Theorem 3
Assume that \(a\in {{\mathbb {C}}}\setminus \{0\}\) and \(x_0\in {{\mathbb {C}}}\). Then, recursive relation (25) is solvable in closed form and its general solution is given by the formula
for \(n\in {{\mathbb {N}}}_0.\)
Remark 8
If \(a=0\), then (25) becomes
from which it follows that
when \(x_0\ne 0.\) So, recursive relation (25) is also solvable in this case and its general solution is given by formula (30). If \(x_0=0\), then the solution to (29) is not well-defined.
Remark 9
From (26) we have
from which it follows that when \(a>1\) the sequence \(x_n\) converges to \(\sqrt{a}\) very quickly (the rate of convergence has the fifth order).
Remark 10
By using formula (28), we easily see that for \(a>0\) every positive solution to (25) converges to \(\sqrt{a}.\)
2.4 Two families of recursive relations generalizing the ones in (19) and (25)
Unlike relations (1) and (6), the recursive relations in (19) and (25) could be new (as far as we know they are new).
It is a natural question if the recursive relations are special cases of some classes of solvable nonlinear recursive relations. Here we deal with the problem. We present two families of recursive relations which naturally generalize the ones in (1), (6), (19) and (25). We show their solvability by presenting closed form formulas for their general solutions.
First, we consider a family of recursive relations, which generalizes relations (1) and (19).
Theorem 4
Let \(k\in {{\mathbb {N}}}\) and \(a\in {{\mathbb {C}}}\setminus \{0\}\). Consider the recursive relation
for \(n\in {{\mathbb {N}}}_0,\) where \(x_0\in {{\mathbb {C}}}\). Then, relation (31) is solvable in closed form and its general solution is given by the formula
Proof
We have
and
for \(n\in {{\mathbb {N}}}_0.\)
Hence
from which formula (32) easily follows. \(\square \)
From Theorem 4 the following corollary easily follows.
Corollary 1
Assume that \(k\in {{\mathbb {N}}}\), \(a\in {{\mathbb {R}}}_+\). Then every positive solution to (31) converges to \(\sqrt{a}.\)
Now we consider a family of recursive relations, which generalizes relations (6) and (25).
Theorem 5
Let \(k\in {{\mathbb {N}}}\) and \(a\in {{\mathbb {C}}}\setminus \{0\}\). Consider the recursive relation
for \(n\in {{\mathbb {N}}}_0,\) where \(x_0\in {{\mathbb {C}}}\). Then, relation (35) is solvable in closed form and its general solution is given by the formula
Proof
We have
and
for \(n\in {{\mathbb {N}}}_0.\)
Hence
from which formula (36) follows. \(\square \)
From Theorem 5 the following corollary easily follows.
Corollary 2
Assume that \(k\in {{\mathbb {N}}}\), \(a\in {{\mathbb {R}}}_+\). Then every positive solution to (35) converges to \(\sqrt{a}.\)
Availability of data and material
Not applicable.
References
Adamović, D.: Problem 194. Mat. Vesnik 22(2), 270 (1970)
Adamović, D.: Solution to problem 194. Mat. Vesnik 23, 236–242 (1971)
Andruch-Sobilo, A., Migda, M.: On the rational recursive sequence \(x_{n+1}=ax_{n-1}/(b+cx_nx_{n-1}),\) Tatra Mt. Math. Publ. 43, 1–9 (2009)
Bajo, I., Liz, E.: Global behaviour of a second-order nonlinear difference equation. J. Differ. Equat. Appl. 17(10), 1471–1486 (2011)
Bashmakov, M. I., Bekker, B. M., Gol’hovoi, V. M.: Zadachi po Matematike. Algebra and Analiz. Nauka, Moskva, (1982). (in Russian)
Boole, G.: A Treatsie on the Calculus of Finite Differences, 3rd edn. Macmillan and Co., London (1880)
Demidovich, B.P.: Sbornik Zadach i Uprazhneniy po Matematicheskomu Analizu, 8th edn. Nauka, Moskva, (1972) (in Russian)
Demidovich, B.P., Maron, I.A.: Computational Mathematics. Mir Publishers, Moscow (1973)
Djordjević, L.N.: An iterative solution of algebraic equations with a parameter to accelerate convergence. Publ. Elektroteh. Fak. Ser. Mat. Fiz. No. 412–460, 179–182 (1973)
Euler, L.: Introductio in Analysin Infinitorum, Tomus Primus, Lausannae, (in Latin) (1748)
Herschel, J. F. W.: A Collection of Examples of the Applications of the Calculus of Finite Differences, Cambridge, Printed by J. Smith (1820)
Hildebrand, F.B.: Introduction to Numerical Analysis, 2nd edn. Dover, Mineola (1987)
Iričanin, B.: Global stability of some classes of higher-order nonlinear difference equations Appl. Math. Comput. 216(4), 1325–1328 (2010)
Jordan, C.: Calculus of Finite Differences. Chelsea Publishing Company, New York (1956)
Karakostas, G.L.: Asymptotic 2-periodic difference equations with diagonally self-invertible responces. J. Differ. Equations Appl. 6, 329–335 (2000)
Kent, C.M.: Convergence of solutions in a nonhyperbolic case. Nonlinear Anal. 47(7), 4651–4665 (2001)
Kosmala, W.A.: A Friendly Introduction to Analysis, 2nd edn. Pearson, Upper Saddle River, New Jersey (2004)
Kosmala, W.A., Teixeira, C.: More on the difference equation \(y_{n+1}=(p+y_{n-1})/(qy_n+y_{n-1}),\) Appl. Anal. 81(1), 143–151 (2002)
Krechmar, V.A.: A Problem Book in Algebra. Mir Publishers, Moscow (1974)
Lacroix, S. F.: Traité des Differénces et des Séries, J. B. M. Duprat, Paris (in French) (1800)
Lacroix, S.F.: An Elementary Treatise on the Differential and Integral Calculus, with an Appendix and Notes by J. J. Smith, Cambridge, Herschel (1816)
Laplace, P. S.: Recherches sur l’intégration des équations différentielles aux différences finies et sur leur usage dans la théorie des hasards, Mémoires de l’ Académie Royale des Sciences de Paris 1773, t. VII, (1776) (Laplace OEuvres, VIII, 69-197, 1891). (in French)
Mitrinović, D. S., Adamović, D. D.: Nizovi i Redovi/Sequences and Series, Naučna Knjiga, Beograd, Serbia, (1980) (in Serbian)
Mitrinović, D. S., Kečkić, J. D.: Metodi Izračunavanja Konačnih Zbirova/Methods for Calculating Finite Sums, Naučna Knjiga, Beograd (in Serbian) (1984)
Papaschinopoulos, G., Schinas, C.J.: Invariants for systems of two nonlinear difference equations. Differ. Equ. Dyn. Syst. 7, 181–196 (1999)
Papaschinopoulos, G., Schinas, C.J.: Invariants and oscillation for systems of two nonlinear difference equations. Nonlinear Anal. Theory Methods Appl. 46, 967–978 (2001)
Papaschinopoulos, G., Schinas, C. J., Stefanidou, G.: On a \(k\)-order system of Lyness-type difference equations, Adv. Difference Equ. 2007, Article ID 31272, 13 (2007)
Papaschinopoulos, G., Schinas, C.J., Stefanidou, G.: Two modifications of the Beverton-Holt equation. Int. J. Differ. Equ. 4(1), 115–136 (2009)
Papaschinopoulos, G., Stefanidou, G.: Asymptotic behavior of the solutions of a class of rational difference equations. Inter. J. Differ. Equ. 5(2), 233–249 (2010)
Sadovnichiy, V. A., Podkolzin, A. S.: Zadachi Studencheskih Olimpiad po Matematike, Moskva, Nauka, (1978) (in Russian)
Schinas, C.: Invariants for difference equations and systems of difference equations of rational form. J. Math. Anal. Appl. 216, 164–179 (1997)
Schinas, C.: Invariants for some difference equations. J. Math. Anal. Appl. 212, 281–291 (1997)
Stević, S.: A global convergence results with applications to periodic solutions. Indian J. Pure Appl. Math. 33(1), 45–53 (2002)
Stević, S.: Solvable product-type system of difference equations whose associated polynomial is of the fourth order, Electron. J. Qual. Theory Differ. Equ. 2017, Article No. 13, 29 (2017)
Stević, S.: Solving a class of non-autonomous difference equations by generalized invariants. Math. Methods Appl. Sci. 42, 6315–6338 (2019)
Stević, S.: New class of practically solvable systems of difference equations of hyperbolic-cotangent-type, Electron. J. Qual. Theory Differ. Equ. 2020, Article No. 89, 25 (2020)
Stević, S.: On a class of solvable difference equations generalizing an iteration process for calculating reciprocals, Adv. Difference Equ. 2021, Article No. 205, 14 pages (2021)
Stević, S., Iričanin, B., Kosmala, W.: More on a hyperbolic-cotangent class of difference equations. Math. Methods Appl. Sci. 42, 2974–2992 (2019)
Stević, S., Iričanin, B., Kosmala, W., Šmarda, Z.: Note on theoretical and practical solvability of a class of discrete equations generalizing the hyperbolic-cotangent class, J. Inequal. Appl. 2021, Article No. 184, 12 (2021)
Stević, S., Iričanin, B., Šmarda, Z.: On a product-type system of difference equations of second order solvable in closed form, J. Inequal. Appl. 2015, Article No. 327, 15 (2015)
Stević, S., Iričanin, B., Šmarda, Z.: Solvability of a close to symmetric system of difference equations, Electron. J. Differential Equations 2016, Article No. 159, 13 (2016)
Vorobiev, N.N.: Fibonacci Numbers. Birkhäuser, Basel (2002)
Acknowledgements
Not applicable.
Funding
Not applicable.
Author information
Authors and Affiliations
Contributions
The author has contributed solely to the writing of this paper. He read and approved the manuscript.
Corresponding author
Ethics declarations
Competing interests
The authors declares that he has no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Stević, S. On a class of recursive relations for calculating square roots of numbers. J. Appl. Math. Comput. 69, 973–987 (2023). https://doi.org/10.1007/s12190-022-01780-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12190-022-01780-5