Analysis proof planning: axioms, quantifiers and recursive sequences

Learning goals and axiomatic starting point

Plan epsilon arguments backward from a target error, track dependencies, and give a complete recursive-sequence proof rather than only solving a fixed-point equation. The real numbers are assumed to form an ordered field with completeness: field identities and inverses, a compatible total order, and a supremum for every nonempty bounded-above subset. The ordered-field laws alone do not imply completeness.

Completeness proves monotone bounded convergence. If $x_n$ is nondecreasing and bounded above, put $L=\sup\{x_n:n\ge1\}$. For every $\varepsilon>0$, supremum approximation gives an index $N$ with $L-\varepsilon<x_N\le L$. For all $n\ge N$, monotonicity gives $L-\varepsilon<x_n\le L$, so $x_n\to L$. The decreasing case follows by negating the sequence. This proof identifies exactly where completeness is used.

1. Error planning requires a buffer before a product

Suppose $u_n\to a$ and $v_n\to b$. To prove $u_nv_n\to ab$, split the error as

$$|u_nv_n-ab|\le |u_n|\,|v_n-b|+|b|\,|u_n-a|.$$

The first coefficient is not initially a fixed constant. First use convergence with tolerance one to choose $N_0$ such that $|u_n|\le|a|+1=:M$ for $n\ge N_0$. Now $M>0$ is independent of $n$.

Given an arbitrary $\varepsilon>0$, choose $N_1$ making $|v_n-b|<\varepsilon/(2M)$, and choose $N_2$ making $|u_n-a|<\varepsilon/[2(|b|+1)]$. For $n\ge\max(N_0,N_1,N_2)$, the displayed error is less than $\varepsilon/2+\varepsilon/2=\varepsilon$. The harmless $|b|+1$ avoids dividing by zero when $b=0$.

The dependency order is important: the fixed bound $M$ is chosen before error thresholds that depend on it; the final threshold depends on $\varepsilon$ but not on the eventual index $n$. A proof that chooses $N$ using the value of $u_n$ at the yet-uncontrolled index has reversed the quantifiers.

2. A recursive definition has five separate obligations

For a recurrence $x_{n+1}=F(x_n)$, check:

1. Well-definedness: all iterates remain in the domain of $F$.
2. Invariant information: a region or inequality remains true after an update.
3. Existence of a limit: for example, use monotone bounded convergence or a Cauchy estimate.
4. Identification: only after existence, pass to the limit using a valid continuity result.
5. Error: if approximation matters, derive a rate rather than just asserting convergence.

Solving $L=F(L)$ addresses only the fourth obligation, and even there it supplies candidates rather than a proof that any sequence approaches them. The recurrence $x_{n+1}=1-x_n$ with $x_0=0$ has a unique fixed point $1/2$, but its iterates alternate between zero and one. The fixed-point equation alone does not establish convergence.

3. Newton square-root iteration, from definition to limit

Let $A>0$ and $x_0>0$, and define

$$x_{n+1}=\frac12\left(x_n+\frac A{x_n}\right).$$

Let $\alpha>0$ be the unique positive real square root of $A$, whose existence follows independently from completeness or the intermediate value theorem. We do not assume the recurrence itself has already constructed that root.

Well-definedness. A positive input produces a positive output, so induction gives every $x_n>0$. All divisions are therefore legitimate.

Invariant bound. Direct algebra gives

$$x_{n+1}-\alpha=\frac{(x_n-\alpha)^2}{2x_n}\ge0.$$

Thus every iterate from $x_1$ onward is at least $\alpha$, even if $x_0<\alpha$. A statement that the entire sequence decreases from an arbitrary positive initial value would be false in that latter case.

Monotonicity after the first step. For $n\ge1$,

$$x_{n+1}-x_n=\frac{A-x_n^2}{2x_n}\le0,$$

because $x_n\ge\alpha$. Hence the tail is decreasing and bounded below by $\alpha$. Completeness gives a limit $L\ge\alpha>0$.

Identification. Reciprocal continuity at a nonzero point permits passage to the limit: $L=(L+A/L)/2$, so $L^2=A$. Positivity and uniqueness of the positive root give $L=\alpha$. Solving this equation was valid because convergence and the nonzero limiting denominator had already been established.

4. Derive both a rate and an exact transformed recurrence

Let $e_n=x_n-\alpha$ for $n\ge1$. The invariant identity gives

$$e_{n+1}=\frac{e_n^2}{2x_n}\le\frac{e_n^2}{2\alpha}, \qquad e_{n+1}\le\frac12e_n.$$

The second inequality follows from $e_n=x_n-\alpha<x_n$, and is non-strict when $e_n=0$. It gives an elementary geometric error estimate, while the first gives quadratic improvement once the error is small compared with $\alpha$.

There is also a revealing exact transform. For every $n\ge0$, set $r_n=(x_n-\alpha)/(x_n+\alpha)$, whose denominator is positive and whose magnitude is less than one. Algebra gives

$$x_{n+1}+\alpha=\frac{(x_n+\alpha)^2}{2x_n},\qquad r_{n+1}=r_n^2.$$

Thus $r_n=r_0^{2^n}$ and $x_n=\alpha(1+r_n)/(1-r_n)$. This supplies an independent convergence route and explains the rapidly increasing accuracy. It is not a practical formula for computing an unknown $\alpha$, because the transform itself uses $\alpha$; its role is proof and error analysis.

