nyuuzyou/wikis huggingface dataset:
Sum of Discrete Random Variables

== Theorem ==
Let $X$ and $Y$ be discrete random variables on the probability space $\struct {\Omega, \Sigma, \Pr}$.
Let $U: \Omega \to \R$ be defined as:
:$\forall \omega \in \Omega: \map U \omega = \map X \omega + \map Y \omega$
Then $U$ is also a discrete random variable on $\struct {\Omega, \Sigma, \Pr}$.
== Proof ==
To show that $U$ is discrete random variable on $\struct {\Omega, \Sigma, \Pr}$, we need to show that:
:$(1): \quad$ The image of $U$ is a countable subset of $\R$;
:$(2): \quad \forall x \in \R: \set {\omega \in \Omega: \map U \omega = x} \in \Sigma$.
First we consider any $U_u = \set {\omega \in \Omega: \map U \omega = u}$ such that $U_u \ne \O$.
We have that $U_u = \set {\omega \in \Omega: \map X \omega + \map Y \omega = u}$.
Consider any $\omega \in U_u$.
Then:
:$\omega \in X_x \cap Y_x$
where:
:$X_x = \set{\omega \in \Omega: \map X \omega = x}, Y_x = \set {\omega \in \Omega: \map Y \omega = u - x}$
Because $X$ and $Y$ are discrete random variables, both $X_x \in \Sigma$ and $Y_x \in \Sigma$.
As $\struct {\Omega, \Sigma, \Pr}$ is a probability space, then $X_x \cap Y_x \in \Sigma$.
Now note that:
:$\ds U_u = \bigcup_{x \mathop \in \R} \paren {X_x \cap Y_x}$
That is, it is the union of all such intersections of sets whose discrete random variables add up to $u$.
As $X_x$ is a countable set it follows that $U_u$ is a countable union of countable sets.
From Countable Union of Countable Sets is Countable it follows that $X_x$ is a countable set.
And, by dint of $\struct {\Omega, \Sigma, \Pr}$ being a probability space, $U_u \in \Sigma$.
Thus $U$ is a discrete random variables on $\struct {\Omega, \Sigma, \Pr}$.
== Sources ==
* : $\S 2.1$: Probability mass functions: Exercise $1$
Category:Discrete Random Variables
Sum of Elements in Inverse of Cauchy Matrix

== Theorem ==
Let $C_n$ be the Cauchy matrix of order $n$ given by:
:$C_n = \begin{bmatrix}
\dfrac 1 {x_1 + y_1} & \dfrac 1 {x_1 + y_2 } & \cdots & \dfrac 1 {x_1 + y_n} \\
\dfrac 1 {x_2 + y_1} & \dfrac 1 {x_2 + y_2 } & \cdots & \dfrac 1 {x_2 + y_n} \\
\vdots & \vdots & \ddots & \vdots \\
\dfrac 1 {x_m + y_1} & \dfrac 1 {x_m + y_2 } & \cdots & \dfrac 1 {x_m + y_n} \\
\end{bmatrix}$
Let $C_n^{-1}$ be its inverse, from Inverse of Cauchy Matrix:
:$b_{i j} = \dfrac {\ds \prod_{k \mathop = 1}^n \paren {x_j + y_k} \paren {x_k + y_i} } {\ds \paren {x_j + y_i} \paren {\prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } \paren {\prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne i} } \paren {y_i - x_k} } }$
The sum of all the elements of $C_n^{-1}$ is:
:$\ds \sum_{1 \mathop \le i, \ j \mathop \le n} b_{i j} = \sum_{k \mathop = 1}^n x_k + \sum_{k \mathop = 1}^n y_k$
== Proof ==
It suffices to prove the Theorem for Cauchy matrix:
 
