PropositionStatement: AI-generatedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Geometric growth, truncation and total decrement budgets

Statement

Let $q > 1$ and $b > 0$ . For every integer $k \geq 0$ , $\sum_{j = k}^{\infty} b q^{- j} = b q^{- k} q / (q - 1)$ .

Let $M > 0$ and let $(a_{j})_{j \geq 0}$ be a positive real sequence satisfying $a_{j + 1} \geq \min {q a_{j}, M}$ for every $j \geq 0$ . Reaching the cap means having $a_{j} \geq M$ ; the sequence may overshoot it. For every $j$ , $a_{j} \geq \min {q^{j} a_{0}, M}$ , and before the first cap crossing $a_{j} \geq q^{j} a_{0}$ . If $0 < a_{0} < M$ , the cap is reached in at most $⌈ \log (M / a_{0}) / \log q ⌉$ updates, where $⌈ x ⌉$ is the least integer at least $x$ . If $a_{0} \geq M$ , it is already reached.

A geometric stage beginning at an index $k$ is a consecutive finite or infinite collection of indices $j \geq k$ for which $a_{j} \geq a_{k} q^{j - k}$ . If nonnegative angle decrements $d_{j}$ on such a stage satisfy $d_{j} \leq b / a_{j}$ , their total is at most $b q / (a_{k} (q - 1))$ ; for an infinite stage the total denotes the convergent series of decrements.

Statement references

For |r| < 1, ∑_k ≥ 0 rᵏ = 1/(1-r), and for |r| ≥ 1 the series diverges

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

Integer part: for every real x there is exactly one integer m with m ≤ x < m + 1

The principle of mathematical induction

Laws of integer exponents

A nondecreasing sequence bounded above converges to the supremum of its range, and a nonincreasing sequence bounded below to the infimum

Sequences of reals: bounded, eventually, frequently, tails, subsequences

Integer powers aᵐ

Finite sums and finite products, by recursion

Series, partial sums, convergence and the sum, divergence, and the tail series

Facts & Assumptions

[F1]

For $∣ r ∣ < 1$ , the geometric series has sum $\sum_{h = 0}^{\infty} r^{h} = 1 / (1 - r)$ (For |r| < 1, ∑_k ≥ 0 rᵏ = 1/(1-r), and for |r| ≥ 1 the series diverges).

[F2]

The logarithm is strictly increasing on the positive reals, $\log 1 = 0$ , and $\log (x y) = \log x + \log y$ for positive $x, y$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[F3]

Every real $x$ has an integer part $m$ with $m \leq x < m + 1$ ; consequently the least integer at least $x$ exists (Integer part: for every real x there is exactly one integer m with m ≤ x < m + 1).

[F4]

A property of natural numbers holding at zero and preserved by the successor step holds for every natural number (The principle of mathematical induction).

[F5]

Integer powers of a nonzero real obey $q^{m + n} = q^{m} q^{n}$ and $q^{- m} = 1 / q^{m}$ ; in particular $q^{j + 1} = q^{j} q$ (Laws of integer exponents).

[F6]

Every nondecreasing real sequence bounded above converges to its supremum (A nondecreasing sequence bounded above converges to the supremum of its range, and a nonincreasing sequence bounded below to the infimum).

Proof

Given: The positive numbers $q - 1$ , $b$ , $M$ and the sequence $(a_{j})$ satisfy the stated hypotheses.

Goal: Establish the tail identity, growth and stopping bounds, and the decrement budget.

1.1givenF1F5algebra

Set $r = 1 / q$ , so $0 < r < 1$ . By the power laws, $q^{- (k + h)} = q^{- k} r^{h}$ . Factoring $b q^{- k}$ from the partial sums and applying the geometric-series formula gives $\sum_{j = k}^{\infty} b q^{- j} = b q^{- k} / (1 - 1 / q) = b q^{- k} q / (q - 1)$ .

1.2givenF4F5algebra

Induct on $j$ to show $a_{j} \geq \min {q^{j} a_{0}, M}$ . At $j = 0$ this is immediate. If it holds at $j$ , then $q a_{j} \geq \min {q^{j + 1} a_{0}, q M}$ ; since $q M > M$ , the recurrence yields $a_{j + 1} \geq \min {q^{j + 1} a_{0}, M}$ . Thus the claim holds for every $j$ . If $a_{j} < M$ , the minimum cannot equal $M$ , so $a_{j} \geq q^{j} a_{0}$ .

2.1givenF2F3F4F5step 1.2algebra

Suppose $a_{0} < M$ and set $x = \log (M / a_{0}) / \log q$ and $N = ⌈ x ⌉$ . Since $M / a_{0} > 1$ and $q > 1$ , strict logarithmic monotonicity gives $x > 0$ ; the integer-part property gives a finite positive integer $N \geq x$ . Repeated use of the logarithm product law gives $\log (q^{N}) = N \log q \geq \log (M / a_{0})$ , so strict monotonicity gives $q^{N} a_{0} \geq M$ . Step 1.2 then gives $a_{N} \geq M$ . If $a_{0} \geq M$ , the cap is reached at index zero.

3.1givenF5F6step 1.1algebra∎

On a geometric stage beginning at $k$ , positivity and the stage bound give $0 \leq d_{k + h} \leq (b / a_{k}) q^{- h}$ for each included index. Every finite partial total is therefore bounded above by the corresponding finite geometric sum, hence by $b q / (a_{k} (q - 1))$ from step 1.1 with $k = 0$ . For an infinite stage these partial totals are nondecreasing and bounded, so they converge by F6, and their limit has the same upper bound. This proves all the stated bounds.

Depends on

Used by · 9

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.