avewright/proofwiki-math huggingface dataset:
Theorem: Hero's Method

Let $a \in \R$ be a real number such that $a > 0$.
Let $x_1 \in \R$ be a real number such that $x_1 > 0$.
Let $\sequence {x_n}$ be the sequence in $\R$ defined recursively by:
:$\forall n \in \N_{>0}: x_{n + 1} = \dfrac {x_n + \dfrac a {x_n} } 2$
Then $x_n \to \sqrt a$ as $n \to \infty$.

Proof:
Consider $x_n - x_{n + 1}$.
{{begin-eqn}}
{{eqn | l = x_n - x_{n + 1}
      | r = x_n - \frac {x_n + \dfrac a {x_n} } 2
      | c = 
}}
{{eqn | r = \frac 1 {2 x_n} \paren {x_n^2 - a}
      | c = 
}}
{{eqn | o = \ge
      | r = 0
      | c = for $n \ge 2$
      | cc= Lemma 2
}}
{{end-eqn}}
So, providing we ignore the first term (about which we can state nothing), the sequence $\sequence {x_n}$ is decreasing and bounded below by $\sqrt a$.
Thus by the Monotone Convergence Theorem (Real Analysis), $x_n \to l$ as $n \to \infty$, where $l \ge \sqrt a$.
Now we want to find exactly what that value of $l$ actually is.
By Limit of Subsequence equals Limit of Real Sequence we also have $x_{n + 1} \to l$ as $n \to \infty$.
But $x_{n + 1} = \dfrac {x_n + \dfrac a {x_n} } 2$.
Because $l \ge \sqrt a$ it follows that $l \ne 0$.
So by the Combination Theorem for Sequences:
:$x_{n + 1} = \dfrac {x_n + \dfrac a {x_n} } 2 \to \dfrac {l + \dfrac a l} 2$ as $n \to \infty$
Since a Convergent Real Sequence has Unique Limit, that means:
:$l = \dfrac {l + \dfrac a l} 2$
and so (after some straightforward algebra):
:$l^2 = a$
Thus:
:$l = \pm \sqrt a$
and as $l \ge +\sqrt a$ it follows that:
:$l = +\sqrt a$
Hence the result.
{{Qed}}
Theorem: Hero's Method

Let $a \in \R$ be a real number such that $a > 0$.
Let $x_1 \in \R$ be a real number such that $x_1 > 0$.
Let $\sequence {x_n}$ be the sequence in $\R$ defined recursively by:
:$\forall n \in \N_{>0}: x_{n + 1} = \dfrac {x_n + \dfrac a {x_n} } 2$
Then $x_n \to \sqrt a$ as $n \to \infty$.