The sum $S$ of elements in $C^{-1}$ will be shown to be a scalar product of two vectors $\vec A$ and $\vec B$.
The statement of the theorem is obtained by replacing $y_k \to -y_k$ in $C$ and in the sum $S$.
Let:
The sum $S$ of elements in $C^{-1}$ is the matrix product:
To identify vectors $\vec A$ and $\vec B$, the tool is:
Definitions of symbols:
Compute the sum $S$:
Define vectors $\vec A$ and $\vec B$:
Compute $\vec A$:
Then $\vec A$ uniquely solves the problem 
The two polynomials
have coefficients expressed by symmetric functions:
Solve in equation $\map q {y_j} = 0$ for highest power $y_j^n$ and replace in the equation for $\map p {y_j}$:
Vector $\begin {pmatrix} \map p {y_1} \\ \vdots \\ -\map p {y_n} \\ \end {pmatrix}$ is a linear combination of the column vectors of matrix $V_y^T$ with weights (coefficients) $b_i - a_i$.
Then:
Compute $\vec B$:
Evaluate $S$:
 
 
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $44$
Category:Cauchy Matrices
Category:Summations
Category:Continued Products
Category:Summation of Powers over Product of Differences
Sum of Elements in Inverse of Combinatorial Matrix

== Theorem ==
Let $C_n$ be the combinatorial matrix of order $n$ given by:
:$C_n = \begin{bmatrix}
x + y & y & \cdots & y \\
y & x + y & \cdots & y \\
\vdots & \vdots & \ddots & \vdots \\
y & y & \cdots & x + y
\end{bmatrix}$
Let $C_n^{-1}$ be its inverse, from Inverse of Combinatorial Matrix:
:$b_{i j} = \dfrac {-y + \delta_{i j} \paren {x + n y} } {x \paren {x + n y} }$
where $\delta_{i j}$ is the Kronecker delta.
The sum of all the elements of $C_n^{-1}$ is:
:$\ds \sum_{1 \mathop \le i, \ j \mathop \le n} b_{i j} = \dfrac n {x + n y}$
== Proof ==
All $n^2$ elements of $C_n^{-1}$ have a term $\dfrac {-y} {x \paren {x + n y} }$.
Further to this, the $n$ elements on the main diagonal contribute an extra $\dfrac {x + n y} {x \paren {x + n y} }$ to the total.
Hence:
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $42$
Category:Combinatorial Matrix
Sum of Elements in Inverse of Hilbert Matrix

== Theorem ==
Let $H_n$ be the Hilbert matrix of order $n$:
:$\begin{bmatrix} a_{i j} \end{bmatrix} = \begin{bmatrix} \dfrac 1 {i + j - 1} \end{bmatrix}$
Consider its inverse $H_n^{-1}$.
All the elements of $H_n^{-1}$ are integers.
The sum of all the elements $b_{i j}$ of $H_n^{-1}$ is:
:$\ds \sum_{1 \mathop \le i, \ j \mathop \le n} b_{i j} = n^2$
== Proof ==
From Hilbert Matrix is Cauchy Matrix, $H_n$ is a special case of a Cauchy matrix:
:$\begin{bmatrix} c_{i j} \end{bmatrix} = \begin{bmatrix} \dfrac 1 {x_i + y_j} \end{bmatrix}$
where:
:$x_i = i$
:$y_j = j - 1$
Then:
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $45$
Category:Hilbert Matrices
Sum of Elements in Inverse of Vandermonde Matrix

== Theorem ==
Let $V_n$ be the Vandermonde matrix of order $n$ given by:
:$V_n = \begin{pmatrix}
 x_1 & x_2 & \cdots & x_n \\
 x_1^2 & x_2^2 & \cdots & x_n^2 \\
\vdots & \vdots & \ddots & \vdots \\
 x_1^n & x_2^n & \cdots & x_n^n
