nyuuzyou/wikis huggingface dataset:
Cartesian Product of Sets is Set

== Theorem ==
Let $V$ be a basic universe.
Let $A$ and $B$ be sets in $V$.
Then their cartesian product $A \times B$ is also a set.
== Proof ==
Let $A$ and $B$ be sets in $V$.
Because $V$ is a basic universe, the basic universe axioms apply.
Hence by the axiom of pairing $\set {A, B}$ is a set.
Then by the axiom of unions $\bigcup \set {A, B}$ is also a set.
We have that $A \cup B = \bigcup \set {A, B}$.
By the axiom of powers $\powerset {A \cup B}$ is a set.
Therefore, also by the axiom of powers, so is $\powerset {\powerset {A \cup B} }$.
It remains to be shown that $A \times B$ is a subclass of $\powerset {\powerset {A \cup B} }$.
Let $x \in A \times B$.
Then:
:$x = \tuple {a, b}$
for some $a \in A$ and $b \in B$.
By definition of ordered pair:
:$x = \set {\set a, \set {a, b} }$
From Set is Subset of Union:
:$A \subseteq A \cup B$ and $B \subseteq A \cup B$
Hence by definition of subset:
:$a \in A \cup B$
and:
:$b \in A \cup B$
Thus:
:$\set a \subseteq A \cup B$
and:
:$\set {a, b} \subseteq A \cup B$
Thus by definition of power set:
:$\set a \in \powerset {A \cup B}$
and:
:$\set {a, b} \in \powerset {A \cup B}$
Hence:
:$\set {\set a, \set {a, b} } \subseteq \powerset {A \cup B}$
That is:
:$\tuple {a, b} \subseteq \powerset {A \cup B}$
and so:
:$x \subseteq \powerset {A \cup B}$
which means:
:$x \in \powerset {\powerset {A \cup B} }$
Hence by definition of subclass:
:$A \times B \subseteq \powerset {\powerset {A \cup B} }$
We have that $\powerset {\powerset {A \cup B} }$ is a set.
By the it follows that $A \times B$ is also a set.
== Sources ==
* : Chapter $2$: Some Basics of Class-Set Theory: $\S 7$ Cartesian products: Theorem $7.1$
Category:Cartesian Product
Cartesian Product of Subsets

== Theorem ==
Let $A, B, S, T$ be sets such that $A \subseteq B$ and $S \subseteq T$.
Then:
:$A \times S \subseteq B \times T$
In addition, if $A, S \ne \O$, then:
:$A \times S \subseteq B \times T \iff A \subseteq B \land S \subseteq T$
=== Corollary 1 ===
=== Corollary 2 ===
=== Corollary 3 ===
=== Family of Subsets ===
==== Nonempty Subsets ====
== Proof ==
First we show that $A \subseteq B \land S \subseteq T \implies A \times S \subseteq B \times T$.
First, let $A = \O$ or $S = \O$.
Then from Cartesian Product is Empty iff Factor is Empty:
:$A \times S = \O \subseteq B \times T$
so the result holds.
Next, let $A, S \ne \O$.
Then from Cartesian Product is Empty iff Factor is Empty:
:$A \times S \ne \O$
and we can use the following argument:
Thus $A \times S \subseteq B \times T$ as we were to prove.
Now we show that if $A, S \ne \O$, then:
:$A \times S \subseteq B \times T \implies A \subseteq B \land S \subseteq T$
So suppose that $A \times S \subseteq B \times T$.
First note that if $A = \O$, then $A \times S = \O \subseteq B \times T$, whatever $S$ is, so it is not necessarily the case that $S \subseteq T$.
Similarly if $S = \O$; it is not necessarily the case that $A \subseteq B$.
So that explains the restriction $A, S \ne \O$.
Now, as $A, S \ne \O$, $\exists x \in A, y \in S$.
Thus:
So when $A, S \ne \O$, we have:
:$A \subseteq S \land B \subseteq T \implies A \times S \subseteq B \times T$
:$A \times S \subseteq B \times T \implies A \subseteq B \land S \subseteq T$
from which:
:$A \times S \subseteq B \times T \iff A \subseteq B \land S \subseteq T$
== Sources ==
* : $\S 6$: Ordered Pairs
* : Chapter $\text I$: Algebraic Structures: $\S 1$: The Language of Set Theory: Exercise $1.3$
* : $1$: Set Theory and Logic: $\S 1$: Fundamental Concepts: Exercise $1.2 \ \text{(j)}, \text{(l)}$
Category:Cartesian Product
Category:Subsets
Category:Cartesian Product of Subsets
Cartesian Product of Subsets/Corollary 1

