nyuuzyou/wikis huggingface dataset:
Factors of Sums of Powers of 100,000/General Result

== Theorem ==
All integers $n$ of the form:
:$n = \ds \sum_{k \mathop = 0}^m 10^{r k}$ for $m \in \Z_{> 0}$
are composite for $r \ge 2$.
The only exceptions are:
:$r = 2^k, m = 1$ for some $k \in \N$
:$r = m + 1 =$ some odd prime
in which cases $n$ may be prime.
== Proof ==
=== Case $1$: $m + 1$ is Composite ===
Suppose $m + 1$ is composite.
Then:
:$\exists p, q > 1: m + 1 = p q$
By Division Theorem, for each $k$ with $0 \le z \le m$:
:$\exists i, j \in \N: 0 \le i \le q - 1, \, 0 \le j \le p - 1: k = i + q j$
Thus:
Both sums are greater than $1$, so $n$ is composite.
=== Case $2$: $m + 1$ is an Odd Prime and $r \ne m + 1$ ===
Notice that: 
:$\ds \sum_{k \mathop = 0}^m 10^{r k} \times R_r = R_{r \paren {m + 1} }$
where $R_i$ is the $i$th repunit.
Suppose $m + 1$ and $r$ are coprime.
By Condition for Repunits to be Coprime, $R_{m + 1}$ and $R_r$ are coprime.
By Euclid's Lemma:
:$R_{m + 1} \divides \dfrac {R_{r \paren {m + 1} } } {R_r} = n$
Suppose $r^2 \divides m + 1$.
By Divisors of Repunit with Composite Index:
:$R_r \divides R_{r^2}$
and:
:$R_{r^2} \divides R_{r \paren {m + 1} }$
So we have:
:$\dfrac {R_{r^2}} {R_r} \divides \dfrac {R_{r \paren {m + 1} } } {R_r} = n$
=== Case $3$: $m = 1$, $r$ is not a Power of $2$ ===
We write $n = 1 + 10^r$.
Since $r$ is not a power of $2$, $r$ has an odd factor greater than $1$.
Write $r = x \paren {2 y + 1}$. 
Then:
By Sum of Two Odd Powers:
:$1 + 10^x$ is a factor of $1^{2 y + 1} + \paren {10^x}^{2 y + 1} = n$.
Thus all cases are covered.
Category:Factors of Sums of Powers of 100,000
Factors of Sums of Powers of 100,000/Historical Note

== Historical Note on Factors of Sums of Powers of 100,000 ==
According to in his of $1997$, this appears in , volume $5$, page $147$, and was attributed to Wilke (probably ).
However, examination of the archives of that magazine online does not corroborate this.
== Sources ==
* : $100,001$
Category:Historical Notes
Faithful Functor Reflects Monomorphisms

== Theorem ==
Let $\mathbf C$ and $\mathbf D$ be categories.
Let $F: \mathbf C \to \mathbf D$ be a faithful functor.
Let $x$ and $y$ be objects in $\mathbf C$.
Let $f: x \to y$ be a morphism in $\mathbf C$.
Let $\map F f : \map F x \to \map F y$ be a monomorphism in $\mathbf D$.
Then $f$ is a monomorphism in $\mathbf C$.
== Proof ==
Let $z$ be an object in $\mathbf C$.
Let $g: z \to x$ and $h: z \to x$ be morphisms in $\mathbf C$ such that $f \circ g = f \circ h$.
Hence $f$ is a monomorphism in $\mathbf C$.
Category:Category Theory
Fallacy/Examples/Arbitrary Example 1

== Example of Fallacy ==
is a fallacy.
== Proof ==
Let $x = y = z = 1$.
Then:
:$1 \ge 1$
which satisfies both $x \ge y$ and $y \ge z$, but it is not the case that:
:$1 > 1$
Hence the given argument is a fallacy.
== Sources ==
* 
Category:Examples of Fallacies
Fallacy of Every and All