\end{pmatrix}$
Let $V_n^{-1}$ be its inverse, from Inverse of Vandermonde Matrix:
:$b_{i j} = \begin {cases}
\paren {-1}^{j - 1} \paren {\dfrac {\ds \sum_{\substack {1 \mathop \le m_1 \mathop < \ldots \mathop < m_{n - j} \mathop \le n \\ m_1, \ldots, m_{n - j} \mathop \ne i} } x_{m_1} \cdots x_{m_{n - j} } } {x_i \ds \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne i} } \paren {x_m - x_i} } } & : 1 \le j < n \\
\qquad \qquad \qquad \dfrac 1 {x_i \ds \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne i} } \paren {x_i - x_m} } & : j = n
\end{cases}$
The sum of all the elements of $V_n^{-1}$ is:
:$\ds \sum_{1 \mathop \le i, \ j \mathop \le n} b_{i j} = 1 - \prod_{k \mathop = 1}^n \paren {1 - \dfrac 1 {x_k} }$
== Proof ==
From Sum of Elements of Nonsingular Matrix, the sum of elements in $V_n^{-1}$ is:
:$1 - \map \det {V_n^{-1} } \map \det {V_n - J_n}$
The plan is to expand $\map \det {V_n - J_n}$ and simplify.
The method is efficiently communicated in the $3 \times 3$ case:
The proof is completed by induction using the lemmas below.
=== Lemma 1 ===
Let:
:$A_n = \det \begin {pmatrix}
1 & \cdots & 1 \\
x_1 & \cdots & x_n \\
\vdots & \cdots & \vdots \\
x_1^{n - 1} & \cdots & x_n^{n - 1} \\
\end {pmatrix}$ 
Then from Effect of Elementary Row Operations on Determinant:
:$\ds \map \det {V_n} = \paren {\prod_{k \mathop = 1}^n x_k} \map \det {A_n}$
=== Lemma 2 ===
:$\ds \map \det {V_n - J_n} = \prod_{k \mathop = 1}^n \paren {x_k - 1} \map \det {A_n}$
=== Lemma 3 ===
By Lemmas 1 and 2:
:$\ds \map \det {V_n^{-1} } \map \det {V_n - J_n} = \dfrac {\ds \prod_{k \mathop = 1}^n \paren {x_k - 1} } {\ds \prod_{k \mathop = 1}^n x_k}$
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $43$
Category:Vandermonde Matrices
Sum of Elements of Inverse of Matrix with Column of Ones

== Theorem ==
Let $\mathbf B = \sqbrk b_n$ denote the inverse of a square matrix $\mathbf A$ of order $n$.
Let $\mathbf A$ be such that it has a row or column of all ones.
Then the sum of elements in $\mathbf B$ is one:
:$\ds \sum_{i \mathop = 1}^n \sum_{j \mathop = 1}^n b_{ij} = 1$
== Proof ==
If ones appear in a row of $\mathbf A$, then replace $\mathbf A$ by $\mathbf A^T$ and $\mathbf B$ by $\mathbf B^T$.
Assume $\mathbf A$ has a column of ones.
Apply Sum of Elements of Nonsingular Matrix to the inverse $\mathbf B = \mathbf A^{-1}$:
:$\ds \sum_{i \mathop = 1}^n \sum_{j \mathop = 1}^n b_{i j} = 1 - \map \det {\mathbf B} \map \det {\mathbf B^{-1} - \mathbf J_n}$
where $\mathbf J_n$ denotes the square ones matrix of order $n$.
If $\mathbf A = \mathbf B^{-1}$ has a column of ones, then $\mathbf B^{-1} - \mathbf J_n$ has a column of zeros, implying determinant zero.
Substitute $\map \det {\mathbf B^{-1} - \mathbf J_n} = 0$ in Sum of Elements of Nonsingular Matrix:
:$\ds \sum_{i \mathop = 1}^n \sum_{j \mathop = 1}^n b_{i j} = 1 - 0$
which implies the statement.
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $43$ (solution)
Category:Inverse Matrices
Sum of Elements of Nonsingular Matrix

== Theorem ==
Let $\mathbf J_n$ be the $n \times n$ square ones matrix.
Let $\mathbf B$ be an $n \times n$ nonsingular matrix with entries $b_{i j}$, $1 \le i, j \le n$.
Then:
:$\ds \sum_{i \mathop = 1}^n \sum_{j \mathop = 1}^n b_{i j} = 1 - \map \det {\mathbf B} \map \det {\mathbf B^{-1} - \mathbf J_n}$
== Proof ==
=== Lemma ===
Let$\mathbf J_n$ be the $n \times n$ square ones matrix.
Let $\mathbf A$ be an $n \times n$ matrix.
Let $\mathbf A_{ij}$ denote the cofactor of element $a_{ij}$ in $\map \det {\mathbf A}$, $1 \le i, j \le n$.
Then:
Let $\mathbf A = \mathbf B^{-1}$.
Then:
Then:
Category:Nonsingular Matrices
Sum of Entries in Lesser Diagonal of Pascal's Triangle equal Fibonacci Number

