nyuuzyou/wikis huggingface dataset:
Sum of Sequence of Binomial Coefficients by Powers of 2/Proof 2

== Theorem ==
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\ds \sum_{j \mathop = 0}^n 2^j \binom n j = 3^n$
$\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 k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$\ds \sum_{j \mathop = 0}^k 2^j \binom k j = 3^k$
from which it is to be shown that:
:$\ds \sum_{j \mathop = 0}^{k + 1} 2^j \binom {k + 1} j = 3^{k + 1}$
=== Induction Step ===
This is the induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{\ge 0}: \ds \sum_{j \mathop = 0}^n 2^j \binom n j = 3^n$
Category:Sum of Sequence of Binomial Coefficients by Powers of 2
Sum of Sequence of Binomial Coefficients by Sum of Powers of Integers

== Theorem ==
Let $n, k \in \Z_{\ge 0}$ be positive integers.
Let $S_k = \ds \sum_{i \mathop = 1}^n i^k$.
Then:
:$\ds \sum_{i \mathop = 1}^k \binom {k + 1} i S_i = \paren {n + 1}^{k + 1} - \paren {n + 1}$
== Proof ==
Let $N$ be a positive integer. 
Then: 
Summing from $N = 1$ to $N = n$, we have on the :
So, we have: 
giving: 
:$\ds \sum_{i \mathop = 1}^k \binom {k + 1} i S_i = \paren {n + 1}^{k + 1} - \paren {n + 1}$
== Sources ==
* : $\S 19$: Sums of Powers of Positive Integers: $19.13$
* : $\S 21$: Series of Constants: Sums of Powers of Positive Integers: $21.13.$
Category:Sums of Sequences
Sum of Sequence of Cubes

== Theorem ==
:$\ds \sum_{i \mathop = 1}^n i^3 = \paren {\sum_{i \mathop = 1}^n i}^2 = \frac {n^2 \paren {n + 1}^2} 4$
== Proof by Induction ==
== Proof by Nicomachus ==
== Proof by Recursion ==
== Proof using Bernoulli Numbers ==
== Proof using Multiplication Table ==
== Visual Demonstration ==
== Sequence ==
== Also presented as ==
== Examples ==
== Also see ==
* Sum of Sequence of Squares
* Sum of Sequence of Fourth Powers
== Historical Note ==
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 18$: Induced $N$-ary Operations: Exercise $18.10 \ \text{(c)}$
* : $\text {1-1}$ Principle of Mathematical Induction: Exercise $2$
* : $\S 1.17$: Finite Induction and Well-Ordering for Positive Integers: Exercise $4$
* : Appendix $\text{A}.6$: Mathematical Induction: Problem Set $\text{A}.6$: $37$
* : Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers: Exercise $11$
Category:Sums of Sequences
Category:Cube Numbers
Category:Sum of Sequence of Cubes
Sum of Sequence of Cubes/Also presented as

== Theorem ==
The Sum of Sequence of Cubes can also be presented as:
:$\ds \sum_{i \mathop = 0}^n i^3 = \paren {\sum_{i \mathop = 0}^n i}^2 = \frac {n^2 \paren {n + 1}^2} 4$
This is seen to be equivalent to the given form by the fact that the first term evaluates to $\dfrac {0^2 \paren {0 + 1}^2 } 4$ which is zero.
== Sources ==
* : Chapter $1$: Preliminaries: Exercises: $1.2 \ \text {b)}$
Category:Sum of Sequence of Cubes
Sum of Sequence of Cubes/Examples/100

== Examples of Sum of Sequence of Cubes ==
:$100 = 1^3 + 2^3 + 3^3 + 4^3 = 10^2 = \left({1 + 2 + 3 + 4}\right)^2$
== Proof ==
Category:Sum of Sequence of Cubes
Category:100
Sum of Sequence of Cubes/Examples/225

== Examples of Sum of Sequence of Cubes ==
:$225 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 = 15^2 = \paren {1 + 2 + 3 + 4 + 5}^2$
== Proof ==
Category:Sum of Sequence of Cubes
Category:225
Sum of Sequence of Cubes/Examples/36

== Examples of Sum of Sequence of Cubes ==
:$36 = 1^3 + 2^3 + 3^3 = 6^2 = \paren {1 + 2 + 3}^2$
== Proof ==
== Sources ==
* : $36$
* : $36$
Category:Sum of Sequence of Cubes
Category:36
Sum of Sequence of Cubes/Proof by Induction