== Fallacy ==
A statement containing both universal quantifiers and existential quantifiers has a different meaning if the order of the quantifiers is reversed.
To not recognize such a shift in meaning is to commit the Fallacy of Every and All.
== Counterexample ==
Proof by Counterexample:
Let $x$ and $y$ be natural numbers.
:$\forall x \, \exists y : x = y$: for every $x$ there is some $y$ such that $x$ equals $y$. 
Since $x = x$, this is true.
:$\exists y \, \forall x: x = y$: there is some $y$ such that for every $x$, $x$ equals $y$.
Since no natural number equals both $1$ and $2$ at the same time, this is false.
== Sources ==
* : $\S 11.5$, Appendix $B$: Every and All
Category:Fallacies
Category:Logic
Category:Named Theorems
Fallacy of Four Terms/Examples/Arbitrary Example 1

== Examples of Fallacy of Four Terms ==
The following is an example of the fallacy of four terms:
:$(1): \quad$ All metals are elements.
:$(2): \quad$ Brass is a metal.
:$(3): \quad$ Therefore, brass is an element.
== Resolution ==
It is common to refer to an alloy as an example of a metal.
That is how the word metal is used in $(2)$.
However, when used in $(1)$, the word metal is being used in its exclusive sense, that is, metals which are elements.
Hence there are $4$ terms in the syllogism:
:metal, in the true sense
:Chemical element
:Brass
:metal, in the sense which includes alloys.
== Sources ==
* 
Category:Examples of Fallacy of Four Terms
Fallacy of Generalisation

== Fallacy ==
Consider the argument:
... which can be epitomised by:
... which one has to admit seems plausible.
On the other hand, consider the argument:
... an example of which reasoning may be:
Well I don't know about you, but I've never been beaten at chess by an amoeba.
Such reasoning is referred to as a fallacy of generalisation.
== Resolution ==
When processing statements in natural language into predicate logic such as the above, the word most must be interpreted in the same way as some.
Category:Fallacies
Category:Predicate Logic
Fallacy of Undistributed Middle

== Fallacy ==
By Middle Term of Valid Categorical Syllogism is Distributed at least Once, the middle term of a valid categorical syllogism is distributed in at least one of the premises.
To express a syllogism where this rule is violated is to commit the fallacy of the undistributed middle.
== Sources ==
* : Chapter $4$: The Predicate Calculus $2$: $4$ The Syllogism: Exercises: $\text{A}$: Rules of Quantity: $2$: Footnote
Category:Categorical Syllogisms
Category:Fallacies
Falling Factorial as Quotient of Factorials

== Theorem ==
Let $x \in \Z_{\ge 0}$ be a positive integer.
Then:
:$x^{\underline n} = \dfrac {x!} {\paren {x - n}!} = \dfrac {\map \Gamma {x + 1} } {\map \Gamma {x - n + 1} }$ 
where:
:$x^{\underline n}$ denotes the $n$th falling factorial power of $x$.
:$\map \Gamma x$ denotes the Gamma function of $x$.
== Proof ==
== Also see ==
* Rising Factorial as Quotient of Factorials
== Sources ==
* : $\S 1.2.5$: Permutations and Factorials: $(21)$
Category:Falling Factorials
Category:Factorials
Falling Factorial of Complex Number as Summation of Unsigned Stirling Numbers of First Kind

== Theorem ==
Let $z \in \C$ be a complex number whose real part is positive.
Then:
:$z^{\underline r} = \ds \sum_{k \mathop = 0}^m{r \brack r - k} \paren {-1}^k z^{r - k} + \map \OO {z^{r - m - 1} }$
where:
:$\ds {r \brack r - k}$ denotes the extension of the unsigned Stirling numbers of the first kind to the complex plane
:$z^{\underline r}$ denotes $z$ to the $r$ falling
:$\map \OO {z^{r - m - 1} }$ denotes big-$\OO$ notation.
== Proof ==
== Historical Note ==
== Sources ==
* 
* : $\S 1.2.6$: Binomial Coefficients: $(60)$
Category:Falling Factorials
Category:Stirling Numbers
Category:Falling Factorial of Complex Number as Summation of Unsigned Stirling Numbers of First Kind
Falling Factorial of Sum of Integers