== Theorem ==
The sum of the entries in the $n$th lesser diagonal of Pascal's triangle equals the $n + 1$th Fibonacci number.
== Proof ==
By definition, the entries in the $n$th lesser diagonal of Pascal's triangle are:
:$\dbinom n 0, \dbinom {n - 1} 1, \dbinom {n - 2} 2, \dbinom {n - 3} 3, \ldots$
and so the statement can be written:
:$F_{n + 1} = \ds \sum_{k \mathop \ge 0} \dbinom {n - k} k$
The proof proceeds by strong induction.
For all $n \in \Z_{>0}$, let $\map P n$ be the proposition:
:$F_{n + 1} = \ds \sum_{k \mathop \ge 0} \dbinom {n - k} k$
$\map P 0$ is the case:
Thus $\map P 0$ is seen to hold.
=== Basis for the Induction ===
$\map P 1$ is the case:
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P j$ is true, for all $j$ such that $0 \le j \le r$, then it logically follows that $\map P {r + 1}$ is true.
So this is the induction hypothesis:
from which it is to be shown that:
:$F_{r + 2} = \ds \sum_{k \mathop \ge 0} \dbinom {r + 1 - k} k$
=== Induction Step ===
This is the induction step:
So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{>0}: F_{n + 1} = \ds \sum_{k \mathop \ge 0} \dbinom {n - k} k$
== Sources ==
* : $35$
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $16$
* : $35$
Category:Pascal's Triangle
Category:Fibonacci Numbers
Sum of Entries in Row of Pascal's Triangle/Proof 1

== Theorem ==
== Proof ==
By definition, the entries in $n$th row of Pascal's triangle are exactly the binomial coefficients:
:$\dbinom n 0, \dbinom n 1, \ldots, \dbinom n n$
The result follows from Sum of Binomial Coefficients over Lower Index.
== Sources ==
* : $35$
Category:Sum of Entries in Row of Pascal's Triangle
Sum of Entries in Row of Pascal's Triangle/Proof 2

== Theorem ==
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:The sum of all the entries in the $n$th row of Pascal's triangle is equal to $2^n$.
=== Basis for the Induction ===
$\map P 0$ is the case:
:The sum of all the entries in the row $0$ of Pascal's triangle is equal to $2^0 = 1$.
This is true, as the only non-zero entry in row $0$ is $\dbinom 0 0$ which equals $1$.
Thus $\map P 0$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P k$ is true, where $k \ge 0$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:The sum of all the entries in the row $k$ of Pascal's triangle is equal to $2^k$.
from which it is to be shown that:
:The sum of all the entries in the row $k + 1$ of Pascal's triangle is equal to $2^{k + 1}$.
=== Induction Step ===
This is the induction step:
In row $k + 1$ there are $k + 2$ entries:
:$\dbinom {k + 1} 0, \dbinom {k + 1} 1, \dbinom {k + 1} 2, \ldots, \dbinom {k + 1} k, \dbinom {k + 1} {k + 1}$
From Pascal's Rule:
:$\dbinom {k + 1} j = \dbinom k {j - 1} + \dbinom k j$
Thus for each of the $k + 1$ entries in row $k$:
:$\dbinom k 0, \dbinom k 1, \ldots, \dbinom k k$
Element $\dbinom k j$ contributes to exactly $2$ elements of row $k + 1$
:$\dbinom {k + 1} j$ and $\dbinom {k + 1} {j + 1}$
So the sum of all the elements of row $k + 1$ is equal to $2$ times the sum of all the elements of row $k$.
By the induction hypothesis, that means the sum of all the elements of row $k + 1$ is equal to $2 \times 2^k$.
That is, the sum of all the entries in the row $k + 1$ of Pascal's triangle is equal to $2^{k + 1}$.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:For all $n \in \Z_{\ge 0}$, the sum of all the entries in the $n$th row of Pascal's triangle is equal to $2^n$.
Category:Sum of Entries in Row of Pascal's Triangle
Sum of Equal and Opposite Harmonic Waves form Stationary Wave