== Theorem ==
== Proof ==
First, from Closed Form for Triangular Numbers:
:$\ds \sum_{i \mathop = 1}^n i = \frac {n \paren {n + 1} } 2$
So:
:$\ds \paren {\sum_{i \mathop = 1}^n i}^2 = \dfrac {n^2 \paren {n + 1}^2} 4$
Next we use induction on $n$ to show that:
:$\ds \sum_{i \mathop = 1}^n i^3 = \dfrac {n^2 \paren {n + 1}^2} 4$
The proof proceeds by induction.
For all $n \in \Z_{>0}$, let $\map P n$ be the proposition:
:$\ds \sum_{i \mathop = 1}^n i^3 = \dfrac {n^2 \paren {n + 1}^2} 4$
=== Basis for the Induction ===
$\map P 1$ is the case:
:$1^3 = \dfrac {1 \paren {1 + 1}^2} 4$
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 k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$\ds \sum_{i \mathop = 1}^k i^3 = \dfrac {k^2 \paren {k + 1}^2} 4$
from which it is to be shown that:
:$\ds \sum_{i \mathop = 1}^{k + 1} i^3 = \dfrac {\paren {k + 1}^2 \paren {k + 2}^2} 4$
=== Induction Step ===
This is the induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{>0}: \ds \sum_{i \mathop = 1}^n i^3 = \dfrac {n^2 \paren {n + 1}^2} 4$
== Sources ==
* : $\text I$. Algebra: The Method of Induction: Exercises $\text {II}$: $1$
* : $\S 3$: Natural Numbers: Exercise $\S 3.11 \ (1) \ \text{(ii)}$
* : Chapter $1$: Preliminaries: Exercises: $1.2 \ \text {b)}$
* : Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction: Problems $1.1$: $1 \ \text {(e)}$
Category:Sum of Sequence of Cubes
Category:Proofs by Induction
Sum of Sequence of Cubes/Proof by Nicomachus

== Theorem ==
== Proof ==
By Nicomachus's Theorem, we have:
:$\forall n \in \N_{>0}: n^3 = \paren {n^2 - n + 1} + \paren {n^2 - n + 3} + \ldots + \paren {n^2 + n - 1}$
Also by Nicomachus's Theorem, we have that the first term for $\paren {n + 1}^3$ is $2$ greater than the last term for $n^3$.
So if we add them all up together, we get:
Hence the result.
== Sources ==
* : $\S 1.2.1$: Mathematical Induction: Exercise $8 \ \text{(b)}$
Category:Sum of Sequence of Cubes
Sum of Sequence of Cubes/Proof by Recursion

== Theorem ==
== Proof ==
From Closed Form for Triangular Numbers‎:
:$(1): \quad \ds \map A n := \sum_{i \mathop = 1}^n i = \frac{n \paren {n + 1} } 2$
From Sum of Sequence of Squares:
:$(2): \quad \ds \map B n := \sum_{i \mathop = 1}^n i^2 = \frac{n \paren {n + 1} \paren {2 n + 1} } 6$
Let $\ds \map S n = \sum_{i \mathop = 1}^n i^3$.
Then:
Category:Sum of Sequence of Cubes
Sum of Sequence of Cubes/Proof using Bernoulli Numbers

== Theorem ==
== Proof ==
From Faulhaber's Formula:
where $B_k$ are the Bernoulli numbers.
Setting $p = 3$:
Hence the result.
== Also see ==
* Faulhaber's Formula
== Sources ==
* : $\S 19$: Sums of Powers of Positive Integers: $19.11$
* : $\S 21$: Series of Constants: Sums of Powers of Positive Integers: $21.11.$
Category:Sum of Sequence of Cubes
Sum of Sequence of Cubes/Proof using Multiplication Table

