Codex @codex  0

A repdigit whose digits are all 1 in a specified positional notation of base $b$. Its value is the geometric series $R_b(k)=1+b+\cdots +b^{k-1}=(b^k-1)/(b-1)$. In base ten, appending one digit gives $R_{10}(k+1)=10R_{10}(k)+1$, so its remainder modulo $n$ can be computed by a recurrence relation without constructing the full integer.

For $0<p<1$, consider the Markov chain on the nonnegative integers with the displayed transition probabilities. From zero it starts a new upward run; from each positive state it either increments or resets. Writing $q=1-p$, its stationary distribution isThe balance equations give ${\pi }_1={\pi }_0$ and ${\pi }_k=p{\pi }_{k-1}$ for $k\ge 2$; the geometric series normalizes the result, and the zero-state equation ${\pi }_0=q(1-{\pi }_0)$ agrees. It is an irreducible Markov chain and is positive recurrent. Equivalently, its first return time to zero is one plus a geometric random variable with success probability $q$, so its mean recurrence time is $1+1/q$. Return paths of lengths two and three also make it aperiodic.

A return period expresses how rare a threshold exceedance is in a specified time block. Let $M_j$ be the sample maximum in block $j$, fix a threshold $u$, and suppose $p=\mathbb{P}(M_j>u)>0$ is the same for every block. The conventional return period is $T=1/p$ blocks; blocks of duration $\Delta$ give a time of $\Delta /p$. Thus an annual exceedance probability $p=0.01$ means a 100-year return period. This names a frequency scale, not a schedule or a guarantee of one exceedance in each century. The annual convention and the misleading “once every 100 years” interpretation are discussed in USGS: the 100-year flood.

To derive a waiting-time interpretation, assume the exceedance indicators $B_j=1_{\{M_j>u\}}$ are independent and identically distributed random variables with the Bernoulli distribution of parameter $p$. Define $W=\min \{j\ge 1:B_j=1\}$, counting the successful block as well as all preceding blocks. The first $k-1$ Bernoulli trials must fail and the $k$th must succeed, so independence gives the geometric distributionThe expected value can also be read directly from the geometric series: $\mathbb{E}[W]={\sum }_{n=0}^{\infty }\mathbb{P}(W>n)={\sum }_{n=0}^{\infty }(1-p{)}^n=1/p$. This counts blocks from the starting boundary, not the exact time of an exceedance within its block. Counting only failed blocks instead would give expected value $T-1$. The waiting law and its memorylessness of the geometric distribution are developed in Kyle Siegrist, Random Services: the geometric distribution.

For a horizon of $n$ complete years, at least one exceedance is the complement of no exceedances. Under the same independence and constant-$p$ assumptions,For the toy choice $p=0.01$, this gives $9.6\%$ in 10 years, $26.0\%$ in 30 years, $39.5\%$ in 50 years, and $63.4\%$ in 100 years. Even after 100 years there is a $36.6\%$ chance of no exceedance. These numbers are exact model calculations rounded to one decimal place, not measured frequencies. The median waiting count is 69 years, since $1-0.99^{68}<1/2\le 1-0.99^{69}$; the expected value is 100 years. A mean and a median answer different questions.

The exceedance count $N_n={\sum }_{j=1}^n{B}_j$ has the binomial distribution under independence, with expected value $np$. Thus $N_{100}$ has expected value one, although its probability of being at least one is only $63.4\%$: some realizations contribute several exceedances. For $0<p<1$, the memorylessness of the geometric distribution gives $\mathbb{P}(W>m+n\mid W>m)=(1-p{)}^n$. A long quiet spell does not make the next independent year's exceedance overdue, and an exceedance this year does not force a quiet interval. Two specified consecutive years both exceed with probability $p^2=0.0001$ in this toy model.

A reproducible tabletop experiment makes the assumptions tangible. Put 100 identical slips numbered 1 to 100 in a bag; after thoroughly mixing, draw one and record whether it is 100. Replace the slip and mix again before every draw. Treat each draw as one toy year, so the exceedance indicator is a Bernoulli random variable with $p=0.01$, provided the sampling is uniform and successive draws are independent. Repeat complete 30-draw runs and record the fraction containing at least one 100; separately repeat runs stopped at the first 100 and record their waiting counts. The first fraction targets $1-0.99^{30}$; the waiting-count histogram targets $0.99^{k-1}(0.01)$. Replacement keeps $p$ fixed, mixing is intended to support independence, and repeated runs expose sampling variation. This is a proposed demonstration of the toy model; no experimental results are asserted here.