== Theorem ==
Let $\phi_1$ be a harmonic wave which is propagated along the $x$-axis in the positive direction with constant velocity $c$.
Let $\phi_2$ be a harmonic wave travelling with constant velocity $-c$, that is, at the same speed as $\phi_1$ but in the opposite direction.
Then their sum $\phi_1 + \phi_2$ describes a stationary wave.
== Proof ==
From Equation of Harmonic Wave: Wave Number and Frequency:
:$(1): \quad \map {\phi_1} {x, t} = a \map \cos {2 \pi \paren {k x - \nu t} }$
where:
:$k$ denotes the wave number of $\phi_1$
:$\nu$ denotes the frequency of $\phi_1$.
From Equation of Wave with Constant Velocity: Corollary, the equation of $\phi_2$ is:
:$(2): \quad \map {\phi_2} {x, t} = a \map \cos {2 \pi \paren {k x + \nu t} }$
Then we have:
== Sources ==
* : Chapter $\text {I}$: The Equation of Wave Motion: $\S 6$: $(15)$
Category:Harmonic Waves
Category:Stationary Waves
Sum of Euler Numbers by Binomial Coefficients Vanishes

== Theorem ==
$\forall n \in \Z_{>0}: \ds \sum_{k \mathop = 0}^n \binom {2 n} {2 k} E_{2 k} = 0$
where $E_k$ denotes the $k$th Euler number.
=== Corollary ===
== Proof ==
Thus:
Let:
Then:
We now have:
Grouping terms with even exponents produces:
$\forall n \in \Z_{>0}$, multiplying the coefficients of $x^{2 n}$ through by $\paren {2 n}!$ gives:
:$\paren {\dfrac {\paren {2 n}! } {0! \paren {2 n}!} } E_0 + \paren {\dfrac {\paren {2 n}! } {2! \paren {2 n - 2 }!} } E_2 + \paren {\dfrac {\paren {2 n}! } {4! \paren {2 n - 4 }!} } E_4 + \cdots + \paren {\dfrac {\paren {2 n}! } {\paren {2 n}! 0!} } E_{2 n} = 0$
But those coefficients are the binomial coefficients:
:$\dbinom {2 n} 0 E_0 + \dbinom {2 n} 2 E_2 + \dbinom {2 n} 4 E_4 + \dbinom {2 n} 6 E_6 + \cdots + \dbinom {2 n} {2 n} E_{2 n} = 0$
Hence the result.
== Examples ==
== Also see ==
* Sum of Bernoulli Numbers by Binomial Coefficients Vanishes
* Recurrence Relation for Euler Numbers
Category:Sum of Euler Numbers by Binomial Coefficients Vanishes
Category:Euler Numbers
Category:Binomial Coefficients
Sum of Euler Numbers by Binomial Coefficients Vanishes/Examples

== Example of Use of Sum of Euler Numbers by Binomial Coefficients Vanishes ==
:$\begin{array}{r|cccccccccc}
E_k & \dbinom n 0 & & \dbinom n 2 & & \dbinom n 4 & & \dbinom n 6 & & \dbinom n 8 & & \dbinom n {10} \\
\hline
E_0 = +1 & 1 E_0 & & & & & & & & & & & = 1 \\
E_2 = -1 & 1 E_0 & + & 1 E_2 & & & & & & & & & = 0 \\
E_4 = +5 & 1 E_0 & + & 6 E_2 & + & 1 E_4 & & & & & & & = 0 \\
E_6 = -61 & 1 E_0 & + & 15 E_2 & + & 15 E_4 & + & 1 E_6 & & & & & = 0 \\
E_8 = +1385 & 1 E_0 & + & 28 E_2 & + & 70 E_4 & + & 28 E_6 & + & 1 E_8 & & & = 0 \\
E_{10} = -50521 & 1 E_0 & + & 45 E_2 & + & 210 E_4 & + & 210 E_6 & + & 45 E_8 & + & 1 E_{10} & = 0 \\
\end{array}$
Category:Sum of Euler Numbers by Binomial Coefficients Vanishes
Sum of Euler Phi Function over Divisors