== Theorem ==
Let $r \in \R$ be a real number.
Let $a, b \in \Z$ be (positive) integers.
Then:
:$r^{\underline {a + b} } = r^{\underline a} \paren {r - a}^{\underline b}$
where $r^{\underline a}$ denotes the $a$th falling factorial of $r$.
== Proof ==
Category:Falling Factorials
False Balance Problem

== Classic Problem ==
:A Cheshire cheese being put into one of the pans of a false balance,
:was found to weigh $16$ pounds,
:and when put into the other pan only $9$ pounds.
:What is the true weight?
== Solution ==
$12$ pounds.
== Proof ==
It is assumed that the reason for the falseness of this balance is that its arms are of unequal lengths.
Let $W$ pounds be the true weight.
Let the arms of the balance be $p$ and $q$.
From True Weight from False Balance with Unequal Arms:
:$W = \sqrt {p q}$
Thus we have:
== Sources ==
* 
* : Rational Amusements for Winter Evenings: $154$
Category:False Balances
False Statement implies Every Statement

== Theorem ==
If something is false, then it implies anything.
==== Formulation 1 ====
==== Formulation 2 ====
== Examples ==
== Also see ==
* Paradoxes of Material Implication, in which category this result is grouped
== Sources ==
* : $\S \text{II}.8$: Implication or Conditional Sentence
* : $\S 2.3$: Basic Truth-Tables of the Propositional Calculus
* : $2$ Arguments Containing Compound Statements: $2.2$: Conditional Statements
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic
* 
* 
Category:False Statement implies Every Statement
Category:Paradoxes of Material Implication
Category:Conditional
False Statement implies Every Statement/Examples/Dilbert

== Example of False Statement implies Every Statement ==
The apparent paradox False Statement implies Every Statement can perhaps be intellectually reconciled by considering the figure of speech in natural language: 
:If Dilbert passes his Practical Management exam I'll eat my hat.
That is, if statement $p$ is so absurdly improbable as to be a falsehood for all practical purposes, then it can imply an even more absurdly improbable conclusion $q$.
Category:Paradoxes of Material Implication
False Statement implies Every Statement/Formulation 1/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, where the truth value in the relevant column on the is $\T$, that under the one on the is also $\T$:
$\begin{array}{|cc||ccc|} \hline
\neg & p & p & \implies & q \\
\hline
\T & \F & \F & \T & \F \\
\T & \F & \F & \T & \T \\
\F & \F & \T & \F & \F \\
\F & \F & \T & \T & \T \\
\hline
\end{array}$
Category:False Statement implies Every Statement
Category:Truth Table Proofs
False Statement implies Every Statement/Formulation 2

== Theorem ==
:$\vdash \neg p \implies \paren {p \implies q}$
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S \text{II}.13$: Symbolism of sentential calculus
* : $\text{I}$: 'NOT' and 'IF': $\S 5$: Theorem $\text{T18}$
* : $2$ Arguments Containing Compound Statements: $2.4$: Statement Forms
Category:False Statement implies Every Statement
Family of Curves/Examples/Circles in Plane

== Example of Family of Curves ==
Consider the equation:
:$(1): \quad \paren {x - h}^2 + \paren {y - k}^2 = a^2$
$(1)$ defines a family of circles:
:whose radii are determined by the parameter $a$
:whose centers are at $\tuple {h, k}$ on Cartesian plane, determined by values of the parameters $h$ and $k$.
Hence $(1)$ represents the family of all circles in the plane.
== Sources ==
* 
* 
Category:Examples of Families of Curves
Family of Curves/Examples/Circles with Centers along x-Axis

