Math for Non-Geeks/How to prove convergence for recursive sequences

oben This article shows you how to prove convergence for recursively defined sequences, i.e. if only a recurrence and an initial value are given, and it is not known what explicitly looks like. The monotonicity criterion will turn out very useful for this. Problem setting We want to solve problems of the following kind: Let be a sequence defined by and for . Does it converge? If yes, what is its limit value? Applying the epsilon-criterion is complicated, here: it is not a priori known what elements with large indices look like (e.g. ), which makes it hard to guess a limit . It is even harder to give a bound for , as the explicit form of is often not known. Problem-solving strategies The article will cover two strategies for proving convergence of a recursively defined sequence: Finding the explicit form: You may try to find the explicit form of the sequence elements . Then it can be easier to determine a limit and prove convergence. Using the monotonicity criterion: If you can not find an explicit form, but you are convinced that the sequence should converge, you may try to use this criterion. It works without knowing an explicit form. Finding the explicit form One way to prove convergence is to try to find an explicit form for the sequence elements . It is useful to compute the first sequence elements in order to get a feeling of how the sequence behaves. In the above example: These elements are all smaller than 1, while slowly approaching it. We therefore conjecture that converges to 1. Let us try to find an explicit form, i.e. a map . That means, we are looking for a term with: The denominator suspiciously looks like a power of . The numerator seems to be always one less than the denominator: That would mean, . So we assert that Now, we should try to prove or disprove this assertion. Induction is a suitable way to do this, as the recursion relation may perfectly serve as an induction step. The induction starts with The induction step from to is done using the recursion relation: So we indeed proved . This explicit form allows us to use the usual tools (from the previous articles) for proving convergence. For instance, we know and we can use the limit theorems: Alternative way: using a telescoping sum Sometimes, finding a simple explicit form may be enormously hard or even impossible. In any case, one can write the elements using telescoping sums. To illustrate this, we consider: The difference between two sequence elements and is For , applying this step again yields So each time, we get an additional factor of . After steps, there will be This is not yet an explicit form for , but for the differences . However, we can express using telescoping sums: Substituting the formula for the differences gives a geometric sum This allows for an explicit expression Using and the limit theorems, we get Using the monotonicity criterion Step 1: Proving convergence What if we cannot find an explicit form of the sequence elements? If the sequence is monotonically increasing or decreasing, the monotonicity criterion can be useful. We recall this criterion: All bounded and monotone real sequences converge. Hence, it suffices to show boundedness and monotonicity of the sequence. For instance, returning to the initial example and : This seems to be monotonically increasing and bounded by . Monotonicity is proven inductively. Clearly , as The induction step from to consists of showing that the sequence element gets bigger within that step: This establishes monotonicity of the sequence. Boundedness by can also be shown inductively. Of course, which is smaller than 1. In the induction step, we need to show that if , then also : Hence, is bounded from above by . Now, the monotonicity criterion can be applied: The sequence is monotonically increasing and bounded from above, so it must converge. Step 2: finding the limit The convergence above can be used for finding the limit. By step 1, we already know that there must be a limit with and it can be at most the upper bound, namely 1. As the sequence elements approach 1 closer and closer, we assert that it is exactly 1. To verify this, we take a look at : So if there is any , it must fulfil . We resolve the equation for and get So is indeed the limit of the sequence . Question Above, we used that if is known, then there is also . Why is this the case? is the limit of the sequence . This is just a subsequence of , which contains all but the first element. Since each subsequence converges to the same limit as the original one, we have . Exercises Exercise 1 Finding the limit of a recursively defined sequence Let be recursively defined by: Prove that this sequence converges and compute the limit by finding an explicit form of the sequence using the monotonicity criterion There is So we assert that for all . The proof goes by induction on : For we have . So we have an explicit form. The limit theorems now directly yield the solution The lower-bound induction below proves for all , using only the recurrence and the initial value. This also shows that the recurrence is well-defined and all its denominators are positive. Using this fact, we show that is monotonically decreasing, i.e. for all . This is done by induction over : In addition, is bounded from below by , i.e. for all . This is also shown using induction: The monotonicity criterion then yields convergence of and there is . The lower bound implies , so the quotient rule applies. We can get the limit by taking the recursion relation and resolving it for : Hence, converges to . Exercise 2 Proving convergence of a recursively defined sequence We consider the following recursive sequence Prove that this sequence converges and determine the limit. What happens with , concerning convergence? There is Applying this step times, we get We use telescoping sums and obtain So we have an explicit form. With and the limit theorems, we get the limit For and we can plug in The next plugging-ins would exactly look the same, and we always get 1. So we assert that the sequence is constantly 1 and therefore converges to 1. We prove this assertion by induction on the pair of consecutive terms: We start with . The initial values give . Together with , this proves the induction claim. Hence, the sequence is constantly 1 and its limit is . Application: computing roots by Heron's method thumb|300px|The first sequence elements when computing starting at , or . thumb|300px|The sequence elements of Heron's method for when starting at . We will now come to an application, where convergence of a recursively defined sequence can be shown using the monotonicity criterion: Heron's method can be used to compute roots of positive integers, positive rational numbers or even positive real numbers . It recursively constructs a sequence of approximations for the root . From the first iterate onwards, these approximations get increasingly better, as shown by the following theorem: Heron's method Let be a real number with . Let the sequence be recursively defined by Then, converges to . Sequence elements of yield an increasingly precise approximation for , where we can get to an arbitrary precision . One can, for instance, use a computer to approximate up to an arbitrary precision, which is done by performing a sufficiently large number of recursion steps. In order to show that really converges to , we will show that: converges by the monotonicity criterion. The limit of is . We can not leave out the first step, as in step 2, we use that the sequence converges. A direct proof of convergence using the Epsilon-criterion (in one step) would be way more complicated. The sequence converges. Since , induction gives for all , so the recurrence is well-defined. We prove that the tail , starting at , is monotonically decreasing and bounded from below. The sequence is bounded from below. A bound is established using the inequality between arithmetic and geometric means: For there is . Hence, So for all . The full sequence is bounded from below by . The tail , starting at , is monotonically decreasing. This means, we need to show for , or equivalently, : So the tail , starting at , is bounded from below and monotonically decreasing. Hence, it converges by means of the monotonicity criterion. Adding the initial term does not change convergence. The limit of is . We will make use of a trick, here: As converges, there must be a limit , i.e. a real number with . Then, there is also , since is a subsequence of . The bound for implies , so the quotient rule applies. The recursion relation and the limit theorems yield: This can be resolved for and we get the limit: At this point, there are two candidates for the limit. But since , we also have so the convergence must be towards the positive limit candidate The initial value can be chosen to be any (strictly) positive real number. The proof of convergence works exactly the same way, since for every such initial value. Exercise Recursion for the third root Let with . Show that the sequence defined recursively for via converges to . Proceed as follows: ordered Use Bernoulli's inequality: For every with there is and use this to show by induction that for all Use step 1 to show: is monotonically decreasing and bounded from below. Determine the limit of . ordered First inequality: At first, Bernoulli's inequality can be applied to the last factor, as Set . Since , , so Bernoulli's inequality is strict here. Thus, with we get: Second inequality: Induction on : Induction basis: . holds by assumption. Induction step: . by the first inequality, since there is by the induction assumption. is monotonically decreasing: There is is bounded from below: Since we directly obtain As is monotonically decreasing and bounded from below, the monotonicity criterion implies its convergence. We denote the limit by . Since , the quotient rule applies. We plug this into the recursive relation and resolve for : We can even compute roots of higher order: For any natural number , as well as for real numbers and we can recursively construct a sequence with and show that it converges to . unten