Proof of Iterated Powers, Factorials, and Convergence of the Series of Powers over Factorials

Each result cited below is universally quantified over the data in its own statement, and is applied to the data named in the step where it is cited. Every induction below is on a natural number and uses Natural Numbers. Throughout, $\iota$ denotes the canonical map of $\mathbb{N}$ into $\mathbb{R}$ of The Canonical Map from the Natural Numbers to a Field, and a natural number is identified with its image under $\iota$ wherever it occurs in a real expression. Transitivity of $\le$ on $\mathbb{R}$ is used freely below, and is licensed as follows: if $a\le b$ and $b\le c$ then $0\le b-a$ and $0\le c-b$ by claim 3 of Elementary Arithmetic in an Ordered Field, so $0\le(b-a)+(c-b)=c-a$ by claim 2 of that lemma, whence $a\le c$ by claim 3 again. Mixed transitivity on $\mathbb{R}$, in the form that $a<b$ and $b\le c$ imply $a<c$, is claim 2 of Elementary Order Arithmetic in an Ordered Field. Order relations between natural numbers are never transported to $\mathbb{R}$ except through $\iota$, as in Claim 3, Step 1.

Claim 1.

Step 1 (doubling). By clause 3 of Natural Numbers, $k\cdot 1=k$; by clause 4 of that definition and $2=S(1)$,

$$k\cdot 2=k\cdot S(1)=k\cdot 1+k=k+k .$$

By claim 6 of Properties of the Order on the Natural Numbers, applied with $m=k$ and $j=k$, we have $k<k+k$, that is, $k<2k$.

Step 2 (iterated powers). Fix $c\in\mathbb{R}$ and $m\in\mathbb{N}$, and induct on $n$. For $n=1$: by clause 3 of Natural Numbers we have $m\cdot 1=m$, and by claim 1 of Properties of Natural Number Powers in a Field we have $(c^{m})^{1}=c^{m}$, so $c^{\,m\cdot 1}=c^{m}=(c^{m})^{1}$. Assume $c^{\,m\cdot n}=(c^{m})^{n}$. By claim 1 of Properties of Natural Number Powers in a Field,

$$\bigl(c^{m}\bigr)^{S(n)}=\bigl(c^{m}\bigr)^{n}c^{m}=c^{\,m\cdot n}\,c^{m},$$

which equals $c^{\,m\cdot n+m}$ by Addition of Exponents for Natural Number Powers in a Field, applied with the exponents $m\cdot n$ and $m$; and $m\cdot n+m=m\cdot S(n)$ by clause 4 of Natural Numbers. Hence $(c^{m})^{S(n)}=c^{\,m\cdot S(n)}$, completing the induction.

Step 3 (absolute values). Fix $c\in\mathbb{R}$ and induct on $n$. For $n=1$, claim 1 of Properties of Natural Number Powers in a Field gives $|c^{1}|=|c|=|c|^{1}$. Assume $|c^{n}|=|c|^{n}$. Then, using claim 1 of Properties of Natural Number Powers in a Field twice and claim 4 of Properties of the Absolute Value in an Ordered Field,

$$\bigl|c^{S(n)}\bigr|=\bigl|c^{n}c\bigr|=\bigl|c^{n}\bigr|\,|c|=|c|^{n}\,|c|=|c|^{S(n)} .$$

Step 4 (the two consequences). Let $c\in\mathbb{R}$ and $n\in\mathbb{N}$. Since $-c=(-1)\,c$, claim 3 of Properties of Natural Number Powers in a Field gives $(-c)^{n}=(-1)^{n}c^{n}$. Applying that claim once more, together with claim 2 of the same lemma and $(-1)(-1)=1$,

$$\bigl((-1)^{n}\bigr)^{2}=(-1)^{n}(-1)^{n}=\bigl((-1)(-1)\bigr)^{n}=1^{n}=1 ,$$

the first equality by claim 1 of that lemma and $2=S(1)$. Hence, by Step 2 applied with $m=n$ and exponent $2$, and by claim 3 of Properties of Natural Number Powers in a Field,