== Corollary to Cartesian Product of Subsets ==
Let $A, B, S$ be sets such that $A \subseteq B$.
Then:
:$A \times S \subseteq B \times S$
== Proof ==
From Set is Subset of Itself we have $S \subseteq S$.
From Cartesian Product of Subsets:
:$A \subseteq B \land S \subseteq S \implies A \times S \subseteq B \times S$
== Sources ==
* : $\S 1.9$: Cartesian Product: Exercise $1$
Category:Cartesian Product of Subsets
Cartesian Product of Subsets/Corollary 2

== Corollary to Cartesian Product of Subsets ==
Let $A, S, T$ be sets such that $S \subseteq T$.
Then:
:$A \times S \subseteq A \times T$
== Proof ==
From Set is Subset of Itself we have $A \subseteq A$.
From Cartesian Product of Subsets:
:$A \subseteq A \land S \subseteq T \implies A \times S \subseteq A \times T$
Category:Cartesian Product of Subsets
Cartesian Product of Subsets/Corollary 3

== Corollary to Cartesian Product of Subsets ==
Let $A, B, C$ be sets such that $B \ne \O$.
Let $A \times B \subseteq C \times C$.
Then:
:$A \subseteq C$
== Proof ==
Since $B \ne O$ we have from Cartesian Product of Subsets that:
:$A \times B \subseteq C \times C \implies A \subseteq C \land B \subseteq C$
== Sources ==
* : $\S 8.1$: Cartesian product of sets
Category:Cartesian Product of Subsets
Cartesian Product of Subsets/Family of Nonempty Subsets

== Theorem ==
Let $\family {S_i}_{i \mathop \in I}$ be a family of sets where $I$ is an arbitrary index set.
Let $S = \ds \prod_{i \mathop \in I} S_i$ be the Cartesian product of $\family {S_i}_{i \mathop \in I}$.
Let $\family {T_i}_{i \mathop \in I}$ be another family of sets.
Let $T = \ds \prod_{i \mathop \in I} T_i$ be the Cartesian product of $\family {T_i}_{i \mathop \in I}$.
Let $T_i \ne \O$ for all $i \in I$.
Then:
:$T \subseteq S \iff \forall i \in I: T_i \subseteq S_i$.
== Proof ==
From Cartesian Product of Family of Subsets:
:$\paren {\forall i \in I: T_i \subseteq S_i} \implies T \subseteq S$
So it remains to show that:
:$T \subseteq S \implies \forall i \in I : T_i \subseteq S_i$.
Let $T \subseteq S$.
Let $x_j \in T_j$ for some $j \in I$.
Let $\map x j = x_j$
Suppose $k \in I: k \ne j$.
As $T_k \ne \O$ it is possible to use the axiom of choice to choose $\map x k \in T_k$.
Then:
:$x \in T \subseteq S$
By definition of the Cartesian product $S$:
:$\forall i \in I: \map x i \in S_i$
In particular:
:$\map x j = x_j \in S_j$
As $x_j$ is an arbitrary element of $T_j$:
:$T_j \subseteq S_j$
As $j$ is an arbitrary element of $I$:
:$\forall i \in I: T_i \subseteq S_i$
The result follows. 
Category:Cartesian Product of Subsets
Category:Indexed Families
Cartesian Product of Subsets/Family of Subsets

== Theorem ==
Let $\family {S_i}_{i \mathop \in I}$ be a family of sets where $I$ is an arbitrary index set.
Let $S = \ds \prod_{i \mathop \in I} S_i$ be the Cartesian product of $\family {S_i}_{i \mathop \in I}$.
Let $\family {T_i}_{i \mathop \in I}$ be a family of sets.
Let $T = \ds \prod_{i \mathop \in I} T_i$ be the Cartesian product of $\family {T_i}_{i \mathop \in I}$.
Then:
:$\paren {\forall i \in I: T_i \subseteq S_i} \implies T \subseteq S$.
=== Nonempty Subsets ===
== Proof ==
Let $T_i \subseteq S_i$ for all $i \in I$.
Then:
Thus $T \subseteq S$ by the definition of a subset.
Category:Cartesian Product of Subsets
Category:Indexed Families
Cartesian Product of Unions