== Theorem ==
Let $n \in \Z_{>0}$ be a strictly positive integer.
Then $\ds \sum_{d \mathop \divides n} \map \phi d = n$
where:
:$\ds \sum_{d \mathop \divides n}$ denotes the sum over all of the divisors of $n$
:$\map \phi d$ is the Euler $\phi$ function, the number of integers less than $d$ that are prime to $d$.
That is, the total of all the totients of all divisors of a number equals that number.
== Proof ==
Let us define:
:$S_d = \set {m \in \Z: 1 \le m \le n, \gcd \set {m, n} = d}$.
That is, $S_d$ is all the numbers less than or equal to $n$ whose GCD with $n$ is $d$.
Now from Integers Divided by GCD are Coprime we have:
:$\gcd \set {m, n} = d \iff \dfrac m d, \dfrac n d \in \Z: \dfrac m d \perp \dfrac n d$
So the number of integers in $S_d$ equals the number of positive integers no bigger than $\dfrac n d$ which are prime to $\dfrac n d$.
That is, by definition of the Euler phi function:
:$\card {S_d} = \map \phi {\dfrac n d}$
From the definition of the $S_d$, it follows that for all $1 \le m \le n$:
:$\exists d \divides n: m \in S_d$
Therefore:
:$\ds \set {1, \ldots, n} = \bigcup_{d \mathop \divides n} S_d$
Moreover, it follows from the definition of the $S_d$ that they are pairwise disjoint.
Now from Corollary to Cardinality of Set Union, it follows that:
But from Sum Over Divisors Equals Sum Over Quotients:
:$\ds \sum_{d \mathop \divides n} \map \phi {\dfrac n d} = \sum_{d \mathop \divides n} \map \phi d$
and hence the result.
== Sources ==
* : Chapter $1$: Properties of the Natural Numbers: $\S 25 \alpha$
* : $2.3$: The Euler totient function $\map \varphi n$
* : $\S 2.3$: Congruences: Exercise $16$
Category:Euler Phi Function
Sum of Even Index Binomial Coefficients

== Theorem ==
Let $n > 0$ be a (strictly) positive integer.
Then:
:$\ds \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1}$
where $\dbinom n i$ is a binomial coefficient.
That is:
:$\dbinom n 0 + \dbinom n 2 + \dbinom n 4 + \dotsb = 2^{n - 1}$
== Proof 1 ==
== Proof 2 ==
== Also see ==
* Sum of Odd Index Binomial Coefficients
== Sources ==
* : $\S 3$: The Binomial Formula and Binomial Coefficients: Properties of Binomial Coefficients: $3.10$
* : $\text {3-1}$ Permutations and Combinations: Exercise $7$
* : Chapter $1$: Some Preliminary Considerations: $1.2$ The Binomial Theorem: Problems $1.2$: $3 \ \text{(e)}$
* : $\S 3$: The Binomial Formula and Binomial Coefficients: Properties of Binomial Coefficients: $3.10.$
Category:Sum of Even Index Binomial Coefficients
Category:Binomial Coefficients
Sum of Even Index Binomial Coefficients/Proof 1

== Theorem ==
== Proof ==
From Sum of Binomial Coefficients over Lower Index we have:
:$\ds \sum_{i \mathop \in \Z} \binom n i = 2^n$
That is:
:$\dbinom n 0 + \dbinom n 1 + \dbinom n 2 + \dbinom n 3 + \cdots + \dbinom n n = 2^n$
as $\dbinom n i = 0$ for $i < 0$ and $i > n$.
This can be written more conveniently as:
:$\dbinom n 0 + \dbinom n 1 + \dbinom n 2 + \dbinom n 3 + \dbinom n 4 + \cdots = 2^n$
Similarly, from Alternating Sum and Difference of Binomial Coefficients for Given n we have:
:$\ds \sum_{i \mathop \in \Z} \paren {-1}^i \binom n i = 0$
That is:
:$\dbinom n 0 - \dbinom n 1 + \dbinom n 2 - \dbinom n 3 + \dbinom n 4 - \cdots = 0$
Adding them together, we get:
:$2 \dbinom n 0 + 2 \dbinom n 2 + 2 \dbinom n 4 + \cdots = 2^n$
as the odd index coefficients cancel out.
Dividing by $2$ throughout gives us the result.
== Sources ==
* : $\text I$. Algebra: The Binomial Theorem: Relations between coeffficients
* : $\S 1.2.6$: Binomial Coefficients: Exercise $37$
Category:Sum of Even Index Binomial Coefficients
Sum of Even Index Binomial Coefficients/Proof 2