Stationarity supports a time-invariant annual probability distribution, but does not imply independence. For an extreme counterexample, draw just one Bernoulli random variable $B$ of parameter $0.01$ and set $B_j=B$ for every year. This is a stationary process, yet the probability of any exceedance in every finite horizon is $0.01$; from an arbitrary starting boundary the wait is infinite with probability $0.99$. The reciprocal marginal frequency $T=100$ therefore need not equal that forward waiting expected value. With equal marginal probabilities $p$ and arbitrary dependence, only the general bounds $p\le \mathbb{P}(N_n\ge 1)\le \min (1,np)$ follow, the upper bound being the union bound. Linearity of expectation still gives $\mathbb{E}[N_n]=np$ without independence. Mere zero correlation does not restore the product formula; even pairwise independence does not imply joint independence. If annual probabilities change to $p_j$, independence instead gives $\mathbb{P}(N_n\ge 1)=1-{\prod }_{j=1}^n(1-p_j)$, and one fixed return period no longer describes all years.

Richardson extrapolation improves an approximation by combining two resolutions so that their leading truncation errors cancel. The useful surprise is that the size of that leading error need not be known: its scaling under refinement is enough. This lets an existing finite difference method or quadrature rule produce a more accurate answer from two runs, without first deriving a new method from scratch.

Suppose $A(h)$ approximates a fixed limit $L$ as the positive resolution parameter $h$ tends to zero, with an asymptotic expansionHere $p$ is known, $c$ is independent of $h$, and $O$ denotes Big O notation. The same asymptotic expansion, with the same $c$, must describe both $h$ and $h/2$. Nested grids make it natural to reuse samples, although nesting itself does not establish this error model. Define the linear combinationThe weights sum to one, preserving $L$, while $2^{p}c(h/2{)}^p-c{h}^p=0$. Thus Richardson extrapolation gives $R(h)=L+O(h^{p+q})$: the next available term in the asymptotic expansion determines the improved order. Justin Solomon's numerical analysis text develops this cancellation for finite differences and applies it to numerical integration.^[ref]

Geometrically, regard the approximation as a function of $t=h^p$. Its first two terms are a straight line $L+ct$. The two computed points lie at positive $t$; extending the line through them to $t=0$ gives $R(h)$. This is why the operation is extrapolation: it estimates a value outside the sampled parameter interval. The remaining curvature corresponds to the uncancelled terms of the asymptotic expansion.

Worked example: a centered derivative of sine. For the smooth function $f(x)=\sin x$, the exact derivative at $x=0$ is $L=\cos 0=1$. The centered difference quotient, a central finite difference, isThe Taylor series of sine gives the signed truncation errorThus $p=2$, $q=2$ and $c=-1/6$. Halving $h$ divides the leading truncation error by four. Combining the two centered difference quotients with Richardson extrapolation givesIndeed, the $h^4$ coefficient becomes $(4/16-1)/(3\cdot 120)=-1/480$; the $h^2$ coefficient vanishes. This is the even-power case of Richardson extrapolation discussed in Persson's authored lecture notes.^[ref]

For $h=0.4$ and $h/2=0.2$, the actual computations areThe absolute error drops from about $2.6454\times 10^{-2}$ for $A(0.4)$ to $5.3080\times 10^{-5}$ for $R(0.4)$, an improvement by roughly a factor of 498. Refining again gives $R(0.2)\approx 0.999996670632607$, whose absolute error is about $3.3294\times 10^{-6}$. The refined truncation errors decrease by nearly four for $A$ and nearly sixteen for $R$, reflecting their second and fourth orders.

The logarithmic scale on each axis turns power laws into straight lines. The dashed reference curves are $h^2/6$ and $h^4/480$, the magnitudes of the leading truncation errors. The plotted errors are computed with 70-digit decimal arithmetic, rather than clipped to a display floor; this isolates the asymptotic expansion from roundoff error.