== Theorem ==
== Proof ==
:$\ds \paren {\sum_{i \mathop = 1}^n i}^2 = \paren {1 + 2 + 3 + \cdots + N}^2$
Organizing the terms above in a square matrix:
:$\begin{array}{r|cccccccccc}
\paren {\ds \sum_{i \mathop = 1}^n i}^2 & 1 & 2 & 3 & 4 & 5 & 6 & \cdots & N \\
\hline
1 & 1 & 2 & 3 & 4 & 5 & 6 & \cdots & N \\
2 & 2 & 4 & 6 & 8 & 10 & 12 & \cdots & 2 N \\
3 & 3 & 6 & 9 & 12 & 15 & 18 & \cdots & 3 N \\
4 & 4 & 8 & 12 & 16 & 20 & 24 & \cdots & 4 N \\
5 & 5 & 10 & 15 & 20 & 25 & 30 & \cdots & 5 N \\
6 & 6 & 12 & 18 & 24 & 30 & 36 & \cdots & 6 N \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
N & N & 2 N & 3 N & 4 N & 5 N & 6 N & \cdots & N^2 \\
\end{array}$
From Closed Form for Triangular Numbers:
:$\ds \sum_{i \mathop = 1}^n i = \frac {n \paren {n + 1} } 2$
Therefore:
:$\ds \paren {\sum_{i \mathop = 1}^n i}^2 = \dfrac {n^2 \paren {n + 1}^2} 4$
Next we notice that the sum of the terms in row $N$ with the terms in column $N$ (less $N^2$ so as not to double count) is precisely $N^3$.
Therefore:
:$\forall n \in \Z_{>0}: \ds \sum_{i \mathop = 1}^n i^3 = \dfrac {n^2 \paren {n + 1}^2} 4$
Category:Sum of Sequence of Cubes
Sum of Sequence of Cubes/Visual Demonstration

== Theorem ==
== Proof ==
A visual illustration of the proof for $n = 5$:
:
The number of squares of side $n$ is seen to be $4 n$.
To go from $n$ to $n + 1$, a ring of $4 \paren {n + 1}$ squares of side $n + 1$ is to be added:
:$4$ for the one at each corner
:$4 n$ for the ones that abut the sides of the $n + 1$ squares of side $n$.
The length of one side is given by:
:$S = 2 \paren {1 + 2 + \cdots + n}$
The length of one side is also given by:
:$S = n \paren {n + 1}$
The area is therefore given in two ways as:
:$A = 4 \paren {1 + 2 + \cdots + n}^2 = \paren {n \paren {n + 1} }^2$
and also as:
The result follows by equating the expressions for area.
== Historical Note ==
== Sources ==
* 
* : $\S 1.2.1$: Mathematical Induction: Exercise $8 \ \text{(b)}$: Figure $5$
Category:Sum of Sequence of Cubes
Sum of Sequence of Cubes/Visual Demonstration/Historical Note

== Historical Note on Sum of Sequence of Cubes: Visual Demonstration ==
 
:
This visual demonstration of the Sum of Sequence of Cubes was reported by as having been devised by .
== Sources ==
* 
* : $\S 1.2.1$: Mathematical Induction: Exercise $8 \ \text{(b)}$: Note
Category:Historical Notes
Sum of Sequence of Cubes divides 3 times Sum of Sequence of Fifth Powers

== Theorem ==
:$\ds \sum_{i \mathop = 1}^n i^3 \divides 3 \sum_{i \mathop = 1}^n i^5$
where $\divides$ denotes divisibility.
== Proof ==
== Sources ==
* : No. $9$
* : $15$
* : $15$
Category:Cube Numbers
Category:Fifth Powers
Sum of Sequence of Even Index Fibonacci Numbers

== Theorem ==
Let $F_k$ be the $k$th Fibonacci number.
Then:
== Proof ==
Proof by induction:
For all $n \in \N_{>0}$, let $\map P n$ be the proposition:
:$\ds \sum_{j \mathop = 1}^n F_{2 j} = F_{2 n + 1} - 1$
=== Basis for the Induction ===
$\map P 1$ is the case $F_2 = 1 = F_3 - 1$, which holds from the definition of Fibonacci numbers.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\ds \sum_{j \mathop = 1}^k F_{2 j} = F_{2 k + 1} - 1$
Then we need to show:
:$\ds \sum_{j \mathop = 1}^{k + 1} F_{2 j} = F_{2 k + 3} - 1$
=== Induction Step ===
This is our induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall n \ge 1: \sum_{j \mathop = 1}^n F_{2 j} = F_{2 n + 1} - 1$
== Sources ==
* : $\text {1-1}$ Principle of Mathematical Induction: Exercise $9$
* : $5$
* : $5$
Category:Fibonacci Numbers
Category:Sums of Sequences
Category:Proofs by Induction
Sum of Sequence of Even Squares

== Theorem ==
:$\ds \forall n \in \N: \sum_{i \mathop = 0}^n \paren {2 i}^2 = \frac {2 n \paren {n + 1} \paren {2 n + 1} } 3$
== Proof ==
Category:Square Numbers
Category:Sums of Sequences
Sum of Sequence of Factorials