A certified example. For $A=2,x_0=1$, exact rational iteration gives $x_1=3/2$, $x_2=17/12$ and $x_3=577/408$. Since $(7/5)^2<2<(3/2)^2$, we have $0<e_1<1/10$ and $\alpha>1$. Therefore $e_2<1/200$ and $e_3<1/80000$. The rational interval $[577/408-1/80000,577/408]$ contains the positive square root of two. The error bound was proved from inequalities, not inferred from matching a decimal display.

5. A subsequence diagnostic with an essential hypothesis

If a bounded real sequence has only one possible subsequential limit $L$, then it converges to $L$. Suppose not. The negation of convergence supplies $\varepsilon_0>0$ and a subsequence whose distance from $L$ is always at least $\varepsilon_0$. Boundedness and Bolzano–Weierstrass give a convergent subsequence of that subsequence. Its limit is still at least $\varepsilon_0$ away by continuity of absolute value, contradicting uniqueness of the possible subsequential limit.

Boundedness matters. The sequence with even terms zero and odd terms $n$ has only zero as a finite subsequential limit, but does not converge: its odd terms are unbounded. Uniqueness of a finite cluster point does not by itself force all terms to stay near it.

Graded proof-planning tasks

1. Quantifier repair. Why is it invalid to choose a convergence threshold depending on the eventual index $n$? Rewrite the product-limit plan with a fixed preliminary bound and a threshold depending only on $\varepsilon$ and the given sequences.
2. Fixed-point diagnosis. Analyze $x_{n+1}=1-x_n$ for arbitrary real $x_0$. Determine exactly which initial value gives convergence and why the algebraic candidate alone is insufficient.
3. First-step exception. In the Newton iteration, if $0<x_0<\alpha$, prove the first step crosses to the other side of $\alpha$ and explain which monotonicity statement remains valid.
4. Error propagation. Suppose $\alpha\ge m>0$ and $0\le e_N\le\eta$. Give bounds for $e_{N+1}$ and $e_{N+2}$ using only $m,\eta$, and explain the distinction between absolute and relative accuracy.
5. Subsequence proof. Prove the bounded unique-subsequential-limit criterion and give the unbounded counterexample in explicit index notation.
6. Cauchy diagnosis. Show $x_n=\sqrt n$ has successive increments tending to zero but is not Cauchy. Explain why the Cauchy definition controls all pairs of sufficiently late terms rather than only neighbors.

Full solutions

1. The limit definition requires one $N$ that works for every $n\ge N$; an index-dependent threshold changes the quantifier order and may verify no common tail. First fix $N_0$ with $|u_n|\le|a|+1=M$. Given $\varepsilon$, use convergence to select thresholds for $|v_n-b|<\varepsilon/(2M)$ and $|u_n-a|<\varepsilon/[2(|b|+1)]$. Their maximum with $N_0$ is independent of the eventual $n$ and bounds the full product error.
2. The even iterates equal $x_0$ and the odd iterates equal $1-x_0$. They converge exactly when these two values agree, namely $x_0=1/2$, in which case the sequence is constant. Otherwise the two constant subsequences have different limits. The fixed-point equation identifies the only possible limit, not the behavior of arbitrary iterates.
3. The identity $x_1-\alpha=(x_0-\alpha)^2/(2x_0)$ is strictly positive when $x_0\ne\alpha$, so $x_1>\alpha$ despite $x_0<\alpha$. The sequence cannot be decreasing starting at index zero. From index one onward it is decreasing and bounded below by $\alpha$, as the separate invariant and difference calculations prove.
4. The quadratic error identity gives $e_{N+1}\le\eta^2/(2m)$ and then $e_{N+2}\le\eta^4/(8m^3)$. These bound errors in the same units as the root. Relative error divides by $\alpha$; its magnitude is at most the corresponding absolute bound divided by $m$, but the actual denominator is $\alpha$. A number of decimal digits is not established until a numerical error bound has been compared with a specified rounding tolerance.
5. Failure of convergence yields an infinite subsequence staying at least $\varepsilon_0$ away. Boundedness supplies a convergent subsubsequence; its limit remains separated and contradicts the unique possible limit. For the counterexample define $x_{2k}=0$ and $x_{2k-1}=2k-1$. Any convergent subsequence can include only finitely many odd indices, since those values tend to infinity, so its limit is zero. Yet the whole sequence is unbounded and nonconvergent.
6. Rationalizing gives $\sqrt{n+1}-\sqrt n=1/(\sqrt{n+1}+\sqrt n)\to0$. But for indices $n$ and $4n$, their difference is $\sqrt{4n}-\sqrt n=\sqrt n$, arbitrarily large beyond every proposed tail threshold. Taking a fixed tolerance one therefore disproves the Cauchy condition. Small neighboring changes can accumulate over many steps; the Cauchy requirement rules out that accumulation across every late pair.

Summary and terms

An invariant survives every iteration. A fixed point is only a candidate limit until convergence is proved. A buffer bound turns a varying coefficient into a fixed constant before an epsilon choice. A subsequential limit is a limit of some extracted subsequence, and boundedness supplies such limits through completeness. A rigorous approximation argument establishes valid iterates, invariant control, existence, identification and error as separate obligations.