$$(-c)^{2n}=(-c)^{\,n\cdot 2}=\bigl((-c)^{n}\bigr)^{2}=\bigl((-1)^{n}c^{n}\bigr)^{2}=\bigl((-1)^{n}\bigr)^{2}\bigl(c^{n}\bigr)^{2}=\bigl(c^{n}\bigr)^{2}=c^{\,n\cdot 2}=c^{2n} .$$

Finally, by claim 1 of Properties of Natural Number Powers in a Field,

$$(-c)^{2n+1}=(-c)^{S(2n)}=(-c)^{2n}(-c)=c^{2n}(-c)=-\bigl(c^{2n}c\bigr)=-c^{S(2n)}=-c^{2n+1}.$$

Claim 2.

Step 1 (positivity). We show $1\le k!$ by induction on $k$. For $k=1$, Finite Product Notation gives $1!=\prod_{i=1}^{1}i=1$. Let $k\in\mathbb{N}$ and assume $1\le k!$. By claim 4 of Properties of the Order on the Natural Numbers we have $1\le k$, so $S(1)\le S(k)$ by claim 6 of that lemma; since $S(1)=2$ this says $2\le S(k)$, and $S(k)-1=k$. Hence the second clause of Finite Product Notation applies and gives

$$S(k)!=\Bigl(\prod_{i=1}^{k}i\Bigr)\,S(k)=k!\;S(k).$$

By claim 2 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field we have $1\le\iota(S(k))$ as an inequality in $\mathbb{R}$. Two applications of claim 5 of Elementary Arithmetic in an Ordered Field — first to $1\le k!$ with the nonnegative factor $1$, then to $1\le\iota(S(k))$ with the nonnegative factor $k!$ — give

$$1=1\cdot 1\le k!\cdot 1\le k!\,\iota(S(k))=S(k)! ,$$

so $1\le S(k)!$ by transitivity of $\le$ on $\mathbb{R}$. This completes the induction. In particular $0<1\le k!$ by claim 6 of Elementary Order Arithmetic in an Ordered Field and mixed transitivity, so $k!$ is positive and, being a nonzero element of the field $\mathbb{R}$, has a multiplicative inverse.

Step 2 (monotonicity). Let $m,n\in\mathbb{N}$ with $m\le n$. By Order on the Natural Numbers either $m=n$, in which case $m!=n!$, or $m<n$, and in that case claim 7 of Properties of the Order on the Natural Numbers provides $p\in\mathbb{N}$ with $n=m+p$. In the latter case we induct on $p$. For $p=1$, $n=m+1=S(m)$ by claim 1 of Arithmetic of Addition on the Natural Numbers, and the displayed recursion of Step 1 gives $n!=m!\,\iota(S(m))$; since $1\le\iota(S(m))$ by claim 2 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field and $0\le m!$, claim 5 of Elementary Arithmetic in an Ordered Field gives $m!=m!\cdot 1\le m!\,\iota(S(m))=n!$. For the step, assume $m!\le (m+p)!$; then $m+S(p)=S(m+p)$ by clause 2 of Natural Numbers, and the same argument applied to $m+p$ in place of $m$ gives $(m+p)!\le S(m+p)!=(m+S(p))!$, so $m!\le (m+S(p))!$ by transitivity of $\le$ on $\mathbb{R}$, as licensed in the preamble.

Claim 3. Nonnegativity of the terms: $0\le A^{k}$ by claim 5 of Properties of Natural Number Powers in a Field, and $0<k!$ by Claim 2, so $0\le A^{k}/k!$ by claim 4 of Elementary Arithmetic in an Ordered Field and claim 5 of the same lemma.

Step 1 (the canonical map). We use Properties of the Canonical Map from the Natural Numbers to an Ordered Field throughout: by claim 3 of that lemma, $0<\iota(n)$ and $0<\iota(n)^{-1}$ for every $n\in\mathbb{N}$; by claim 2, $1\le\iota(n)$; and by claim 6, $m<n$ in $\mathbb{N}$ implies $\iota(m)<\iota(n)$ in $\mathbb{R}$.

Step 2 (a threshold). The number $2A=A+A$ is real, so claim 1 of The Archimedean Property of the Real Numbers provides $N\in\mathbb{N}$ with $2A<\iota(N)$.