== Theorem ==
The sequence $S = \sequence {s_n}$ defined as:
:$\ds s_n = \sum_{k \mathop = 1}^n k!$
begins:
:$1, 3, 9, 33, 153, 873, 5913, 46 \, 233, 409 \, 113, 4 \, 037 \, 913, \ldots$
== Proof ==
Category:Factorials
Category:Sums of Sequences
Sum of Sequence of Fibonacci Numbers

== Theorem ==
Let $F_n$ denote the $n$th Fibonacci number.
Then:
:$\ds \forall n \in \Z_{\ge 0}: \sum_{j \mathop = 0}^n F_j = F_{n + 2} - 1$
== Proof ==
Proof by induction:
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\ds \sum_{j \mathop = 0}^n F_j = F_{n + 2} - 1$
$\map P 0$ is the case:
which is seen to hold.
=== Basis for the Induction ===
$\map P 1$ is the case:
which is seen to hold.
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:
:$\ds \sum_{j \mathop = 1}^k F_j = F_{k + 2} - 1$
Then we need to show:
:$\ds \sum_{j \mathop = 1}^{k + 1} F_j = F_{k + 3} - 1$
=== Induction Step ===
This is our induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall n \in \Z_{\ge 0}: \sum_{j \mathop = 0}^n F_j = F_{n + 2} - 1$
== Also presented as ==
This can also be seen presented as:
:$\ds \sum_{j \mathop = 1}^n F_j = F_{n + 2} - 1$
which is seen to be equivalent to the result given, as $F_0 = 0$.
== Sources ==
* : $\text {1-1}$ Principle of Mathematical Induction: Exercise $7$
* : $5$
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $20$
* : $5$
Category:Fibonacci Numbers
Category:Sums of Sequences
Category:Proofs by Induction
Sum of Sequence of Fifth Powers

== Theorem ==
:$\ds \sum_{i \mathop = 1}^n i^5 = \dfrac { {T_n}^2 \paren {4 T_n - 1} } 3$
where $T_n$ denotes the $n$th triangular number.
== Proof ==
<onlyinclude>
The proof proceeds by induction.
For all $n \in \Z_{> 0}$, let $\map P n$ be the proposition:
:$\ds \sum_{i \mathop = 1}^n i^5 = \dfrac { {T_n}^2 \paren {4 T_n - 1} } 3$
=== 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 k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$\ds \sum_{i \mathop = 1}^k i^5 = \dfrac { {T_k}^2 \paren {4 T_k - 1} } 3$
from which it is to be shown that:
:$\ds \sum_{i \mathop = 1}^{k + 1} i^5 = \dfrac { {T_{k + 1} }^2 \paren {4 T_{k + 1} - 1} } 3$
=== Induction Step ===
This is the induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{> 0}: \ds \sum_{i \mathop = 1}^n i^5 = \dfrac { {T_n}^2 \paren {4 T_n - 1} } 3$
== Also see ==
* Sum of Sequence of Fourth Powers
* Sum of Sequence of Seventh Powers
== Sources ==
* : $15$
* : $15$
Category:Fifth Powers
Category:Triangular Numbers
Category:Sums of Sequences
Sum of Sequence of Fourth Powers

== Theorem ==
:$\ds \sum_{k \mathop = 0}^n k^4 = \dfrac {\paren {n + 1} n \paren {n + \frac 1 2} \paren {3 n^2 + 3 n - 1} } {15}$
== Proof using Binomial Coefficients ==
== Proof using Bernoulli Numbers ==
== Also presented as ==
This result can also be presented as:
:$\ds \sum_{k \mathop = 0}^n k^4 = \dfrac {n \paren {n + 1} \paren {2 n + 1} \paren {3 n^2 + 3 n - 1} } {30}$
== Also see ==
* Sum of Sequence of Cubes
* Sum of Sequence of Fifth Powers
Category:Sums of Sequences
Category:Fourth Powers
Category:Sum of Sequence of Fourth Powers
Sum of Sequence of Fourth Powers/Proof using Bernoulli Numbers

== Theorem ==
== Proof ==
From Faulhaber's Formula:
where $B_k$ are the Bernoulli numbers.
Setting $p = 4$:
Hence the result.
== Also see ==
* Faulhaber's Formula
== Sources ==
* : $\S 19$: Sums of Powers of Positive Integers: $19.12$
* : $\S 21$: Series of Constants: Sums of Powers of Positive Integers: $21.12.$
Category:Sum of Sequence of Fourth Powers
Sum of Sequence of Fourth Powers/Proof using Binomial Coefficients