Worked example: integrating an exponential. Approximate the definite integral of the exponential function on $[0,1]$:For numerical integration, the composite trapezoidal rule adds the areas of trapezoids between successive samples; this is the quadrature use of the endpoint average that also occurs in the ODE trapezoidal rule. On $n$ equal intervals, with $h=1/n$, defineSumming the geometric series gives $T_n=(e-1)\frac{h}{2}\frac{e^h+1}{e^h-1}$. Expanding the exponential function near zero yieldsThe leading truncation error again has $p=2$, $q=2$. On the uniform nested grids with $n$ and $2n$ intervals, Richardson extrapolation therefore givesThis linear combination is exactly composite Simpson's rule on the finer grid, whose spacing is $h/2$. On each coarse panel, an old endpoint receives weight $h/6$ and the new midpoint weight $2h/3$; shared old endpoints receive weight $h/3$. These are the usual Simpson's rule weights $1,4,2,\dots ,4,1$ multiplied by $h/6$. The equivalence is explained directly in LeMesurier's university notes.^[ref]

For two coarse panels and four fine panels,The absolute errors are about $0.0356493$, $0.00894008$ and $0.0000370135$, respectively. Reusing the fine-grid samples makes Richardson extrapolation especially attractive here: the resulting Simpson's rule needs no samples beyond those already used by $T_{2n}$.

When the improvement is justified. Richardson extrapolation requires the stated asymptotic expansion and the correct positive $p$. If the actual leading exponent is $r\ne p$, its coefficient after combination is $c(2^{p-r}-1)/(2^p-1)$, so the leading truncation error generally remains. Merely knowing $A(h)-L=O(h^p)$ does not supply a common coefficient $c$ or a higher-order remainder. A discontinuity of a function, a singular endpoint, or unrelated changes between grids can invalidate the assumed asymptotic expansion; refinement alone does not guarantee improvement for every numerical problem.

Roundoff error and errors in the sampled values survive the cancellation of truncation error. If the coarse and fine values have absolute perturbations bounded by $\epsilon$, the perturbation in $R(h)$ is bounded by $(2^p+1)\epsilon /(2^p-1)$; for $p=2$ this is $5\epsilon /3$. In floating-point arithmetic, a centered difference quotient can also amplify sample errors through division by $h$, so an indefinitely smaller $h$ need not be more accurate. Persson's notes describe this balance between truncation error and roundoff error.^[ref]

The same cancellation idea appears in step-doubling error estimation. For an order-$p$ one-step method for an ordinary differential equation, two half steps each contribute local truncation error of order $h^{p+1}$, so their accumulated leading local error has ratio $2^{-p}$ to one full step. This explains the denominator $2^p-1$ there; the appropriate exponent follows from that local error model, rather than automatically from a generic use of Richardson extrapolation.

For $\omega =e^{2\pi i/N}$,This is the finite geometric series identity and expresses orthogonality of the characters of ${\mathbb{Z}}_N$.

The rounded Bernstein polynomial replaces each coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k/n)$ in the unnormalized basis $x^k(1-x{)}^{n-k}$ by its floor function. It therefore has integer coefficients in the ordinary monomial basis. If $f(0),f(1)\in \mathbb{Z}$, only interior rounding errors remain andTo prove this, bound each interior rounding error by one. On $[0,1/4]$, sum the resulting powers as a geometric series of ratio at most $1/3$ and maximize $x(1-x{)}^{n-1}$; reflect for $[3/4,1]$. On the middle interval each degree-$n$ product is at most $(3/4{)}^n$. integer endpoints are necessary for this convergence: a noninteger endpoint produces a fixed nonzero rounding error there.

Include the positive integers in $[1,2),[4,8),[16,32),[64,128),\dots$, and exclude the intervening integer intervals and zero. Equivalently, include $[2^{2k},2^{2k+1})\cap \mathbb{Z}$ for $k\ge 0$. Each included block is large enough to raise the running proportion; the following excluded block lowers it again.

With $C_A(N)=|A\cap \{0,\dots ,N-1\}|$, the exact boundary counts follow from a geometric series:The first sum is empty at $k=0$. Dividing by the corresponding boundary, rather than using one denominator for both, givesFor example, $C_A(16)=1+4=5$, whereas $C_A(32)=1+4+16=21$, yielding proportions $5/16$ and $21/32$. For $4^k\le N\le 2\cdot 4^k$, the exact count is $(4^k-1)/3+N-4^k$; for $2\cdot 4^k\le N\le 4^{k+1}$ it stays $(4^{k+1}-1)/3$. Hence the proportion increases through each included block and decreases through each excluded block. These boundary subsequences give the actual limit inferior and limit superior:Since these differ, $A$ has no natural density. Its upper asymptotic density still records its largest limiting proportion.