== Theorem ==
== Proof ==
Let ${\N_n}^*$ be the initial segment of natural numbers, one-based.
Let:
:$E_n = \set {X : \paren {X \subset {\N_n}^*} \land \paren {2 \divides \size X} }$
:$O_n = \set {X : \paren {X \subset {\N_n}^*} \land \paren {2 \nmid \size X} }$
That is:
:$E_n$ is the set of all subsets of ${\N_n}^*$ with an even number of elements
:$O_n$ is the set of all subsets of ${\N_n}^*$ with an odd number of elements.
So by Cardinality of Set of Subsets:
:$\ds \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1} \iff \size {E_n} = 2^{n - 1}$
which is to be proved by induction below.
=== Basis of the Induction ===
Let $n = 1$.
Then
:$\size {E_n} = \size {\set \O} = 1$
and:
:$2^{n - 1} = 2^{1 - 1} = 2^0 = 1$
This is the basis for the induction.
=== Induction Hypothesis ===
This is the induction hypothesis:
:$\size {E_k} = 2^{k - 1}$
So:
:$\size {O_k} = \size {2^{ {\N_k}^*} \divides E_k} = 2^k - 2^{k - 1} = 2^{k - 1}$
=== Induction Step ===
This is the induction step:
The result follows by induction.
Category:Sum of Even Index Binomial Coefficients
Category:Proofs by Induction
Sum of Even Integers is Even/Proof 1

== Theorem ==
== Proof ==
Proof by induction:
For all $n \in \N$, let $\map P n$ be the proposition:
:The sum of $n$ even integers is an even integer.
$\map P 1$ is trivially true, as this just says:
:The sum of $1$ even integer is an even integer.
The sum of $0$ even integers is understood, from the definition of a vacuous summation, to be $0$, which is even.
So $\map P 0$ is also true.
=== Basis for the Induction ===
$\map P 2$ is the case:
:The sum of any two even integers is itself even.
Consider two even integers $x$ and $y$.
Since they are even, they can be written as $x = 2 a$ and $y = 2 b$ respectively for integers $a$ and $b$.
Therefore, the sum is:
:$x + y = 2 a + 2 b = 2 \paren {a + b}$
Thus $x + y$ has $2$ as a divisor and is even by definition.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:The sum of any $k$ even integers is itself even.
Then we need to show:
:The sum of any $k+1$ even integers is itself even.
=== Induction Step ===
This is our induction step:
Consider the sum of any $k + 1$ even integers.
This is the sum of:
:$k$ even integers (which is even by the induction hypothesis)
and:
:another even integer.
That is, it is the sum of two even integers.
By the basis for the induction, this is also even.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
That is:
:The sum of any finite number of even integers is itself even.
Category:Sum of Even Integers is Even
Sum of Even Integers is Even/Proof 2

== Theorem ==
== Proof ==
Let $S = \set {r_1, r_2, \ldots, r_n}$ be a set of $n$ even numbers.
By definition of even number, this can be expressed as:
:$S = \set {2 s_1, 2 s_2, \ldots, 2 s_n}$
where:
:$\forall k \in \closedint 1 n: r_k = 2 s_k$
Then:
Thus, by definition, $\ds \sum_{k \mathop = 1}^n r_k$ is even.
== Sources ==
* : Book $\text{IX}$. Propositions
Category:Sum of Even Integers is Even
Sum of Even Number of Odd Numbers is Even

== Theorem ==
== Proof ==
Let $S = \set {r_1, r_2, \ldots, r_n}$ be a set of $n$ odd numbers, where $n = 2 m$.
By definition of odd number, this can be expressed as:
:$S = \set {2 s_1 + 1, 2 s_2 + 1, \ldots, 2 s_n + 1}$
where:
:$\forall k \in \closedint 1 n: r_k = 2 s_k + 1$
Then:
Thus, by definition, $\ds \sum_{k \mathop = 1}^n r_k$ is even.
== Sources ==
* : Book $\text{IX}$. Propositions
Category:Euclidean Number Theory
Sum of Even Sequence of Products of Consecutive Fibonacci Numbers

== Theorem ==
Let $F_k$ be the $k$'th Fibonacci number.
Then:
:$\ds \sum_{j \mathop = 1}^{2 n} F_j F_{j + 1} = {F_{2 n + 1} }^2 - 1$
== Proof ==
From Sum of Odd Sequence of Products of Consecutive Fibonacci Numbers:
:$(1): \quad \ds \sum_{j \mathop = 1}^{2 n - 1} F_j F_{j + 1} = {F_{2 n} }^2$
Hence:
== Sources ==
* : $\text {1-1}$ Principle of Mathematical Induction: Exercise $12$
Category:Sums of Sequences
Category:Fibonacci Numbers