Proof:
Let $a > 0$.
We make no statement about $x_1$.
We specify that:
:$x_{n + 1} = \dfrac {x_n + \dfrac a {x_n} } 2$
Now:
{{begin-eqn}}
{{eqn | l = x_{n + 1} - \sqrt a
      | r = \frac {x_n + \dfrac a {x_n} } 2 - \sqrt a
      | c = 
}}
{{eqn | r = \frac 1 {2 x_n} \paren {x_n^2 - 2 x_n \sqrt a + a}
      | c = 
}}
{{eqn | r = \frac 1 {2 x_n} \paren {x_n - \sqrt a}^2
      | c = 
}}
{{eqn | r = \frac 1 {2 x_n} \paren {\dfrac {\paren {x_{n - 1} - \sqrt a}^2} {2 x_{n - 1} } }^2
      | c = 
}}
{{eqn | r = \frac 1 {2 x_n} \frac 1 {\paren {2 x_{n - 1} }^2} \paren {x_{n - 1} - \sqrt a}^4
      | c = 
}}
{{eqn | r = \frac 1 {2 x_n} \frac 1 {\paren {2 x_{n - 1} }^2} \frac 1 {\paren {2 x_{n - 2} }^4} \paren {x_{n - 2} - \sqrt a}^8
      | c = 
}}
{{eqn | r = \frac 1 {2 x_n} \frac 1 {\paren {2 x_{n - 1} }^2} \cdots \frac 1 {\paren {2 x_1}^{2 n - 1} } \paren {x_1 - \sqrt a}^{2 n}
      | c = 
}}
{{end-eqn}}
If we now assume that $x_1 \ge \sqrt a$, then it follows from Lemma 2 that $x_n \ge \sqrt a$.
So:
{{begin-eqn}}
{{eqn | l = \size {x_{n + 1} - \sqrt a}
      | o = \le
      | r = \paren {\frac 1 {2 \sqrt a} }^{1 + 2 + 2^2 + \cdots + 2^{n - 1} } \paren {x_1 - \sqrt a}^{2 n}
      | c = 
}}
{{eqn | r = \paren {\frac 1 {2 \sqrt a} }^{\dfrac {2^n - 1} {2 - 1} } \paren {x_1 - \sqrt a}^{2 n}
      | c = 
}}
{{eqn | r = 2 \sqrt a \paren {\frac {x_1 - \sqrt a} {2 \sqrt a} }^{2 n}
      | c = 
}}
{{end-eqn}}
If $\size y < 1$, then $y^n \to 0$ as $n \to \infty$ from Sequence of Powers of Number less than One.
So, by Limit of Subsequence equals Limit of Real Sequence:
:$y^{2^n} \to 0$ as $n \to \infty$
Thus we see that:
:$x_n \to \sqrt a$ as $n \to \infty$
provided that:
:$\dfrac {x_1 - \sqrt a} {2 \sqrt a} < 1$
that is, that:
:$\sqrt a \le x_1 < 3 \sqrt a$
We assumed above that $x_1 \ge \sqrt a$.
Now we have shown that $x_n \to \sqrt a$ as $n \to \infty$ provided that $\sqrt a \le x_1 < 3 \sqrt a$.
However, we have already shown that $x_n \to \sqrt a$ as long as $x_1 \ge 0$.
The advantage to this analysis is that this gives us an opportunity to determine how close $x_n$ gets to $\sqrt a$.
{{Qed}}
Theorem: Limit of Integer to Reciprocal Power

Let $\sequence {x_n}$ be the real sequence defined as $x_n = n^{1/n}$, using exponentiation.
Then $\sequence {x_n}$ converges with a limit of $1$.

Proof:
From Number to Reciprocal Power is Decreasing we have that the real sequence $\sequence {n^{1/n} }$ is decreasing for $n \ge 3$.
Now, as $n^{1 / n} > 0$ for all positive $n$, it follows that $\sequence {n^{1 / n} }$ is bounded below (by $0$, for a start).
Thus the subsequence of $\sequence {n^{1 / n} }$ consisting of all the terms of $\sequence {n^{1 / n} }$ where $n \ge 3$ is convergent by the Monotone Convergence Theorem (Real Analysis).
Now we need to demonstrate that this limit is in fact $1$.
Let $n^{1 / n} \to l$ as $n \to \infty$.
Having established this, we can investigate the subsequence $\sequence {\paren {2 n}^{1 / {2 n} } }$.
By Limit of Subsequence equals Limit of Real Sequence, this will converge to $l$ also.
From Limit of Root of Positive Real Number, we have that $2^{1 / {2 n} } \to 1$ as $n \to \infty$.
So $n^{1 / {2 n} } \to l$ as $n \to \infty$ by the Combination Theorem for Sequences.
Thus:
:$n^{1 / n} = n^{1 / {2 n} } \cdot n^{1 / {2 n} } \to l \cdot l = l^2$
as $n \to \infty$.
So $l^2 = l$, and as $l \ge 1$ the result follows.
{{qed}}
Theorem: Limit of Integer to Reciprocal Power

Let $\sequence {x_n}$ be the real sequence defined as $x_n = n^{1/n}$, using exponentiation.
Then $\sequence {x_n}$ converges with a limit of $1$.