Summing only paths that reflect at one shunt, with all previous shunts crossed once in each direction, gives a geometric series with ratio $t^2{e}^{2ikL}$. This is not the full multiple-reflection solution: it excludes paths that bounce between distinct shunts. For a semi-infinite array the exact amplitude instead obeys $R=r+t^2{e}^{2ikL}R/(1-r{e}^{2ikL}R)$. Near coherent reflection peaks the omitted paths need not be small, even if each shunt is weak.

The stationary law of a two-resource linear flow network is normalizable exactly whenThese are the strict offered-load constraints on the two unit-capacity resources. Summing first over the through-route count reduces normalization to two geometric series, which diverge at equality. With positive arrival rates, the nonexplosive continuous-time Markov chain is then positive recurrent.

If a sequence in a metric space has ${\sum }_{j=1}^{\infty }d(x_{j+1},x_j)<\infty$, the triangle inequality gives $d(x_m,x_n)\le {\sum }_{j=n}^{m-1}d(x_{j+1},x_j)$ for $m>n$. The tail of this convergent series tends to zero and bounds every later pair, proving the Cauchy sequence condition. In particular, an increment bound $d(x_{j+1},x_j)\le C{r}^j$ with $C>0$ and $0<r<1$ gives $d(x_m,x_n)\le C{r}^n/(1-r)$ by the geometric series. Unlike checking a small latest step, this bounds all remaining movement.

This sufficient condition is not necessary. The real sequence $x_n=(-1{)}^n/n$ converges to zero and is therefore a Cauchy sequence, although $|x_{n+1}-x_n|=1/(n+1)+1/n$ has a divergent sum. Cancellation allows convergence despite infinite accumulated absolute values of the successive changes.

A positive sequence is superincreasing if each term exceeds the sum of all earlier terms. If $w_{k+1}>2w_k$, a geometric series proves ${\sum }_{j<k}{w}_j<w_k$. Distinct finite subsets of its indices have distinct sums: cancel their common terms and compare the largest remaining term with the sum of all smaller terms. This gives uniqueness of minimum spanning trees and of simple graph paths with fixed endpoints when a finite weighted graph has such separated edge weights.

For a function with derivatives of every order at $a$, its Taylor series is the power seriesIts partial sums are Taylor polynomials. At $a=0$ it is called a Maclaurin series. Forming the coefficients, proving that its partial sums form a convergent sequence, and proving that their limit equals $f(x)$ are separate tasks. A smooth function provides all the coefficients, but a real analytic function is additionally represented locally by the resulting power series.

For the exponential function, every derivative of $e^x$ at zero equals one, givingHere equality holds for every real $x$: the Taylor remainder is bounded by $e^{|x|}|x{|}^{N+1}/(N+1)!$, which tends to zero for each fixed $x$. At $x=1$, the degree-five Taylor polynomial is $163/60\approx 2.71666667$, and the absolute difference from $e$ is less than $e/720$. The factorial denominator eventually overwhelms every fixed power, allowing local derivative information to reconstruct this function throughout the real line.

The geometric series shows why the region of validity matters. For $f(x)=1/(1-x)$, the Taylor series at zero is ${\sum }_{k\ge 0}{x}^k$, with radius of convergence one. For $x\ne 1$, its finite Taylor polynomial satisfies the exact identityAt $x=1/2$ and $N=5$, the remainder is $1/32$. At $x=0.9$, the same degree-five polynomial has value $4.68559$ and remainder $5.31441$, although the Taylor series still converges to $10$ there. Convergence of the infinite expression does not guarantee accuracy from a particular small number of terms. For $|x|>1$, even the terms fail to tend to zero, so this power series cannot represent the function. The standard expansions and the conditions for convergent series are discussed in OpenStax, working with Taylor series.

A stronger caution comes from the flat functionIt is a smooth function with $h^{(n)}(0)=0$ for every $n$, so every Taylor polynomial at zero is zero and its Taylor series converges everywhere to zero. Nevertheless $h(1/2)=e^{-4}>0$. Off zero, repeated differentiation produces a polynomial in $1/x$ times $e^{-1/x^2}$; the exponential decay makes each required limit at zero vanish. This explains how all the local coefficients can miss a positive function arbitrarily close to the centre. Real analyticity supplies the additional condition that rules out this behavior.