== Theorem ==
:$\paren {A \cup B} \times \paren {C \cup D} = \paren {A \times C} \cup \paren {B \times D} \cup \paren {A \times D} \cup \paren {B \times C}$
=== Corollary ===
=== General Result ===
== Proof ==
== Sources ==
* : Chapter $1$. Sets: Exercise $11$
* : Chapter $1$: The Notation and Terminology of Set Theory: $\S 9 \alpha$
* : $\S 3$. Ordered pairs; cartesian product sets: Exercise $3 \ (4)$
* : Chapter $1$: Sets and Logic: Exercise $15$
* : Chapter $2$: Some Basics of Class-Set Theory: $\S 7$ Cartesian products: Exercise $7.1$
Category:Cartesian Product
Category:Set Union
Category:Cartesian Product of Unions
Cartesian Product of Unions/General Result

== Theorem ==
Let $I$ and $J$ be indexing sets.
Let $\family {A_i}_{i \mathop \in I}$ and $\family {B_j}_{j \mathop \in J}$ be families of sets indexed by $I$ and $J$ respectively.
Then:
:$\ds \paren {\bigcup_{i \mathop \in I} A_i} \times \paren {\bigcup_{j \mathop \in J} B_j} = \bigcup_{\tuple {i, j} \mathop \in I \times J} \paren {A_i \times B_j}$
where:
:$\ds \bigcup_{i \mathop \in I} A_i$ denotes the union of $\family {A_i}_{i \mathop \in I}$ and so on
:$\times$ denotes Cartesian product.
== Proof ==
== Sources ==
* : $\S 9$: Families
Category:Cartesian Product of Unions
Cartesian Product under Chebyshev Distance of Continuous Mappings between Metric Spaces is Continuous