Step 3 (one step of the descent). Let $m\in\mathbb{N}$ satisfy $2A\le\iota(S(m))$. Using claim 1 of Properties of Natural Number Powers in a Field for $A^{S(m)}=A^{m}A$ and for $2^{S(m)}=2^{m}\,2$, and the recursion $S(m)!=m!\,\iota(S(m))$ established in Claim 2, Step 1,

$$\frac{A^{S(m)}}{S(m)!}\,2^{S(m)}=\Bigl(\frac{A^{m}}{m!}\,2^{m}\Bigr)\cdot\frac{2A}{\iota(S(m))} .$$

By Step 1 the numbers $\iota(S(m))$ and $\iota(S(m))^{-1}$ are positive, and claim 5 of Elementary Arithmetic in an Ordered Field, applied to $2A\le\iota(S(m))$ and the nonnegative factor $\iota(S(m))^{-1}$, gives $2A\,\iota(S(m))^{-1}\le1$. The bracketed factor is nonnegative, as at the start of this claim, so a second application of claim 5 of Elementary Arithmetic in an Ordered Field yields

$$\frac{A^{S(m)}}{S(m)!}\,2^{S(m)}\le\frac{A^{m}}{m!}\,2^{m} .$$

Step 4 (a bound beyond the threshold). We show by induction on $p\in\mathbb{N}$ that

$$\iota(N)\le\iota(N+p) \qquad\text{and}\qquad \frac{A^{N+p}}{(N+p)!}\,2^{N+p}\le\frac{A^{N}}{N!}\,2^{N} .$$

For the first assertion, let $p\in\mathbb{N}$. By claim 6 of Properties of the Order on the Natural Numbers we have $N<N+p$, so $\iota(N)<\iota(N+p)$ by Step 1, hence $\iota(N)\le\iota(N+p)$. Combining with Step 2 by mixed transitivity, $2A<\iota(N+p)$, and therefore

$$2A\le\iota(N+p)\qquad\text{for every }p\in\mathbb{N}.$$

For the second assertion we induct on $p$. For $p=1$: by claim 1 of Arithmetic of Addition on the Natural Numbers, $N+1=S(N)$, and the display just obtained with $p=1$ reads $2A\le\iota(S(N))$, so Step 3 with $m=N$ gives the bound. Assume the bound for some $p\in\mathbb{N}$. By clause 2 of Natural Numbers, $N+S(p)=S(N+p)$, and the display with $S(p)$ in place of $p$ reads $2A\le\iota(S(N+p))$, so Step 3 with $m=N+p$ and then the induction hypothesis give

$$\frac{A^{N+S(p)}}{(N+S(p))!}\,2^{N+S(p)}\le\frac{A^{N+p}}{(N+p)!}\,2^{N+p}\le\frac{A^{N}}{N!}\,2^{N},$$

completing the induction.

Step 5 (a bound for every index). By Greatest Element of a Finite Family in a Totally Ordered Set, applied to the totally ordered set $\mathbb{R}$ and the $N$-tuple whose $k$-th component is $A^{k}\,2^{k}/k!$, there is $j\in[N]$ such that, writing $M=A^{j}2^{j}/j!$,

$$\frac{A^{k}}{k!}\,2^{k}\le M\qquad\text{for every }k\in[N] .$$

Since $N\in[N]$, in particular $A^{N}2^{N}/N!\le M$.

Let $k\in\mathbb{N}$. By claim 3 of Properties of the Order on the Natural Numbers exactly one of $k<N$, $k=N$, $N<k$ holds. In the first two cases $k\le N$ by claim 1 of that lemma, so $k\in[N]$ and $A^{k}2^{k}/k!\le M$. In the third case claim 7 of that lemma provides $p\in\mathbb{N}$ with $k=N+p$, and Step 4 together with $A^{N}2^{N}/N!\le M$ gives $A^{k}2^{k}/k!\le A^{N}2^{N}/N!\le M$. In every case

$$\frac{A^{k}}{k!}\,2^{k}\le M .$$

Step 6 (comparison with a geometric series). Since $2=\iota(2)$ is positive by Step 1, claim 7 of Elementary Order Arithmetic in an Ordered Field makes $2^{-1}$ positive, and claim 3 of Properties of Natural Number Powers in a Field together with claim 2 of that lemma gives $(2^{-1})^{k}2^{k}=(2^{-1}2)^{k}=1^{k}=1$; hence $(2^{-1})^{k}=(2^{k})^{-1}$. The number $(2^{-1})^{k}$ is nonnegative by claim 5 of Properties of Natural Number Powers in a Field, so multiplying the bound of Step 5 by it and using claim 5 of Elementary Arithmetic in an Ordered Field gives