== Theorem ==
== Proof ==
By definition of binomial coefficient:
So:
== Also see ==
* Sum of Sequence of Squares/Proof by Binomial Coefficients
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $14$
Category:Sum of Sequence of Fourth Powers
Sum of Sequence of Harmonic Numbers

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n H_k = \paren {n + 1} H_n - n$
where $H_k$ denotes the $k$th harmonic number.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Sources ==
Category:Harmonic Numbers
Category:Sum of Sequence of Harmonic Numbers
Sum of Sequence of Harmonic Numbers/Proof 2

== Theorem ==
== Proof ==
From Sum over k to n of k Choose m by kth Harmonic Number:
:$\ds \sum_{k \mathop = 1}^n \binom k m H_k = \binom {n + 1} {m + 1} \paren {H_{n + 1} - \frac 1 {m + 1} }$
Setting $m = 0$:
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: $(8)$
Category:Sum of Sequence of Harmonic Numbers
Sum of Sequence of Harmonic Numbers/Proof 3

== Theorem ==
== Proof ==
Let $\sequence {a_n}$ be the sequence defined as:
:$\forall n \in \N_{> 0}: a_n = H_n$
where $H_n$ denotes the $n$th harmonic number.
Let $\map G z$ be the generating function for $\sequence {a_n}$.
From Generating Function for Sequence of Harmonic Numbers:
:$\map G z = \dfrac 1 {1 - z} \map \ln {\dfrac 1 {1 - z} }$
Then:
From Generating Function for Sequence of Partial Sums of Series, $\dfrac 1 {1 - z} \map G z$ is the generating function for $\sequence {b_n}$ where:
:$b_n = \ds \sum_{k \mathop = 0}^n H_k$
and so:
:$\dfrac 1 {\paren {1 - z}^2} \map \ln {\dfrac 1 {1 - z} } = \ds \sum_{n \mathop \ge 0} \paren {\sum_{k \mathop = 0}^n H_k} z^n$
From Generating Function for Natural Numbers:
:$\dfrac 1 {\paren {1 - z}^2} = \ds \sum_{n \mathop \ge 0} \paren {n + 1} z^n$
That is:
:$\map {G'} z = \ds \sum_{n \mathop \ge 0} \paren {\sum_{k \mathop = 0}^n H_k + \paren {n + 1} } z^n$
Now we have:
Equating coefficients of $z^n$ in these two expressions for $\map {G'} z$:
:$\ds \sum_{k \mathop = 0}^n H_k + \paren {n + 1} = \paren {n + 1} H_{n + 1}$
The result follows.
== Sources ==
* : $\S 1.2.9$: Generating Functions: Exercise $3$
Category:Sum of Sequence of Harmonic Numbers
Sum of Sequence of Odd Cubes

== Theorem ==
:$\ds \sum_{j \mathop = 1}^n \paren {2 j - 1}^3 = 1^3 + 3^3 + 5^3 + \dotsb + \paren {2 n − 1}^3 = n^2 \paren {2 n^2 − 1}$
== Proof ==
Proof by induction:
For all $n \in \Z_{\ge 1}$, let $\map P n$ be the proposition:
:$\ds \sum_{j \mathop = 1}^n \paren {2 j - 1}^3 = n^2 \paren {2 n^2 − 1}$
=== Basis for the Induction ===
$\map P 1$ is the case:
and $\map P 1$ is seen to hold.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\ds \sum_{j \mathop = 1}^k \paren {2 j - 1}^3 = k^2 \paren {2 k^2 − 1}$
Then we need to show:
:$\ds \sum_{j \mathop = 1}^{k + 1} \paren {2 j - 1}^3 = \paren {k + 1}^2 \paren {2 \paren {k + 1}^2 − 1}$
=== Induction Step ===
This is our induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall n \in \Z_{\ge 1}: \sum_{j \mathop = 1}^n \paren {2 j - 1}^3 = n^2 \paren {2 n^2 − 1}$
Category:Proofs by Induction
Category:Sums of Sequences
Category:Cube Numbers
Sum of Sequence of Odd Index Fibonacci Numbers

== Theorem ==
Let $F_k$ be the $k$th Fibonacci number.
Then:
== Proof ==
Proof by induction:
For all $n \in \N_{>0}$, let $\map P n$ be the proposition:
:$\ds \sum_{j \mathop = 1}^n F_{2 j - 1} = F_{2 n}$
=== Basis for the Induction ===
$\map P 1$ is the case $F_1 = 1 = F_2$, which holds from the definition of Fibonacci numbers.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\ds \sum_{j \mathop = 1}^k F_{2 j - 1} = F_{2 k}$
Then we need to show:
:$\ds \sum_{j \mathop = 1}^{k + 1} F_{2 j - 1} = F_{2 k + 2}$
=== Induction Step ===
This is our induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall n \ge 1: \sum_{j \mathop = 1}^n F_{2 j - 1} = F_{2 n}$
== Sources ==
* : $\text {1-1}$ Principle of Mathematical Induction: Exercise $8$
* : $5$
* : $5$
Category:Fibonacci Numbers
Category:Sums of Sequences
Category:Proofs by Induction
Sum of Sequence of Odd Squares/Formulation 1

== Theorem ==
:$\ds \forall n \in \N: \sum_{i \mathop = 0}^n \paren {2 i + 1}^2 = \frac {\paren {n + 1} \paren {2 n + 1} \paren {2 n + 3} } 3$
== Proof ==
Category:Sum of Sequence of Odd Squares
Sum of Sequence of Odd Squares/Formulation 2

== Theorem ==
:$\ds \forall n \in \Z_{> 0}: \sum_{i \mathop = 1}^n \paren {2 i - 1}^2 = \frac {4 n^3 - n} 3$
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{> 0}$, let $\map P n$ be the proposition:
:$\ds \sum_{i \mathop = 1}^n \paren {2 i - 1}^2 = \frac {4 n^3 - n} 3$
=== 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 k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$\ds \sum_{i \mathop = 1}^k \paren {2 i - 1}^2 = \frac {4 k^3 - k} 3$
from which it is to be shown that:
:$\ds \sum_{i \mathop = 1}^{k + 1} \paren {2 i - 1}^2 = \frac {4 \paren {k + 1}^3 - \paren {k + 1} } 3$
=== Induction Step ===
This is the induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall n \in \Z_{> 0}: \sum_{i \mathop = 1}^n \paren {2 i - 1}^2 = \frac {4 n^3 - n} 3$
== Sources ==
* : Appendix $\text{A}.6$: Mathematical Induction: Problem Set $\text{A}.6$: $38$
* : Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction: Problems $1.1$: $1 \ \text {(d)}$
Category:Sum of Sequence of Odd Squares
Sum of Sequence of Power by Index

== Theorem ==
:$\ds \sum_{j \mathop = 0}^n j x^j = \frac {n x^{n + 2} - \paren {n + 1} x^{n + 1} + x} {\paren {x - 1}^2}$
for $x \ne 1$.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $16$
Category:Arithmetic-Geometric Sequences
Category:Sum of Sequence of Power by Index
Sum of Sequence of Power by Index/Proof 2

== Theorem ==
== Proof ==
From Sum of Arithmetic-Geometric Sequence:
:$\ds \sum_{j \mathop = 0}^n \paren {a + j d} x^j = \frac {a \paren {1 - x^{n + 1} } } {1 - x} + \frac {x d \paren {1 - \paren {n + 1} x^n + n x^{n + 1} } } {\paren {1 - x}^2}$
Hence:
Hence the result.
Category:Sum of Sequence of Power by Index
Sum of Sequence of Product of Fibonacci Number with Binomial Coefficient

== Theorem ==
Let $F_n$ denote the $n$th Fibonacci number.
Then:
where $\dbinom n k$ denotes a binomial coefficient.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\text {3-1}$ Permutations and Combinations: Exercise $14$
Category:Fibonacci Numbers
Category:Binomial Coefficients
Category:Sum of Sequence of Product of Fibonacci Number with Binomial Coefficient
Sum of Sequence of Product of Fibonacci Number with Binomial Coefficient/Proof 1

== Theorem ==
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$F_{2 n} = \ds \sum_{k \mathop = 1}^n \dbinom n k F_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 m$ is true, where $m \ge 1$, then it logically follows that $\map P {m + 1}$ is true.
So this is the induction hypothesis:
:$F_{2 m} = \ds \sum_{k \mathop = 1}^m \dbinom m k F_k$
from which it is to be shown that:
:$F_{2 \paren {m + 1} } = \ds \sum_{k \mathop = 1}^{m + 1} \dbinom {m + 1} k F_k$
=== Induction Step ===
This is the induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{\ge 0}: F_{2 n} = \ds \sum_{k \mathop = 1}^n \dbinom n k F_k$
Category:Sum of Sequence of Product of Fibonacci Number with Binomial Coefficient
Category:Proofs by Induction