== Theorem ==
Let $n \in \N_{>0}$.
Let $M_1 = \struct {A_1, d_1}, M_2 = \struct {A_2, d_2}, \ldots, M_n = \struct {A_n, d_n}$ be metric spaces.
Let $N_1 = \struct {B_1, d'_1}, N_2 = \struct {B_2, d'_2}, \ldots, N_n = \struct {B_n, d'_n}$ be metric spaces.
Let $f_i: M_i \to N_i$ be continuous mappings for all $i \in \set {1, 2, \ldots, n}$.
Let $\ds \MM = \prod_{i \mathop = 1}^n M_i$ be the cartesian product of $A_1, A_2, \ldots, A_n$.
Let $\ds \NN = \prod_{i \mathop = 1}^n N_i$ be the cartesian product of $B_1, B_2, \ldots, B_n$.
Let $d_\infty$ be the Chebyshev distance on $\ds \AA = \prod_{i \mathop = 1}^n A_i$, and $\ds \BB = \prod_{i \mathop = 1}^n B_i$, defined as:
:$\ds \map {d_\infty} {x, y} = \max_{i \mathop = 1}^n \set {\map {d_i} {x_i, y_i} }$
:$\ds \map {d_\infty} {x, y} = \max_{i \mathop = 1}^n \set {\map {d'_i} {x_i, y_i} }$
where $x = \tuple {x_1, x_2, \ldots, x_n}, y = \tuple {y_1, y_2, \ldots, y_n} \in \AA$ or $\BB$.
Let $F: M \to N$ be the mapping defined as:
:$\forall x \in \AA: \map F {x_1, x_2, \ldots, x_n} = \tuple {\map f {x_1}, \map f {x_2}, \ldots, \map f {x_n} }$
Then $F$ is continuous.
== Proof ==
Let $\epsilon \in \R_{>0}$.
Let $x \in \AA$.
Let $k \in \left\{{1, 2, \ldots, n}\right\}$.
Then as $f_k$ is continuous:
:$(1): \quad \exists \delta_k \in \R_{>0}: \forall y_k \in A_k: \map {d_k} {x_k, y_k} < \delta_k \implies \map {d'} {\map {f_k} {x_k}, \map {f_k} {y_k} } < \epsilon$
Let $\delta = \max \set {\delta_k: k \in \set {1, 2, \ldots, n} }$.
Then:
Thus it has been demonstrated that:
:$\forall \epsilon \in \R_{>0}: \exists \delta \in \R_{>0}: \forall y \in X: \map {d_\infty} {x, y} < \delta \implies \map {d_\infty} {\map F x, \map F y} < \epsilon$
Hence by definition of continuity at a point, $F$ is continuous at $x$.
As $x$ is chosen arbitrarily, it follows that $F$ is continuous for all $x \in X$.
The result follows by definition of continuous mapping.
== Sources ==
* : Chapter $2$: Metric Spaces: $\S 3$: Continuity: Exercise $2$
Category:Continuous Mappings on Metric Spaces
Category:Chebyshev Distance
Cartesian Product with Complement

== Theorem ==
Let $S$ and $T$ be sets.
Let $A \subseteq S$ and $B \subseteq T$ be subsets of $S$ and $T$, respectively.
Let $\relcomp S A$ denote the relative complement of $A$ in $S$.
Then:
== Proof ==
By definition of relative complement we have:
:$\relcomp S A = S \setminus A$
where $S \setminus A$ denotes set difference.
By Cartesian Product Distributes over Set Difference, we have:
:$\paren {S \setminus A} \times T = \paren {S \times T} \setminus \paren {A \times T}$
and the latter equals $\relcomp {S \times T} {A \times T}$.
In conclusion, we obtain:
:$\relcomp S A \times T = \relcomp {S \times T} {A \times T}$
as desired.
Mutatis mutandis, the other statement follows from this argument as well.
 
Category:Cartesian Product
Category:Set Complement
Cartesian Product with Proper Class is Proper Class

== Theorem ==
Let $A$ be a proper class.
Let $B$ be a class which is not empty.
Then the Cartesian product $\paren {A \times B}$ is a proper class.
== Proof ==
 that $\paren {A \times B}$ is small.
By Domain of Small Relation is Small, the domain of $\paren {A \times B}$ is small.
Since $B \ne \O$, Nonempty Class has Members shows that $\exists y: y \in B$.
The domain of $\paren {A \times B}$ is the collection of all $x \in A$ such that $\exists y: y \in B$.
The domain of $\paren {A \times B}$ is $A$.
Therefore, $A$ is small, contradicting the fact that it is a proper class.
== Sources ==
* : $\S 6.9 \ (2)$
Category:Class Theory
Cassini's Identity

== Theorem ==
Let $F_k$ be the $k$th Fibonacci number.
Then:
:$F_{n + 1} F_{n - 1} - F_n^2 = \paren {-1}^n$
=== Negative Indices ===
== Proof 1 ==
== Proof 2 ==
== Also reported as ==
This is also sometimes reported (slightly less elegantly) as:
:$F_{n + 1}^2 - F_n F_{n + 2} = \paren {-1}^n$
== Historical Note ==
== Sources ==
* 
* : $\text {1-1}$ Principle of Mathematical Induction: Exercise $10$
* : $5$
* : $5$
Category:Fibonacci Numbers
Category:Cassini's Identity
Cassini's Identity/Lemma

== Lemma for Cassini's Identity ==
:$\forall n \in \Z_{>1}: \begin{bmatrix}
F_{n + 1} & F_n \\
F_n & F_{n - 1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n$
== Proof ==
=== Basis for the Induction ===
:$\begin{bmatrix}
F_2 & F_1 \\
F_1 & F_0
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^1$
=== Induction Hypothesis ===
For $k \in \Z_{>1}$, it is assumed that:
:$\begin{bmatrix}
F_{k + 1} & F_k \\
F_k & F_{k - 1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^k$
It remains to be shown that:
:$\begin{bmatrix}
F_{k + 2} & F_{k + 1} \\
F_{k + 1} & F_k
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{k + 1}$
=== Induction Step ===
The induction step follows from conventional matrix multiplication:
So by induction:
:$\begin{bmatrix}
F_{n + 1} & F_n \\
F_n & F_{n - 1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n$
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $6$
Category:Cassini's Identity
Cassini's Identity/Negative Indices

== Theorem ==
Let $n \in \Z_{<0}$ be a negative integer.
Let $F_n$ be the $n$th Fibonacci number (as extended to negative integers).
Then Cassini's Identity:
:$F_{n + 1} F_{n - 1} - F_n^2 = \paren {-1}^n$
continues to hold.
== Proof ==
Let $n \in \Z_{> 0}$.
Then:
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $9$
Category:Cassini's Identity
Cassini's Identity/Proof 1

== Theorem ==
== Proof ==
We see that:
: $F_2 F_0 - F_1^2 = 1 \times 0 - 1 = -1 = \left({-1}\right)^1$
so the proposition holds for $n = 1$.
We also see that:
: $F_3 F_1 - F_2^2 = 2 \times 1 - 1 = \left({-1}\right)^2$
so the proposition holds for $n = 2$.
Suppose the proposition is true for $n = k$, that is:
: $F_{k + 1} F_{k - 1} - F_k^2 = \left({-1}\right)^k$
It remains to be shown that it follows from this that the proposition is true for $n = k + 1$, that is:
: $F_{k + 2} F_k - F_{k + 1}^2 = \left({-1}\right)^{k + 1}$
So:
By the Principle of Mathematical Induction, the proof is complete.
Note that from the above we have that:
: $F_{k + 2} F_k - F_{k + 1}^2 = \left({-1}\right)^{k + 1}$
from which:
: $F_{n + 1}^2 - F_n F_{n + 2} = \left({-1}\right)^n$
follows immediately.
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: $(4)$
Category:Cassini's Identity
Cassini's Identity/Proof 2

== Theorem ==
== Proof ==
First we use this :
Then the determinant of both sides is taken.
The follows directly from Determinant of Order 2:
:$\begin{bmatrix}
F_{n + 1} & F_n \\
F_n & F_{n - 1}
\end{bmatrix} = F_{n + 1} F_{n - 1} - F_n^2$
Now for the :
==== Basis for the Induction ====
:$\begin{vmatrix}
1 & 1 \\
1 & 0
\end{vmatrix} = 1 \times 0 - 1 \times 1 = -1 = \paren {-1}^1$
==== Induction Hypothesis ====
For $k \in \Z_{>0}$, it is assumed that:
:$\begin{vmatrix}
1 & 1 \\
1 & 0
\end{vmatrix}^k = \paren {-1}^k$
It remains to be shown that:
:$\begin{vmatrix}
1 & 1 \\
1 & 0
\end{vmatrix}^{k + 1} = \paren {-1}^{k + 1}$
==== Induction Step ====
The induction step follows from Determinant of Matrix Product:
:$\begin{vmatrix}
1 & 1 \\
1 & 0
\end{vmatrix}^{k+1} = \begin{vmatrix}
1 & 1 \\
1 & 0
\end{vmatrix}^k \begin{vmatrix}
1 & 1 \\
1 & 0
\end{vmatrix} = \paren {-1}^k \paren {-1} = \paren {-1}^{k + 1}$
Hence by induction:
:$\forall n \in \Z_{>0}: \begin{vmatrix}
1 & 1 \\
1 & 0
\end{vmatrix}^n = \paren {-1}^n$
== Sources ==
* : $\S 1.2.8$ Exercise $6$
* : $\S 1.2.8$: Fibonacci Numbers: $(5)$
Category:Cassini's Identity
Casting Out Nines

== Proof Technique ==
Casting out nines is a technique for checking that the result of an addition sum is correct.
Let $a$ and $b$ be two integers for which their sum:
:$c = a + b$
is to be calculated.
For each of $a$ and $b$, expressed in conventional decimal notation, the digital root is extracted.
These are added together, and the digital root of the result is extracted.
During this process, any occurrences of the digit $9$ can be cast out, as they have no effect on the digital root.
If that digital root of the sum of the digital roots of $a$ and $b$ do not match the digital root of $c$, it means something must have gone wrong with the addition.
== Proof ==
From Digital Root is Preserved by Addition:
:$\dr c = \dr {\dr a + \dr b}$
where $\dr a$ denotes the digital root of $a$.
Hence the result.
== Examples ==
== Historical Note ==
== Sources ==
* : $9$
* : $9$
* 
Category:Casting Out Nines
Category:9
Category:Number Theory
Casting Out Nines/Historical Note

== Historical Note on Casting Out Nines ==
The technique of Casting Out Nines was probably an invention of the mathematicians of early India.
It appears in 's , dating from about $1150$.
It arrived in Western Europe from the Arabs, via the of $1202$ by .
When initially invented, the technique involved dividing the numbers involved by $9$ and adding the remainders, but the summing of the digital roots has the same effect.
== Sources ==
* : $9$
* : $9$
* 
* : Chapter $3$: Notations and Numbers: Brahmagupta, Mahavira and Bhaskara
Category:Historical Notes
Catalan's Conjecture

== Theorem ==
The only solution to the Diophantine equation:
:$x^a - y^b = 1$
for $a, b > 1$ and $x, y > 0$, is:
:$x = 3, a = 2, y = 2, b = 3$
== Proof ==
== Also known as ==
== Also see ==
* Consecutive Integers which are Powers of 2 or 3: the special case where $x$ and $y$ are $2$ and $3$
* 1 plus Power of 2 is not Perfect Power except 9: the special case of $y = 2$.
* 1 plus Perfect Power is not Power of 2: the special case of $x = 2$.
* 1 plus Square is not Perfect Power: the special case of $b = 2$.
* 1 plus Perfect Power is not Prime Power except for 9: the special case where $x$ is prime.
== Historical Note ==
== Sources ==
* 
* 
* 
Category:Catalan's Conjecture
Category:Number Theory
Catalan's Conjecture/Historical Note

== Historical Note on Catalan's Conjecture ==
Catalan's Conjecture was first put forward by in $1844$.
The case where $x$ and $y$ are $2$ and $3$ was proved in $1344$ by .
A proof was finally published in $2004$ by .
== Also see ==
* Historical Note on Consecutive Integers which are Powers of 2 or 3
== Sources ==
* 
* 
* 
Category:Historical Notes
Catalan's Identity

== Theorem ==
Let $F_k$ be the $k$th Fibonacci number.
Then:
:${F_n}^2 - F_{n - r} F_{n + r} = \left({-1}\right)^{n - r} {F_r}^2$
== Proof 1 ==
== Proof 2 ==
== Also see ==
* Cassini's Identity, the special case of this where $r = 1$
Category:Fibonacci Numbers
Category:Catalan's Identity
Catalan's Identity/Proof 1

== Theorem ==
== Proof 1 ==
From the definition of Fibonacci numbers:
:$F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3$
By Honsberger's Identity:
:$F_n = F_{n - r} F_{r - 1} + F_{n - r + 1} F_r$
Also:
Therefore:
Category:Catalan's Identity
Catalan's Identity/Proof 2

== Theorem ==
== Proof ==
Proof by induction:
For all $n, r \in \N_{>0}$ where $n > r$, let $\map P {n, r}$ be the proposition:
:${F_n}^2 - F_{n - r} F_{n + r} = \paren {-1}^{n - r} {F_r}^2$
=== Basis for the Induction ===
$n = 1$ yields no suitable $r$, so we look at $n = 2$ instead, which only gives us $r = 1$.
$\map P {2, 1}$ is true:
:${F_2}^2 - F_3 F_1 = 1^2 - 2 \times 1 = -1 = -1 \times {F_1}^2$
$n = 3$ gives us only $r = 1$ and $r = 2$.
$\map P {3, 1}$ is true:
:${F_3}^2 - F_2 F_4 = 2^2 - 1 \times 3 = 1 = 1 \times {F_1}^2$
$\map P {3, 2}$ is true:
:${F_3}^2 - F_1 F_5 = 2^2 - 1 \times 5 = -1 = -1 \times {F_2}^2$
This is our basis for the induction.
=== First Induction Hypothesis ===
Now we need to show that, if $\map P {n, r}$ is true for all $r$, where $n > 3$, then it logically follows that $\map P {n + 1, r}$ is true for all $r$.
So this is our induction hypothesis:
:$\forall r < n : {F_n}^2 - F_{n - r} F_{n + r} = \paren {-1}^{n - r} {F_r}^2$
Then we need to show:
:$\forall r < n : {F_{n + 1} }^2 - F_{n - r + 1} F_{n + r + 1} = \paren {-1}^{n - r + 1} {F_r}^2$
=== Induction Step ===
This is our induction step:
It will again be a proof by induction.
==== Basis for the Induction ====
When $r = 1$:
So $\map P {n + 1, 1}$ holds.
This is our basis for the induction.
==== Second Induction Hypothesis ====
Now we need to show that, if $\map P {n + 1, r}$ is true, where $2 < r < n$, then it logically follows that $\map P {n + 1, r + 1}$ is true.
So this is our second induction hypothesis:
:${F_{n + 1} }^2 - F_{n - r + 1} F_{n + r + 1} = \paren {-1}^{n - r + 1} {F_r}^2$
Then we need to show:
:${F_{n + 1} }^2 - F_{n - r} F_{n + r + 2} = \paren {-1}^{n - r} {F_{r + 1} }^2$
==== Induction Step ====
This is our induction step:
So $\map P {n + 1, r} \implies \map P {n + 1, r + 1}$ and the result follows by the Principle of Mathematical Induction.
So $\map P {n, r} \implies \map P {n + 1, r}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$F_n^2 - F_{n - r} F_{n + r} = \paren {-1}^{n - r} {F_r}^2$
Category:Catalan's Identity
Catalan-Dickson Conjecture

== Unproven Conjecture ==
It has been conjectured that all aliquot sequences are bounded.
That is, all aliquot sequences end in one of the following ways:
:$(1): \quad$ It reaches $1$, the previous term being a prime number
:$(2): \quad$ It reaches a perfect number
:$(3): \quad$ It reaches a sociable chain, which may or may not be an amicable pair.
However, this is not known for certain.
== Also see ==
* Existence of Arbitrarily Long Aliquot Sequences
== Historical Note ==
== Sources ==
* 
* 
* : $276$
* : $276$
Category:Unproven Hypotheses
Category:Aliquot Sequences
Catalan-Dickson Conjecture/Historical Note

== Historical Note on Catalan-Dickson Conjecture ==
 first made this conjecture in $1888$, postulating that all aliquot sequences end in $1$ or a perfect number:
:Quelques théorèmes empiriques -- Le journal a publié, en décembre dernier, une Question proposée par M. Oltramare. Cette question m'a fait songer au théorème empirique suivant:
:$n$ étant un nombre entier, soit $n_1$, la somme des diviseurs de $n$, inférieurs à $n$, soit $n_2$ la somme des diviseurs de $n_1$ inférieurs a $n_1$; etc. Cela posé: les nombres $n$, $n_1$, $n_2$ tendent vers une limite $\lambda$, laquel le est $1$ ou un nombre parfait.
:Si cette proposition (vérifée sur divers exemples) est vraie, elle doit être fort difficile à démontrer.
This can be rendered in English as:
:Some empirical theorems -- the journal published, last December, a question posed by Mr. Oltramare. This question made me wonder about the following empirical theorem:
:Let $n$ be an integer, let $n_1$ be the sum of divisors of $n$ less than $n$, let $n_2$ be the sum of divisors of $n_1$ less than $n_1$, and so on. This has been suggested: the numbers $n$, $n_1$, $n_2$ tend to a limit $\lambda$ which is either $1$ or a perfect number.
:If this proposition (verified by various examples) is true, it would be very difficult to prove.
It was refined in $1913$ by to include the possibility of such a sequence ending in a sociable chain.
 independently came up with the concept of aliquot sequences in $1918$, and famously made the same conjecture:
 expresses the opinion, based on heuristic and experimental evidence, that there may exist some aliquot sequences which are unbounded.
 demonstrated that there exist aliquot sequences of arbitrary length which are monotonically increasing.
 has created such an aliquot sequence that increases for over $5000$ terms.
== Sources ==
* 
* : $276$
* : $276$
Category:Historical Notes
Catalan Number/Sequence

== Sequence of Catalan Numbers ==
The sequence of Catalan numbers begins:
:$(1,) \, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \ldots$
where the inclusion or not of the initial $1$ depends on whether $n$ starts from $0$ or $1$.
== Sources ==
* : $42$
* : $42$
* 
Category:Catalan Numbers