$$0\le\frac{A^{k}}{k!}\le M\bigl(2^{-1}\bigr)^{k}\qquad\text{for every }k\in\mathbb{N}.$$

By claim 6 of Elementary Order Arithmetic in an Ordered Field and claim 8 of that lemma, $0\le 2^{-1}<1$, so the series $\sum_{k=1}^{\infty}(2^{-1})^{k}$ converges by Series of Nonnegative Real Numbers, Comparison, and the Geometric Series (iv); by Elementary Properties of Series of Real Numbers (i), applied with that sequence in both sequence slots and the scalar $M$, the series $\sum_{k=1}^{\infty}M(2^{-1})^{k}$ converges. The comparison test Series of Nonnegative Real Numbers, Comparison, and the Geometric Series (iii), applied to the sequences $(A^{k}/k!)_{k\in\mathbb{N}}$ and $(M(2^{-1})^{k})_{k\in\mathbb{N}}$, shows that $\sum_{k=1}^{\infty}A^{k}/k!$ converges.

Claim 4. Let $k\in\mathbb{N}$. By Claim 1 we have $A^{2k}=A^{\,k\cdot 2}=(A^{k})^{2}=A^{k}A^{k}$, using claim 1 of Properties of Natural Number Powers in a Field and $2=S(1)$ for the last equality, and $\bigl(A^{2}\bigr)^{k}=(A\,A)^{k}=A^{k}A^{k}$ by claim 3 of Properties of Natural Number Powers in a Field. Hence

$$A^{2k}=\bigl(A^{2}\bigr)^{k}.$$

By Claim 1 we have $k<2k$, hence $k\le 2k$ by claim 1 of Properties of the Order on the Natural Numbers, so $k!\le(2k)!$ by Claim 2; both are positive by Claim 2, so their inverses are positive by claim 7 of Elementary Order Arithmetic in an Ordered Field and the product $(k!)^{-1}(2k)!^{-1}$ of the two inverses is positive, hence nonnegative, by claim 5 of that lemma; multiplying $k!\le(2k)!$ by that product, using claim 5 of Elementary Arithmetic in an Ordered Field, gives $(2k)!^{-1}\le (k!)^{-1}$. Since $0\le A^{2k}$ by claim 5 of Properties of Natural Number Powers in a Field, claim 5 of Elementary Arithmetic in an Ordered Field gives

$$0\le\frac{A^{2k}}{(2k)!}\le\frac{A^{2k}}{k!}=\frac{(A^{2})^{k}}{k!} .$$

For the odd majorant, claim 1 of Properties of Natural Number Powers in a Field gives $A^{2k+1}=A^{S(2k)}=A^{2k}A$, and $2k<S(2k)=2k+1$ by claim 5 of Properties of the Order on the Natural Numbers, hence $2k\le2k+1$ by claim 1 of that lemma, so Claim 2 gives $k!\le(2k)!\le(2k+1)!$ and the same argument yields

$$0\le\frac{A^{2k+1}}{(2k+1)!}\le\frac{A^{2k}A}{k!}=A\cdot\frac{(A^{2})^{k}}{k!} .$$

Both dominating sequences are, up to the constant factors $1$ and $A$, the terms of $\sum_{k=1}^{\infty}(A^{2})^{k}/k!$, which converges by Claim 3 applied to the real number $A^{2}$ in place of $A$, this being nonnegative by claim 5 of Properties of Natural Number Powers in a Field; by Elementary Properties of Series of Real Numbers (i), applied with that sequence in both sequence slots and the scalar $A$, the series $\sum_{k=1}^{\infty}A\,(A^{2})^{k}/k!$ converges as well. Two applications of the comparison test Series of Nonnegative Real Numbers, Comparison, and the Geometric Series (iii) now give the convergence of $\sum_{k=1}^{\infty}A^{2k}/(2k)!$ and of $\sum_{k=1}^{\infty}A^{2k+1}/(2k+1)!$.