Proof:
We have the definition of the power to a real number:
:$\ds n^{1/n} = \map \exp {\frac 1 n \ln n}$
From Powers Drown Logarithms, we have that:
:$\ds \lim_{n \mathop \to \infty} \frac 1 n \ln n = 0$
Hence:
:$\ds \lim_{n \mathop \to \infty} n^{1/n} = \exp 0 = 1$
and the result.
{{qed}}
Theorem: Limit of Integer to Reciprocal Power

Let $\sequence {x_n}$ be the real sequence defined as $x_n = n^{1/n}$, using exponentiation.
Then $\sequence {x_n}$ converges with a limit of $1$.

Proof:
Let $n^{1/n} = 1 + a_n$.
The strategy is to:
:$(1): \quad$ prove that $a_n > 0$ for $n > 1$
:$(2): \quad$ deduce that $n - 1 \ge \dfrac {n \paren {n - 1} } {2!} a_n^2$ for $n > 1$
and hence:
:$(3): \quad$ deduce that $0 \le a_n^2 \le \dfrac 2 n$
Let $n > 1$.
Then:
{{begin-eqn}}
{{eqn | l = n
      | r = \paren {1 + a_n}^n
      | c = 
}}
{{eqn | r = 1 + n a_n + \dfrac {n \paren {n - 1} } {2!} a_n^2
      | c = 
}}
{{end-eqn}}
{{finish}}
Theorem: Difference Between Adjacent Square Roots Converges

Let $\sequence {x_n}$ be the sequence in $\R$ defined as $x_n = \sqrt {n + 1} - \sqrt n$.
Then $\sequence {x_n}$ converges to a zero limit.

Proof:
We have:
{{begin-eqn}}
{{eqn | l = 0
      | o = \le
      | r = \sqrt {n + 1} - \sqrt n
      | c = 
}}
{{eqn | r = \frac {\paren {\sqrt {n + 1} - \sqrt n} \paren {\sqrt {n + 1} + \sqrt n} } {\sqrt {n + 1} + \sqrt n}
      | c = multiplying top and bottom by $\sqrt {n + 1} + \sqrt n$
}}
{{eqn | r = \frac {n + 1 - n} {\sqrt {n + 1} + \sqrt n}
      | c = Difference of Two Squares
}}
{{eqn | r = \frac 1 {\sqrt {n + 1} + \sqrt n}
      | c = 
}}
{{eqn | o = <
      | r = \frac 1 {\sqrt n}
      | c = as $\sqrt {n + 1} + \sqrt n > \sqrt n$
}}
{{end-eqn}}
But from Sequence of Powers of Reciprocals is Null Sequence, $\dfrac 1 {\sqrt n} \to 0$ as $n \to \infty$.
The result follows by the Squeeze Theorem.
{{Qed}}
Theorem: Peak Point Lemma

Let $\sequence {x_n}$ be a sequence in $\R$ which is infinite.
Then $\sequence {x_n}$ has an infinite subsequence which is monotone.

Proof:
There are $2$ cases to consider.
First, suppose that every set $\set {x_n: n > N}$ has a maximum.
If this is the case, we can find a sequence $n_r \in \N$ such that:
:$\ds x_{n_1} = \max \set {x_n: n > 1}$
:$\ds x_{n_2} = \max \set {x_n: n > n_1}$
:$\ds x_{n_3} = \max \set {x_n: n > n_2}$
and so on.
From the method of construction, $n_1 < n_2 < n_3 < \cdots$, so at each stage we are taking the maximum of a subset of the previous set.
At each stage, the previous maximum has already been taken as the previous term in the sequence.
Thus, $\sequence {x_{n_r} }$ is a decreasing subsequence of $\sequence {x_n}$.
{{qed|lemma}}
Second, suppose it is ''not'' true that ''every'' set $\set {x_n: n > N}$ has a maximum.
Then there will exist some $N_1$ such that $\set {x_n: n > N_1}$ has no maximum.
So it follows that, given some $x_m$ with $m > N_1$, we can find an $x_n$ following that $x_m$ such that $x_n > x_m$.
(Otherwise, the biggest of $x_{N_1 + 1}, \ldots, x_m$ would be a maximum for $\set {x_n: n > N_1}$.)
So, we define $x_{n_1} = x_{N_1 + 1}$.
Then $x_{n_2}$ can be the first term after $x_{n_1}$ such that $x_{n_2} > x_{n_1}$.
Then $x_{n_3}$ can be the first term after $x_{n_2}$ such that $x_{n_3} > x_{n_2}$.
And so on.
Thus we get an increasing subsequence of $\sequence {x_n}$.
{{qed|lemma}}
There exist only these two possibilities.
From each one we get a subsequence that is monotone:
:one is decreasing
:one is increasing.
We can of course choose instead to investigate whether every set $\set {x_n: n > N}$ has a minimum.
The same conclusion will be reached.
{{qed}}
Theorem: Peak Point Lemma