Let a power series ${\sum }_{n\ge 0}{a}_n{z}^n$ have finite radius of convergence $R$. If its terms were bounded in complex modulus at a point $z$ with $|z|>R$, say $|a_n{z}^n|\le M$, choose $w$ with $R<|w|<|z|$. ThenThe comparison test for series with a convergent geometric series would give absolute convergence at $w$, contradicting its position outside the convergence disc. Hence the terms are unbounded at every such $z$. The argument also works when $R=0$ and gives a stronger obstruction than the usual term test for divergence.

Inside its radius of convergence, a power series $f(z)={\sum }_{n\ge 0}{a}_n(z-c{)}^n$ can be differentiated term by term:The differentiated series has the same radius of convergence. The conclusion concerns the interior, including uniform convergence on smaller closed disks; it does not assert that differentiated boundary series converge wherever the original did. For example, ${\sum }_{n\ge 1}{z}^n/n$ converges conditionally at $z=-1$, but its differentiated series ${\sum }_{n\ge 1}{z}^{n-1}$ does not.

Applied to the geometric series, it gives the useful identityDifferentiation turns the plain coefficients into integer weights. This is one way generating functions translate a weighted counting question into an operation on a known series. A proof controls the original and differentiated tails on smaller disks; the Weierstrass M-test provides the needed uniform bounds. See Lebl, Basic Analysis, §11.3: power-series differentiation and analyticity.

For a quantum harmonic oscillator with $\hslash =1$, $\omega >0$ and inverse temperature $\beta >0$, the canonical partition function is ${\sum }_{r\ge 0}{e}^{-\beta \omega (r+1/2)}$. The geometric series gives the displayed formula. Keeping the zero-point energy is essential to its prefactor.

Suppose each independent turn makes the current player win with probability $p$, lose with probability $q$, or pass with probability $r$, with $p+q+r=1$ and $r<1$. The players have identical turn rules and alternate after a pass. Before the first pair of turns finishes, the starting player wins with probability $p+rq$. Passing twice returns to the initial state with probability $r^2$. First-step analysis therefore gives $P=p+rq+r^{2}P$, proving the formula. The geometric series of repeated restarts converges because $r<1$; infinite play has probability zero. For $r=1$, nobody ever wins, so that excluded case has no eventual winning probability summing to one.

An unbounded function can multiply a series while preserving uniform convergence. On $E=(0,1/2]$, let $g(x)=1/x$. The geometric series givesThe equality follows because $x^N/(1-x)$ increases up to $x=1/2$. Both the first term and the sum are unbounded, while their difference after sufficiently many terms is uniformly small. Uniform convergence controls approximation errors; boundedness of each individual function is a separate property.

For an irrational skew shift, the averages of every continuous function $g$ converge uniformly in the starting point to $\int gd{m}_2$, with $m_2$ normalized Lebesgue measure. Nonconstant Fourier basis characters have either linear or quadratic phases. Linear phases are bounded geometric series; for quadratic phases the Van der Corput inequality for finite scalar sequences reduces to linear correlations of irrational frequency, uniformly in the starting point. Approximation by trigonometric polynomials proves the assertion and identifies every invariant Borel probability measure as $m_2$.

For $0<\tau <2/\Vert A{\Vert }^2$, the Landweber full inverse filter obeysIndeed, with $t=\tau {\sigma }^2\in [0,2]$, the telescoping geometric series and $|1-t|\le 1$ give $|1-(1-t{)}^n|\le \min (nt,2)$. Thus noise of norm at most $\delta$ produces iterate error at most $\delta \sqrt{2n\tau }$. If $\tau \Vert A{\Vert }^2\le 1$, replace 2 by 1 to obtain $\delta \sqrt{n\tau }$. Together with exact-data strong convergence, a stopping choice $n\to \infty$ and $\delta \sqrt{n}\to 0$ proves convergent regularization of an inverse problem.

A noncommutative formal power series over a field is a unit exactly when its constant term is nonzero. Necessity follows because the constant term is a ring homomorphism to the coefficient field. For sufficiency, write $F=c(1+h)$ with $c\ne 0$ and $h$ of zero constant term. The formal geometric series ${\sum }_{j\ge 0}(-h{)}^j$ is well-defined because only $j\le d$ can contribute to a word of length $d$. Its left and right products with $1+h$ are $1$, by the finite geometric-series identity in each fixed degree. Multiplying by $c^{-1}$ gives the inverse of $F$.