== Example of Family of Curves ==
Consider the equation:
:$(1): \quad \paren {x - h}^2 + y^2 = a^2$
where $x, y, a, h \in \R$.
$(1)$ defines a family of circles:
:whose radii are determined by the parameter $a$
:whose centers are on the $x$-axis of a Cartesian plane at $\tuple {h, 0}$ determined by values of the parameter $h$.
== Sources ==
* 
* 
Category:Examples of Families of Curves
Family of Lipschitz Continuous Functions with same Lipschitz Constant is Uniformly Equicontinuous

== Theorem ==
Let $\struct {X, d}$ and $\struct {Y, d'}$ be metric spaces. 
Let $\map \CC {X, Y}$ be the set of continuous functions $X \to Y$.
Let $\FF \subset \map \CC {X, Y}$ be a set of Lipschitz continuous functions all with Lipschitz constant $M \ge 0$.
Then $\FF$ is uniformly equicontinuous.
== Proof ==
Note that for each $f \in \FF$, we have: 
:$\map {d'} {\map f x, \map f y} \le M \map d {x, y}$
for each $x, y \in X$.
Note that if $M = 0$, we have: 
:$\map {d'} {\map f x, \map f y} = 0$
for each $f \in \FF$ and $x, y \in X$. 
That is: 
:$\map {d'} {\map f x, \map f y} < \epsilon$
for each $\epsilon > 0$, $f \in \FF$ and $x, y \in X$. 
So $\FF$ is uniformly equicontinuous in this case.
Suppose now that $M > 0$. 
Note that whenever: 
:$\ds \map d {x, y} < \frac \epsilon M$
we have: 
for each $f \in \FF$.
So $\FF$ is uniformly equicontinuous.
Category:Uniform Equicontinuity
Farey Sequence/Examples/Order 5

== Example of Farey Sequence ==
The Farey sequence $F_5$ of order $5$ is:
:$\dfrac 0 1, \dfrac 1 5, \dfrac 1 4, \dfrac 1 3, \dfrac 2 5, \dfrac 1 2, \dfrac 3 5, \dfrac 2 3, \dfrac 3 4, \dfrac 4 5, \dfrac 1 1$
== Sources ==
* 
* 
Category:Examples of Farey Sequences
Farey Sequence has Convergent Subsequences for all x in Closed Unit Interval

== Theorem ==
Consider the Farey sequence:
:$\sequence {a_n} = \dfrac 1 2, \dfrac 1 3, \dfrac 2 3, \dfrac 1 4, \dfrac 2 4, \dfrac 3 4, \dfrac 1 5, \dfrac 2 5, \dfrac 3 5, \dfrac 4 5, \dfrac 1 6, \ldots$
Every element of the closed real interval $\closedint 0 1$ is the limit of a subsequence of $\sequence {a_n}$.
== Proof ==
We have that every rational number $\dfrac p q$ between $0$ and $1$ occurs infinitely often in $\sequence {a_n}$:
:$\dfrac p q, \dfrac {2 p} {2 q}, \dfrac {3 p} {3 q}, \ldots$
Let $x \in \closedint 0 1$.
From Between two Real Numbers exists Rational Number, a term $a_{n_1}$ of $\sequence {a_n}$ can be found such that:
:$x - 1 < a_{n_1} < x + 1$
Then a term $a_{n_2}$ of $\sequence {a_n}$ such that $n_2 > n_1$ can be found such that:
:$x - \dfrac 1 2 < a_{n_2} < x + \dfrac 1 2$
Hence we can create a subsequence $\sequence {a_{n_k} }$ such that:
:$x - \dfrac 1 k < a_{n_k} < x + \dfrac 1 k$
and so by the Squeeze Theorem for Real Sequences:
:$r_{n_k} \to x$ as $k \to \infty$
== Sources ==
* : $\S 5$: Subsequences: Lim sup and lim inf: Exercise $\S 5.15 \ (2)$
Category:Farey Sequences
Category:Subsequences
Category:Limits of Sequences
Farey Sequence is not Convergent

== Theorem ==
Consider the Farey sequence:
:$F = \dfrac 1 2, \dfrac 1 3, \dfrac 2 3, \dfrac 1 4, \dfrac 2 4, \dfrac 3 4, \dfrac 1 5, \dfrac 2 5, \dfrac 3 5, \dfrac 4 5, \dfrac 1 6, \ldots$
$F$ is not convergent.
== Proof ==
We have the following subsequences of $F$ which are all convergent to a different limit:
:$\dfrac 1 2, \dfrac 2 4, \dfrac 3 6, \dfrac 4 8 \to \dfrac 1 2$ as $n \to \infty$
:$\dfrac 1 2, \dfrac 1 3, \dfrac 1 4, \dfrac 1 5 \to 0$ as $n \to \infty$
:$\dfrac 1 2, \dfrac 2 3, \dfrac 3 4, \dfrac 4 5 \to 1$ as $n \to \infty$
It follows from Limit of Subsequence equals Limit of Real Sequence that $F$ cannot be convergent.
== Sources ==
* : $\S 5$: Subsequences: Bolzano-Weierstrass Theorem: $\S 5.12$: Example $\text{(ii)}$
Category:Farey Sequences
Category:Divergent Sequences
Fatou's Lemma for Integrals

== Theorem ==
Let $\struct {X, \Sigma, \mu}$ be a measure space.
=== Positive Measurable Functions ===
=== Integrable Functions ===
== Also see ==
* Reverse Fatou's Lemma
Category:Fatou's Lemma for Integrals
Category:Measure Theory
Category:Fatou's Lemma
Fatou's Lemma for Integrals/Integrable Functions

== Theorem ==
Let $\struct {X, \Sigma, \mu}$ be a measure space.
Let $\sequence {f_n}_{n \mathop \in \N} \in \LL^1$, $f_n: X \to \R$ be a sequence of $\mu$-integrable functions.
Let $\ds \liminf_{n \mathop \to \infty} f_n: X \to \overline \R$ be the pointwise limit inferior of the $f_n$.
Suppose that there exists an $\mu$-integrable $f: X \to \R$ such that for all $n \in \N$, $f \le f_n$ pointwise.
Then:
:$\ds \int \liminf_{n \mathop \to \infty} f_n \rd \mu \le \liminf_{n \mathop \to \infty} \int f_n \rd \mu$
where:
:the integral sign denotes $\mu$-integration
:the limit inferior is taken in the extended real numbers $\overline \R$.
== Proof ==
== Sources ==
* : $\S 10$: Problem $10.8 \ \text{(i)}$
Category:Fatou's Lemma for Integrals
Category:Measure Theory
Fatou's Lemma for Integrals/Positive Measurable Functions

== Theorem ==
Let $\struct {X, \Sigma, \mu}$ be a measure space.
Let $\sequence {f_n}_{n \mathop \in \N} \in \MM_{\overline \R}^+$, $f_n: X \to \overline \R$ be a sequence of positive measurable functions.
Let $\ds \liminf_{n \mathop \to \infty} f_n: X \to \overline \R$ be the pointwise limit inferior of the $f_n$.
Then:
:$\ds \int \liminf_{n \mathop \to \infty} f_n \rd \mu \le \liminf_{n \mathop \to \infty} \int f_n \rd \mu$
where:
:the integral sign denotes $\mu$-integration
:the limit inferior is taken in the extended real numbers $\overline \R$.
== Proof ==
For each $n \in \N$, define $g_n : X \to \overline \R$ by: 
:$\ds g_n = \inf_{k \mathop \ge n} f_k$
That is: 
:$\map {g_n} x = \inf \set {\map {f_k} x : k \ge n}$
for each $x \in X$. 
For each $n \in \N$, we have that: 
:$\set {\map {f_k} x : k \ge n + 1} \subseteq \set {\map {f_k} x : k \ge n}$
From Infimum of Subset: 
:$\inf \set {\map {f_k} x : k \ge n + 1} \ge \inf \set {\map {f_k} x : k \ge n}$
That is: 
:$\map {g_{n + 1} } x \ge \map {g_n} x$
for each $n \in \N$. 
From Pointwise Infimum of Measurable Functions is Measurable, we also have: 
:$g_n$ is $\Sigma$-measurable for each $n \in \N$. 
We have: 
:$\ds \lim_{n \mathop \to \infty} g_n = \lim_{n \mathop \to \infty} \paren {\inf_{k \mathop \ge n} f_k}$
By the definition of limit inferior: 
:$\ds \lim_{n \mathop \to \infty} g_n = \liminf_{n \mathop \to \infty} f_n$
So:
:$\sequence {g_n}_{n \mathop \in \N}$ is an increasing sequence of $\Sigma$-measurable functions convergent to $\ds \liminf_{n \mathop \to \infty} f_n$.
We are therefore able to apply the monotone convergence theorem.
We then have:: 
Clearly we have: 
:$\ds \inf_{k \mathop \ge n} f_k \le f_n$
for any $n \in \N$. 
So, by Integral of Integrable Function is Monotone: 
:$\ds \int \paren {\inf_{k \mathop \ge n} f_k} \rd \mu \le \int f_n \rd \mu$ 
and so: 
:$\ds \int \paren {\inf_{k \mathop \ge n} f_k} \rd \mu \le \inf_{k \mathop \ge n} \int f_k \rd \mu$ 
Then: 
== Also see ==
* Reverse Fatou's Lemma/Positive Measurable Functions
== Sources ==
* : $9.11$
* : $2.4$: Limit Theorems: Theorem $2.4.4$
Category:Measure Theory
Category:Fatou's Lemma for Integrals
Fatou's Lemma for Measures

== Theorem ==
Let $\struct {X, \Sigma, \mu}$ be a measure space.
Let $\sequence {E_n}_{n \mathop \in \N} \in \Sigma$ be a sequence of $\Sigma$-measurable sets.
Then:
:$\ds \map \mu {\liminf_{n \mathop \to \infty} E_n} \le \liminf_{n \mathop \to \infty} \map \mu {E_n}$
where:
:$\ds \liminf_{n \mathop \to \infty} E_n$ is the limit inferior of the $E_n$
:the limit inferior is taken in the extended real numbers $\overline \R$.
=== Corollary ===
== Proof ==
== Sources ==
* : $\S 9$: Problem $9 \ \text{(ii)}$
Category:Measure Theory
Category:Fatou's Lemma
Category:Fatou's Lemma for Measures
Fatou's Lemma for Measures/Corollary

== Corollary to Fatou's Lemma for Measures ==
Let $\struct {X, \Sigma, \mu}$ be a measure space.
Let $\sequence {E_n}_{n \mathop \in \N} \in \Sigma$ be a sequence of $\Sigma$-measurable sets.
Let $\mu$ be a finite measure.
Then:
:$\ds \map \mu {\limsup_{n \mathop \to \infty} E_n} \le \limsup_{n \mathop \to \infty} \map \mu {E_n}$
where:
:$\ds \limsup_{n \mathop \to \infty} E_n$ is the limit superior of the $E_n$
:the limit superior is taken in the extended real numbers $\overline \R$.
== Proof ==
== Examples ==
== Sources ==
* : $\S 9$: Problem $9 \ \text{(iii)}$
Category:Fatou's Lemma for Measures
Fatou's Lemma for Measures/Corollary/Examples/Union of Disjoint Real Intervals

== Example of Use of Corollary to Fatou's Lemma for Measures ==
Letting $E_n = \openint n {n + 1}$.
Since the $E_n$ are pairwise disjoint, the definition of limit superior gives:
:$\ds \limsup_{n \mathop \to \infty} E_n = \O$
By Measure of Interval is Length, we also have:
:$\map \mu {E_n} = 1$
for all $n \in \N$.
Thus:
:$0 = \ds \map \mu {\limsup_{n \mathop \to \infty} E_n} < \limsup_{n \mathop \to \infty} \map \mu {E_n} = \limsup_{n \mathop \to \infty} 1 = 1$
Category:Fatou's Lemma for Measures
Faulhaber's Formula

== Theorem ==
Let $n, p \in \Z_{>0}$ be (strictly) positive integers.
Then:
where:
:$B_i$ denotes the $i$th Bernoulli number.
== Proof ==
Let $x \ge 0$.
We also have:
Equating coefficients:
== Also presented as ==
== Sources ==
* : $\S 19$: Sums of Powers of Positive Integers: $19.8$
* : $\S 21$: Series of Constants: Sums of Powers of Positive Integers: $21.8.$
Category:Faulhaber's Formula
Category:Bernoulli Numbers
Category:Sums of Sequences
Category:Number Theory
Faulhaber's Formula/Also presented as

== Faulhaber's Formula: Also presented as == 
Faulhaber's formula can also be expressed using the archaic form of the Bernoulli numbers as:
== Sources ==
* : $\S 19$: Sums of Powers of Positive Integers: $19.8$
* : $\S 21$: Series of Constants: Sums of Powers of Positive Integers: $21.8.$
Category:Faulhaber's Formula
Faà di Bruno's Formula

== Theorem ==
Let $D_x^k u$ denote the $k$th derivative of a function $u$ $x$.
Then:
:$\ds D_x^n w = \sum_{j \mathop = 0}^n D_u^j w \sum_{\substack {\sum_{p \mathop \ge 1} k_p \mathop = j \\ \sum_{p \mathop \ge 1} p k_p \mathop = n \\ \forall p \mathop \ge 1: k_p \mathop \ge 0} } n! \prod_{m \mathop = 1}^n \dfrac {\paren {D_x^m u}^{k_m} } {k_m! \paren {m!}^{k_m} }$
== Examples ==
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Proof 4 ==
== Also known as ==
Some sources refer to this as Arbogast's formula for who actually deduced this first.
== Historical Note ==
Category:Differential Calculus
Category:Faà di Bruno's Formula
Faà di Bruno's Formula/Example/0/Proof

== Theorem ==
Consider Faà di Bruno's Formula:
When $n = 0$ we have:
== Proof ==
In the summation:
:$\ds \sum_{j \mathop = 0}^0 D_u^j w \sum_{\substack {\sum_{p \mathop \ge 0} k_p \mathop = j \\ \sum_{p \mathop \ge 0} p k_p \mathop = 0 \\ \forall p \ge 0: k_p \mathop \ge 0} } 0! \prod_{m \mathop = 0}^1 \dfrac {\paren {D_x^m u}^{k_m} } {k_m! \paren {m!}^{k_m} }$
the only element appearing is for $j = 0$, and the continued product is vacuous.
Thus:
:$\ds \prod_{m \mathop = 0}^1 \dfrac {\paren {D_x^m u}^{k_m} } {k_m! \paren {m!}^{k_m} } = 1$
and we are left with:
Category:Faà di Bruno's Formula
Faà di Bruno's Formula/Example/1/Proof

== Theorem ==
Consider Faà di Bruno's Formula:
When $n = 1$ we have:
== Proof ==
In the summation:
:$\ds \sum_{j \mathop = 0}^1 D_u^j w \sum_{\substack {\sum_{p \mathop \ge 1} k_p \mathop = j \\ \sum_{p \mathop \ge 1} p k_p \mathop = 1 \\ \forall p \ge 1: k_p \mathop \ge 0} } 1! \prod_{m \mathop = 1}^1 \dfrac {\paren {D_x^m u}^{k_m} } {k_m! \paren {m!}^{k_m} }$
we need to consider $j = 0$ and $j = 1$.
Let $j = 0$.
Consider the set of $k_p$ such that:
:$k_1 + k_2 + \cdots = 0$
:$1 \times k_1 + 2 k_2 + \cdots = 1$
:$k_1, k_2, \ldots \ge 0$
It is apparent by inspection that no set of $k_p$ can fulfil these conditions.
Therefore when $j = 0$ the summation is vacuous
Let $j = 1$.
Consider the set of $k_p$ such that:
:$k_1 + k_2 + \cdots = 1$
:$1 \times k_1 + 2 k_2 + \cdots = 1$
:$k_1, k_2, \ldots \ge 0$
By inspection, it is seen that these can be satisfied only by:
:$k_1 = 1$
and all other $k_p = 0$.
When $k_m = 0$:
:$\dfrac {\paren {D_x^m u}^{k_m} } {k_m! \paren {m!}^{k_m} } = 1$
by definition of zeroth derivative and factorial of $0$.
Thus any contribution to the summation where $k_m = 0$ can be disregarded.
Thus we have:
Category:Faà di Bruno's Formula
Faà di Bruno's Formula/Example/2

== Example of use of Faà di Bruno's Formula: $n = 2$ ==
Consider Faà di Bruno's Formula:
When $n = 2$ we have:
:$D_x^2 w = D_u^2 w \paren {D_x^1 u}^2 + D_u^1 w D_x^2 u$
== Proof ==
Category:Faà di Bruno's Formula
Faà di Bruno's Formula/Example/2/Proof

== Theorem ==
Consider Faà di Bruno's Formula:
When $n = 2$ we have:
== Proof ==
In the summation:
:$\ds \sum_{j \mathop = 0}^2 D_u^j w \sum_{\substack {\sum_{p \mathop \ge 1} k_p \mathop = j \\ \sum_{p \mathop \ge 1} p k_p \mathop = 2 \\ \forall p \ge 1: k_p \mathop \ge 0} } 2! \prod_{m \mathop = 1}^2 \dfrac {\left({D_x^m u}\right)^{k_m} } {k_m! \paren {m!}^{k_m} }$
we need to consider $j = 0, j = 1$ and $j = 2$.
Note that when $k_m = 0$:
:$\dfrac {\paren {D_x^m u}^{k_m} } {k_m! \paren {m!}^{k_m} } = 1$
by definition of zeroth derivative and factorial of $0$.
Thus any contribution to the summation where $k_m = 0$ can be disregarded.
Let $j = 0$.
Consider the set of $k_p$ such that:
:$k_1 + k_2 + \cdots = 0$
:$1 \times k_1 + 2 k_2 + \cdots = 2$
:$k_1, k_2, \ldots \ge 0$
It is apparent by inspection that no set of $k_p$ can fulfil these conditions.
Therefore when $j = 0$ the summation is vacuous
Let $j = 1$.
Consider the set of $k_p$ such that:
:$k_1 + k_2 + \cdots = 1$
:$1 \times k_1 + 2 k_2 + \cdots = 2$
:$k_1, k_2, \ldots \ge 0$
By inspection, it is seen that these can be satisfied only by:
:$k_2 = 1$
and all other $k_p = 0$.
Let $j = 2$.
Consider the set of $k_p$ such that:
:$k_1 + k_2 + \cdots = 2$
:$1 \times k_1 + 2 k_2 + \cdots = 2$
:$k_1, k_2, \ldots \ge 0$
By inspection, it is seen that these can be satisfied only by:
:$k_1 = 2$
and all other $k_p = 0$.
Thus we have:
Category:Faà di Bruno's Formula