Let $\sequence {x_n}$ be a sequence in $\R$ which is infinite.
Then $\sequence {x_n}$ has an infinite subsequence which is monotone.

Proof:
A coastal town in Spain has an infinite row of hotels along a road leading down to the beach.
The tourist bureau which rates these hotels has a special designation for any hotel having a view of the sea.
Any hotel which is at least as tall as the rest of the hotels on the road to the sea receives this view-rating.
Starting with the hotel farthest from the sea, let $x_1, x_2, \ldots$ denote the heights of the hotels as we travel along the road to the beach.
One possibility is that an infinite number of hotels are view-rated.
In this case the heights of these hotels form a decreasing (i.e. nonincreasing) subsequence of the original sequence of heights.
The other possibility is that only a finite number of hotels are view-rated.
In this case we can obtain an increasing subsequence as follows.
Walk along the road to the beach past all the view-rated hotels.
Let $n_1$ be the index of the next hotel.
Since it does not have a view of the sea, there is a taller hotel nearer the shore which blocks the view.
Let $n_2$ be the index of that taller hotel.
Since it is not view-rated, it does not have a view of the sea.
Thus there must be an even taller hotel nearer the shore which blocks the view.
In this way we generate a list of indices $n_1 < n_2 < n_3 \cdots$ of taller and taller hotels.
This gives an increasing subsequence $x_{n_1}, x_{n_2}, x_{n_3}, \ldots$ of the original sequence.
{{qed}}
Theorem: Bolzano-Weierstrass Theorem

Every bounded sequence of real numbers has a convergent subsequence.

Proof:
Let $\sequence {x_n}$ be a bounded sequence in $\R$.
By the Peak Point Lemma, $\sequence {x_n}$ has a monotone subsequence $\sequence {x_{n_r} }$.
Since $\sequence {x_n}$ is bounded, so is $\sequence {x_{n_r} }$.
Hence, by the Monotone Convergence Theorem (Real Analysis), the result follows.
{{qed}}
Theorem: Bolzano-Weierstrass Theorem

Every bounded sequence of real numbers has a convergent subsequence.

Proof:
Let $\sequence {x_n}_{n \mathop \in \N}$ be a bounded sequence in $\R$.
By definition there are real numbers $a, b \in \R$ such that $ x_n \in \openint{a}{b}$ for all $n \in \N$.
We will construct a subsequence  $\sequence {x_{n_i}}_{i \mathop \in \N}$ and two sequences of real numbers $\sequence {b_i}_{i \mathop \in \N}$, $\sequence {c_i}_{i \mathop \in \N}$ as follows:
Set $a_0 = a$, and $b_0 = b$.
For $i \in \N$, at least one of the sets:
:$\set {x_n: n > n_{i-1} , a_i < x_n < \dfrac {a_i + b_i} 2 }, \set {x_n : n > n_{i-1} , \dfrac {a_i + b_i} 2 < x_n < b_i }, \set {x_n : n > n_{i-1} , x_n = \dfrac {a_i + b_i } 2 }$
contains infinitely many elements.
If the set $\set {x_n : n > n_{i-1} , x_n = \dfrac {a_i + b_i} 2 }$ is infinite, the elements of this set form a subsequence that converges to $\dfrac {a_i + b_i} 2$, and the proof is done.
If instead the set $\set {x_n: n > n_{i-1} , a_i < x_n < \dfrac {a_i + b_i} 2 }$ is infinite, define $x_{n_i}$ as the element of that set with the smallest index.
In this case, set $a_{i+1} = a_i$, and $b_{i+1} = \dfrac { a_i + b_i } 2 $.
If instead the set $\set {x_n : n > n_{i-1} , \dfrac {a_i + b_i} 2 < x_n < b_i }$ is infinite, define $x_{n_i}$ as the element of that set with the smallest index.
In this case, set $a_{i+1} = \dfrac { a_i + b_i } 2 $, and $b_{i+1} = b_i$.
In both cases, we have $x_{n_i} \in \openint{ a_j }{ b_j }$ for all $j \in \N$ with $j < i$, so
:$\size { x_{n_j} - x_{n_i} } < b_j - a_j = \dfrac{ a + b } {2^j}$
Repeat this process so we obtain a subsequence $\sequence {x_{n_i} }_{i \mathop \in \N}$.
Given $\epsilon > 0$, we can choose $j \in \N$ so $\size { x_{n_{i}} - x_{n_{i'}} } < \dfrac{ a + b } {2^j} < \epsilon$ for all $i , i' \geq j$.
By {{Defof|Real Cauchy Sequence}}, the subsequence is a Cauchy sequence.
By Cauchy's Convergence Criterion on Real Numbers, the subsequence converges.
{{qed}}
Theorem: Existence of Maximum and Minimum of Bounded Sequence

Let $\sequence {x_n}$ be a bounded sequence in $\R$ (which may or may not be convergent).
Let $L$ be the set of all real numbers which are the limit of some subsequence of $\sequence {x_n}$.
Then $L$ has both a maximum and a minimum.

Proof:
From the Bolzano-Weierstrass Theorem:
:$L \ne \O$
From Lower and Upper Bounds for Sequences, $L$ is a bounded subset of $\R$.
Thus $L$ does have a supremum and infimum in $\R$.
The object of this proof is to confirm that:
:$\overline l := \map \sup L \in L$
and:
:$\underline l := \map \inf L \in L$
that is, that these points do actually belong to $L$.
First we show that $\overline l \in L$.
To do this, we show that:
:$\exists \sequence {x_{n_r} }: x_{n_r} \to \overline l$ as $n \to \infty$
where $\sequence {x_{n_r} }$ is a subsequence of $\sequence {x_n}$.
Let $\epsilon > 0$.
Then $\dfrac \epsilon 2 > 0$.
Since $\overline l = \map \sup L$, and therefore by definition the ''smallest'' upper bound of $L$, $\overline l - \dfrac \epsilon 2$ is ''not'' an upper bound of $L$.
Hence:
:$\exists l \in L: \overline l \ge l > \overline l - \dfrac \epsilon 2$
Therefore:
:$\sequence {l - \overline l} < \dfrac \epsilon 2$
Now because $l \in L$, we can find $\sequence {x_{m_r} }$, a subsequence of $\sequence {x_n}$, such that $x_{m_r} \to l$ as $n \to \infty$.
So:
:$\exists R: \forall r > R: \size {x_{m_r} - \overline l} < \dfrac \epsilon 2$
So, for any $r > R$:
{{begin-eqn}}
{{eqn | l = \size {x_{m_r} - \overline l}
      | r = \size {x_{m_r} - l + l - \overline l}
      | c = 
}}
{{eqn | o = \le
      | r = \size {x_{m_r} - l} + \size {l - \overline l}
      | c = Triangle Inequality
}}
{{eqn | o = <
      | r = \frac \epsilon 2 + \frac \epsilon 2 = \epsilon
      | c = 
}}
{{end-eqn}}
Thus we have shown that:
:$\forall r > R: \size {x_{m_r} - \overline l} < \epsilon$
So far, what has been shown is that, given any $\epsilon > 0$, there exists an infinite set of terms of $\sequence {x_n}$ which satisfy $\size {x_n - \overline l} < \epsilon$.
Next it is shown how to construct a subsequence:
:$\sequence {x_{n_r} }$ such that $x_{n_r} \to \overline l$
as $n \to \infty$.
Take $\epsilon = 1$ in the above.
Then:
:$\exists n_1: \size {x_{n_1} - \overline l} < 1$
Now take $\epsilon = \dfrac 1 2$ in the above.
Then:
:$\exists n_2 > n_1: \size {x_{n_2} - \overline l} < \dfrac 1 2$
In this way a subsequence is contructed:
:$\sequence {x_{n_r} }$ satisfying $\size {x_{n_r} - \overline l} < \dfrac 1 r$
But $\dfrac 1 r \to 0$ as $r \to \infty$ from the Sequence of Reciprocals is Null Sequence.
From the Squeeze Theorem for Real Sequences, it follows that:
:$\size {x_{n_r} - \overline l} \to 0$ as $r \to \infty$
Thus $\overline l \in L$ as required.
{{qed|lemma}}
A similar argument shows that the infimum $\underline l$ of $L$ is also in $L$.
{{qed}}
Theorem: Difference of Two Powers

Let $\mathbb F$ denote one of the standard number systems, that is $\Z$, $\Q$, $\R$ and $\C$.
Let $n \in \N$ such that $n \ge 2$.
Then for all $a, b \in \mathbb F$:
{{begin-eqn}}
{{eqn | l = a^n - b^n
      | r = \paren {a - b} \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j
      | c = 
}}
{{eqn | r = \paren {a - b} \paren {a^{n - 1} + a^{n - 2} b + a^{n - 3} b^2 + \dotsb + a b^{n - 2} + b^{n - 1} }
      | c = 
}}
{{end-eqn}}

Proof:
Let $\ds S_n = \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j$.
This can also be written:
:$\ds S_n = \sum_{j \mathop = 0}^{n - 1} b^j a^{n - j - 1}$
Consider:
:$\ds a S_n = \sum_{j \mathop = 0}^{n - 1} a^{n - j}  b^j$
Taking the first term (where $j = 0$) out of the summation, we get:
:$\ds a S_n = \sum_{j \mathop = 0}^{n - 1} a^{n - j} b^j = a^n + \sum_{j \mathop = 1}^{n - 1} a^{n - j} b^j$
Similarly, consider:
:$\ds b S_n = \sum_{j \mathop = 0}^{n - 1} a^j b^{n - j}$
Taking the first term (where $j = 0$) out of the summation:
:$\ds b S_n = \sum_{j \mathop = 0}^{n - 1} a^j b^{n - j} = b^n + \sum_{j \mathop = 1}^{n - 1} a^{n - j} b^j$
This is equal to:
:$\ds b^n + \sum_{j \mathop = 1}^{n - 1} a^j b^{n - j}$
by Permutation of Indices of Summation.
So:
{{begin-eqn}}
{{eqn | l = \paren {a - b} S_n
      | r = a \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j - b \sum_{j \mathop = 0}^{n - 1} a^j b^{n - j - 1}
      | c = 
}}
{{eqn | r = \sum_{j \mathop = 0}^{n - 1} a^{n - j} b^j - \sum_{j \mathop = 0}^{n - 1} a^j b^{n - j}
      | c = 
}}
{{eqn | r = a^n + \sum_{j \mathop = 1}^{n - 1} a^{n - j} b^j - \sum_{j \mathop = 1}^{n - 1} a^{n - j} b^j - b^n
      | c = 
}}
{{eqn | r = a^n - b^n
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Difference of Two Powers

Let $\mathbb F$ denote one of the standard number systems, that is $\Z$, $\Q$, $\R$ and $\C$.
Let $n \in \N$ such that $n \ge 2$.
Then for all $a, b \in \mathbb F$:
{{begin-eqn}}
{{eqn | l = a^n - b^n
      | r = \paren {a - b} \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j
      | c = 
}}
{{eqn | r = \paren {a - b} \paren {a^{n - 1} + a^{n - 2} b + a^{n - 3} b^2 + \dotsb + a b^{n - 2} + b^{n - 1} }
      | c = 
}}
{{end-eqn}}

Proof:
From Sum of Geometric Sequence:
{{begin-eqn}}
{{eqn | l = \sum_{j \mathop = 0}^{n - 1} x^j
      | r = \frac {x^n - 1} {x - 1}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {\dfrac a b}^n - 1
      | r = \paren {\dfrac a b - 1} \sum_{j \mathop = 0}^{n - 1} \paren {\dfrac a b}^j
      | c = setting $x = \dfrac a b$
}}
{{eqn | ll= \leadsto
      | l = \paren {\dfrac {a^n - b^n} {b^n} }
      | r = \paren {\dfrac {a - b} b} \paren {\paren {\dfrac a b}^{n - 1} + \paren {\dfrac a b}^{n - 2} + \dotsb + \paren {\dfrac a b}^1 + 1}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = a^n - b^n
      | r = \paren {a - b} \paren {a^{n - 1} + a^{n - 2} b + \dotsb + a b^{n - 2} + b^{n - 1} }
      | c = multiplying both sides by $b^n$
}}
{{end-eqn}}
{{qed}}
Theorem: Difference of Two Powers

Let $\mathbb F$ denote one of the standard number systems, that is $\Z$, $\Q$, $\R$ and $\C$.
Let $n \in \N$ such that $n \ge 2$.
Then for all $a, b \in \mathbb F$:
{{begin-eqn}}
{{eqn | l = a^n - b^n
      | r = \paren {a - b} \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j
      | c = 
}}
{{eqn | r = \paren {a - b} \paren {a^{n - 1} + a^{n - 2} b + a^{n - 3} b^2 + \dotsb + a b^{n - 2} + b^{n - 1} }
      | c = 
}}
{{end-eqn}}

Proof:
The proof will proceed by the Principle of Complete Finite Induction on $\Z_{>0}$.
Let $S$ be the set defined as:
:$\ds S := \set {n \in \Z_{>0}: a^n - b^n = \paren {a - b} \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j}$
That is, $S$ is to be the set of all $n$ such that:
:$\ds a^n - b^n = \paren {a - b} \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j$
=== Basis for the Induction ===
We have that:
:$\ds a^1 - b^1 = \paren {a - b} \sum_{j \mathop = 0}^0 a^{1 - 0 - 1} b^j$
So $1 \in S$.
This is the basis for the induction.
=== Induction Hypothesis ===
It is to be shown that if $r \in S$ for all $r$ such that $1 \le r \le k$, then it follows that $k + 1 \in S$.
This is the induction hypothesis:
:$\forall r \in \Z_{>0}: 1 \le r \le k: \ds a^r - b^r = \paren {a - b} \sum_{j \mathop = 0}^{r - 1} a^{r - j - 1} b^j$
It is to be demonstrated that it follows that:
:$\ds a^{k + 1} - b^{k + 1} = \paren {a - b} \sum_{j \mathop = 0}^k a^{k - j} b^j$
=== Induction Step ===
This is the induction step:
{{begin-eqn}}
{{eqn | l = a^{k + 1} - b^{k + 1}
      | r = \paren {a + b} \paren {a^k - b^k} - a b \paren {a^{k - 1} - b^{k - 1} }
      | c = 
}}
{{eqn | r = \paren {a + b} \paren {a - b} \sum_{j \mathop = 0}^{k - 1} a^{k - j - 1} b^j - a b \paren {a - b} \sum_{j \mathop = 0}^{k - 2} a^{k - j - 2} b^j
      | c = Induction Hypothesis
}}
{{eqn | r = \paren {a - b} \paren {\paren {a + b} \sum_{j \mathop = 0}^{k - 1} a^{k - j - 1} b^j - a b \sum_{j \mathop = 0}^{k - 2} a^{k - j - 2} b^j}
      | c = 
}}
{{eqn | r = \paren {a - b} \paren {\sum_{j \mathop = 0}^{k - 1} a^{k - j} b^j + \sum_{j \mathop = 0}^{k - 1} a^{k - j - 1} b^{j + 1} - \sum_{j \mathop = 0}^{k - 2} a^{k - j - 1} b^{j + 1} }
      | c = 
}}
{{eqn | r = \paren {a - b} \paren {\sum_{j \mathop = 0}^{k - 1} a^{k - j} b^j + a^0 b^k}
}}
{{eqn | r = \paren {a - b} \sum_{j \mathop = 0}^k a^{k - j} b^j
}}
{{end-eqn}}
So $\forall r \in S: 0 \le r \le k: r \in S \implies k + 1 \in S$ and the result follows by the Principle of Complete Finite Induction:
:$\forall n \in \Z_{>0}: \ds a^n - b^n = \paren {a - b} \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j$
{{qed}}
Theorem: Difference of Two Powers

Let $\mathbb F$ denote one of the standard number systems, that is $\Z$, $\Q$, $\R$ and $\C$.
Let $n \in \N$ such that $n \ge 2$.
Then for all $a, b \in \mathbb F$:
{{begin-eqn}}
{{eqn | l = a^n - b^n
      | r = \paren {a - b} \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j
      | c = 
}}
{{eqn | r = \paren {a - b} \paren {a^{n - 1} + a^{n - 2} b + a^{n - 3} b^2 + \dotsb + a b^{n - 2} + b^{n - 1} }
      | c = 
}}
{{end-eqn}}

Proof:
Let $\map f x = x^n$ for $x \in \R, n \in \N$.
Let $a \in \R$.
By definition of the derivative:
:$\ds \map {f'} a = \lim_{x \mathop \to a} \frac {\map f x - \map f a} {x - a} = \lim_{x \mathop \to a} \frac {x^n - a^n} {x - a}$
=== Case $\text I$ ===
For $n = 0$ it is possible to do:
{{begin-eqn}}
{{eqn | l = \map {f'} a
      | r = \lim_{x \mathop \to a} \frac {x^0 - a^0} {x - a}
      | c = 
}}
{{eqn | r = \lim_{x \mathop \to a} \frac 0 {x - a}
}}
{{eqn | r = 0
      | c = 
}}
{{end-eqn}}
We have that:
:$0 \cdot x^{0 - 1} = 0$
for all $x \ne 0$.
So in this case:
:$\map {f'} x = n x^{n - 1}$
{{qed|lemma}}
=== Case $\text {II}$ ===
For $n = 1$ we have:
:$\map f x = x$
From Derivative of Identity Function:
:$\map {f'} x = 1$
Then we note that:
:$1 \cdot x^{1 - 1} = 1$
So for the case $n = 1$:
:$\map {f'} x = n x^{n - 1}$
{{qed|lemma}}
=== Case $\text {III}$ ===
$\R$ is a commutative ring, so for $n \ge 2$ it is possible to do:
{{begin-eqn}}
{{eqn | l = \map {f'} a
      | r = \lim_{x \mathop \to a} \frac {x^n - a^n} {x - a}
      | c = 
}}
{{eqn | r = \lim_{x \mathop \to a} \frac {\paren {x - a} \sum_{j \mathop = 0}^{n - 1} x^{n - j - 1} a^j} {x - a}
      | c = Difference of Two Powers
}}
{{eqn | r = \lim_{x \mathop \to a} \sum_{j \mathop = 0}^{n - 1} x^{n - j - 1} a^j
}}
{{eqn | r = \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} a^j
      | c = Real Polynomial Function is Continuous
}}
{{eqn | r = \sum_{j \mathop = 0}^{n - 1} a^{n - 1}
}}
{{eqn | r = \sum_{j \mathop = 1}^n a^{n - 1}
      | c = shifting the index from $0$ to $1$
}}
{{eqn | r = n a^{n - 1}
}}
{{end-eqn}}
This holds for all $a \in \R$, so:
:$\map {f'} x = n x^{n - 1}$
{{qed}}