nyuuzyou/wikis huggingface dataset:
Summation of Zero/Set

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $S$ be a set.
Let $0: S \to \mathbb A$ be the zero mapping.
Then the summation with finite support of $0$ over $S$ equals zero:
:$\ds \sum_{s \mathop \in S} \map 0 s = 0$
== Proof ==
By Support of Zero Mapping, the support of $0$ is empty.
By Empty Set is Finite, the support of $0$ is indeed finite.
By Summation over Empty Set:
:$\ds \sum_{s \mathop \in S} \map 0 s = \sum_{s \mathop \in \O} \map 0 s = 0$
Category:Summations
Summation of i from 1 to n of Summation of j from 1 to i

== Theorem ==
:$\ds \sum_{i \mathop = 1}^n \sum_{j \mathop = 1}^i a_{i j} = \sum_{j \mathop = 1}^n \sum_{i \mathop = j}^n a_{i j}$
== Proof 1 ==
== Proof 2 ==
== Example ==
Category:Summations
Category:Summation of i from 1 to n of Summation of j from 1 to i
Summation of i from 1 to n of Summation of j from 1 to i/Example

== Example of Summation of $i$ from $1$ to $n$ of Summation of $j$ from $1$ to $i$ ==
Let $n = 3$.
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $4$
Category:Summation of i from 1 to n of Summation of j from 1 to i
Summation of i from 1 to n of Summation of j from 1 to i/Proof 1

== Theorem ==
== Proof ==
:$\ds \sum_{i \mathop = 1}^n \sum_{j \mathop = 1}^i$
can be expressed as:
:$\ds \sum_{\map R i} \sum_{\map S {i, j} } a_{i j}$
where:
:$\map R i$ is the propositional function $1 \le i \le n$
:$\map S {i, j}$ is the propositional function $1 \le j \le i$
We wish to find a propositional function $\map {S'} j$ which is to be:
:there exists an $i$ such that both $1 \le i \le n$ and $1 \le j \le i$
This is satisfied by the propositional function:
:$\map {S'} j := 1 \le j \le n$
Next we wish to find a propositional function $\map {R'} {i, j}$ which is to be:
:both $1 \le i \le n$ and $1 \le j \le i$
This is satisfied by the propositional function:
:$\map {R'} {i, j} := j \le i \le n$
Hence the result, from Exchange of Order of Summation with Dependency on Both Indices.
== Sources ==
* : $\S 1.2.3$: Sums and Products: $(10)$
Category:Summation of i from 1 to n of Summation of j from 1 to i
Summation over Cartesian Product as Double Summation

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $S, T$ be finite sets.
Let $S \times T$ be their cartesian product.
Then we have an equality of summations over finite sets:
:$\ds \sum_{s \mathop \in S} \sum_{t \mathop \in T} \map f {s, t} = \sum_{\tuple {s, t} \mathop \in S \times T} \map f {s, t}$
== Outline of proof ==
We use induction on the cardinality of $T$. In the induction step, we use Sum over Disjoint Union of Finite Sets and Summation of Sum of Mappings on Finite Set.
== Proof ==
== Also see ==
* Exchange of Order of Summation over Cartesian Product of Finite Sets
Category:Summations
Summation over Finite Index is Well-Defined

== Theorem ==
Let $\struct{G, +}$ be a commutative monoid.
Let $\family{g }_{i \mathop \in I}$ be an indexed subset of $G$ where the indexing set $I$ is finite.
Then the summation $\ds \sum_{i \mathop \in I} g_i$ is well-defined.
== Proof ==
To show that summation over $I$ is well-defined it needs to be shown:
:$(1) \quad \exists$ a finite enumeration of $I$
:$(2) \quad \forall$ finite enumerations $e$ and $d$ of $I : \ds \sum_{k \mathop = 1}^n g_{e_k} = \sum_{k \mathop = 1}^n g_{d_k}$
=== Proof of $(1)$ ===
By definition of finite set:
:$\exists n \in \N : \exists$ a bijection $e: \closedint 1 n \to I$
Hence $e$ is a finite enumeration of $I$ by definition.
So the summation $\ds \sum_{k \mathop = 1}^n g_{e_k}$ exists.
=== Proof of $(2)$ ===
Let $d: \closedint 1 n \to I$ be any other finite enumeration of $I$.
Consider the composite mapping $e^{-1} \circ d : \closedint 1 n \to \closedint 1 n$ which exists and is a bijection because $e$ and $d$ are bijections.
Let $\operatorname{id}_I: I \to I$ denote the identity mapping on $I$.
We have:
The result follows.
Category:Summations
Summation over Finite Set Equals Summation over Support

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $S$ be a finite set.
Let $f: S \to \mathbb A$ be a mapping.
Let $\map \supp f$ be its support.
Then we have an equality of summations over finite sets:
:$\ds \sum_{s \mathop \in S} \map f s = \sum_{s \mathop \in \map \supp f} \map f s$
== Proof ==
Note that by Subset of Finite Set is Finite, $\map \supp f$ is indeed finite.
The result now follows from:
* Sum over Complement of Finite Set
* Sum of Zero over Finite Set
* Identity Element of Addition on Numbers
== Also see ==
* Definition:Summation over Set with Finite Support
Category:Summations
Summation over Finite Set is Well-Defined

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $S$ be a finite set.
Let $f: S \to \mathbb A$ be a mapping.
Let $n$ be the cardinality of $S$.
let $\N_{<n}$ be an initial segment of the natural numbers.
Let $g, h: \N_{<n} \to S$ be bijections.
Then we have an equality of indexed summations of the compositions $f \circ g$ and $f \circ h$:
:$\ds \sum_{i \mathop = 0}^{n - 1} \map f {\map g i} = \sum_{i \mathop = 0}^{n - 1} \map f {\map h i}$
That is, the definition of summation over a finite set does not depend on the choice of the bijection $g: S \to \N_{< n}$.
== Proof ==
By Inverse of Bijection is Bijection, $h^{-1} : \N_{<n} \to S$ is a bijection.
By Composite of Bijections is Bijection, the composition $h^{-1}\circ g$ is a permutation of $\N_{<n}$.
By Indexed Summation does not Change under Permutation, we have an equality of indexed summations:
:$\ds \sum_{i \mathop = 0}^{n - 1} \map {\paren {f \circ h} } i = \sum_{i \mathop = 0}^{n - 1} \map {\paren {f \circ h} \circ \paren {h^{-1} \circ g} } i$
By Composition of Mappings is Associative and Composite of Bijection with Inverse is Identity Mapping, the equals $\ds \sum_{i \mathop = 0}^{n - 1} \map f {\map g i}$.
== Also see ==
* Change of Variables in Summation over Finite Set
Category:Summations
Summation over Finite Subset is Well-Defined

== Theorem ==
Let $\struct{G, +}$ be a commutative monoid.
Let $F \subseteq G$ be a finite subset of $G$.
Then the summation $\ds \sum_{g \mathop \in F} g$ is well-defined.
== Proof ==
To show that summation over $F$ is well-defined it needs to be shown:
:$(1) \quad \exists$ a finite enumeration of $F$
:$(2) \quad \forall$ finite enumerations $e$ and $d$ of $F : \ds \sum_{i \mathop = 1}^n e_i = \sum_{i \mathop = 1}^n d_i$
=== Proof of $(1)$ ===
By definition of finite set:
:$\exists n \in \N : \exists$ a bijection $e: \closedint 1 n \to F$
Hence $e$ is a finite enumeration of $F$ by definition.
So the summation $\ds \sum_{i \mathop = 1}^n e_i$ exists.
=== Proof of $(2)$ ===
Let $d: \closedint 1 n \to F$ be any other finite enumeration of $F$.
Consider the composite mapping $e^{-1} \circ d : \closedint 1 n \to \closedint 1 n$ which exists and is a bijection because $e$ and $d$ are bijections.
Let $\operatorname{id}_G: G \to G$ denote the identity mapping on $G$.
We have:
The result follows.
Category:Summations
Summation over Interval equals Indexed Summation

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $a, b \in \Z$ be integers.
Let $\closedint a b$ be the integer interval between $a$ and $b$.
Let $f: \closedint a b \to \mathbb A$ be a mapping.
Then the summation over the finite set $\closedint a b$ equals the indexed summation from $a$ to $b$:
:$\ds \sum_{k \mathop \in \closedint a b} \map f k = \sum_{k \mathop = a}^b \map f k$
== Proof ==
By Cardinality of Integer Interval, $\closedint a b$ has cardinality $b - a + 1$.
By Translation of Integer Interval is Bijection, the mapping $T : \closedint 0 {b - a} \to \closedint a b$ defined as:
:$\map T k = k + a$
is a bijection.
By definition of summation:
:$\ds \sum_{k \mathop \in \closedint a b} \map f k = \sum_{k \mathop = 0}^{b - a} \map f {k + a}$
By Indexed Summation over Translated Interval:
:$\ds \sum_{k \mathop = 0}^{b - a} \map f {k + a} = \sum_{k \mathop = a}^b \map f k$
Category:Summations
Summation over Lower Index of Unsigned Stirling Numbers of the First Kind

== Theorem ==
Let $n \in \Z_{\ge 0}$ be a positive integer.
Then:
:$\ds \sum_k {n \brack k} = n!$
where:
:$\ds {n \brack k}$ denotes an unsigned Stirling number of the first kind
:$n!$ denotes the factorial of $n$.
== Proof ==
The proof proceeds by induction on $n$.
For all $n \in \Z_{\ge 0}$, let $\map P N$ be the proposition:
:$\ds \sum_k {n \brack k} = 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 m$ is true, where $m \ge 2$, then it logically follows that $\map P {m + 1}$ is true.
So this is the induction hypothesis:
:$\ds \sum_k {m \brack k} = m!$
from which it is to be shown that:
:$\ds \sum_k {m + 1 \brack k} = \paren {m + 1}!$
=== Induction Step ===
This is the induction step:
So $\map P m \implies \map P {m + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall n \in \Z_{\ge 0}: \sum_k {n \brack k} = n!$
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $39$
Category:Stirling Numbers
Category:Factorials
Summation over Lower Index of Unsigned Stirling Numbers of the First Kind with Alternating Signs

== Theorem ==
Let $n \in \Z_{\ge 0}$ be a positive integer.
Then:
:$\ds \sum_k \paren {-1}^k {n \brack k} = \delta_{n 0} - \delta_{n 1}$
where:
:$\ds {n \brack k}$ denotes an unsigned Stirling number of the first kind
:$\delta_{n 0}$ denotes the Kronecker delta.
== Proof ==
The proof proceeds by induction on $n$.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\ds \sum_k \paren {-1}^k {n \brack k} = \delta_{n 0} - \delta_{n 1}$
$\map P 0$ is the case:
Thus $\map P 0$ is seen to hold.
$\map P 1$ is the case:
Thus $\map P 1$ is seen to hold.
=== Basis for the Induction ===
$\map P 2$ is the case:
Thus $\map P 2$ 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 2$, then it logically follows that $\map P {m + 1}$ is true.
So this is the induction hypothesis:
:$\ds \sum_k \paren {-1}^k {m \brack k} = \delta_{m 0} - \delta_{m 1} = 0$
from which it is to be shown that:
:$\ds \sum_k \paren {-1}^k {m + 1 \brack k} = \delta_{\paren {m + 1} 0} - \delta_{\paren {m + 1} 1} = 0$
=== Induction Step ===
This is the induction step:
So $\map P m \implies \map P {m + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall n \in \Z_{\ge 0}: \sum_k \paren {-1}^k {n \brack k} = \delta_{n 0} - \delta_{n 1}$
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $39$
Category:Stirling Numbers
Category:Factorials
Summation over Union of Disjoint Finite Index Sets

== Theorem ==
Let $\struct{G, +}$ be a commutative monoid.
Let $I$ and $J$ be disjoint finite indexing sets.
Let $K = I \cup J$.
Let $\family{g_k}_{k \mathop \in K}$ be an indexed family of elements of $G$.
Then:
:$\ds \sum_{k \mathop \in K} g_k = \paren{\sum_{i \mathop \in I} g_i} + \paren{\sum_{j \mathop \in J} g_j}$
where:
:$\ds \sum_{k \mathop \in K} g_k$ is the summation of $g$ over $K$
:$\ds \sum_{i \mathop \in I} g_i$ is the summation of the restriction of $g$ over $I$
:$\ds \sum_{j \mathop \in J} g_j$ is the summation of the restriction of $g$ over $J$
== Proof ==
Let $\set{i_1, i_2, \ldots, i_n}$ be an enumeration of $I$.
Let $\set{j_1, j_2, \ldots, j_m}$ be an enumeration of $J$.
Let $k: \closedint 1 {n+m}$ be the mapping defined by:
:$k_l = \begin{cases}
i_l & : \text{ if } 1 \le l \le n \\
j_{l-n} & : \text{ if } l > n \\ 
\end{cases}$
From Union of Bijections with Disjoint Domains and Codomains is Bijection
:$\set{k_1, k_2, \ldots, k_{n + m}}$ is an enumeration of $K$
We have:
Category:Summations
Summation over k of Ceiling of k over 2

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n \ceiling {\dfrac k 2} = \ceiling {\dfrac {n \paren {n + 2} } 4}$
== Proof ==
By Permutation of Indices of Summation:
:$\ds \sum_{k \mathop = 1}^n \ceiling {\dfrac k 2} = \sum_{k \mathop = 1}^n \ceiling {\dfrac {n + 1 - k} 2}$
and so:
:$\ds \sum_{k \mathop = 1}^n \ceiling {\dfrac k 2} = \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\ceiling {\dfrac k 2} + \ceiling {\dfrac {n + 1 - k} 2} }$
First take the case where $n$ is even.
For $k$ odd:
and:
Hence:
For $k$ even:
and:
Hence:
So:
Next take the case where $n$ is odd.
For $k$ odd:
and:
Hence:
For $k$ even:
:$\ceiling {\dfrac k 2} = \dfrac k 2$
and:
:$\ceiling {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2$
Hence:
Let $n = 2 t + 1$.
Then:
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $36$
Category:Ceiling Function
Category:Summations
Summation over k of Ceiling of mk+x over n

== Theorem ==
Let $m, n \in \Z$ such that $n > 0$.
Let $x \in \R$.
Then:
:$\ds \sum_{0 \mathop \le k \mathop < n} \ceiling {\dfrac {m k + x} n} = \dfrac {\paren {m + 1} \paren {n - 1} } 2 - \dfrac {d - 1} 2 + d \ceiling {\dfrac x d}$
where:
:$\ceiling x$ denotes the ceiling of $x$
:$d$ is the greatest common divisor of $m$ and $n$.
== Proof ==
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $37$: Answers to Exercises
Category:Ceiling Function
Category:Summations
Summation over k of Floor of k over 2

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n \floor {\dfrac k 2} = \floor {\dfrac {n^2} 4}$
== Proof ==
By Permutation of Indices of Summation:
:$\ds \sum_{k \mathop = 1}^n \floor {\dfrac k 2} = \sum_{k \mathop = 1}^n \floor {\dfrac {n + 1 - k} 2}$
and so:
:$\ds \sum_{k \mathop = 1}^n \floor {\dfrac k 2} = \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\floor {\dfrac k 2} + \floor {\dfrac {n + 1 - k} 2} }$
First take the case where $n$ is even.
For $k$ odd:
:$\floor {\dfrac k 2} = \dfrac k 2 - \dfrac 1 2$
and:
:$\floor {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2$
Hence:
For $k$ even:
:$\floor {\dfrac k 2} = \dfrac k 2$
and:
:$\floor {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2 - \dfrac 1 2 = \dfrac {n - k} 2$
Hence:
So:
Next take the case where $n$ is odd.
For $k$ odd:
:$\floor {\dfrac k 2} = \dfrac k 2 - \dfrac 1 2$
and:
:$\floor {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2 - \dfrac 1 2$
Hence:
For $k$ even:
:$\floor {\dfrac k 2} = \dfrac k 2$
and:
:$\floor {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2$
Hence:
Let $n = 2 t + 1$.
Then:
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $36$
Category:Floor Function
Category:Summations
Summation over k of Floor of mk+x over n

== Theorem ==
Let $m, n \in \Z$ such that $n > 0$.
Let $x \in \R$.
Then:
:$\ds \sum_{0 \mathop \le k \mathop < n} \floor {\dfrac {m k + x} n} = \dfrac {\paren {m - 1} \paren {n - 1} } 2 + \dfrac {d - 1} 2 + d \floor {\dfrac x d}$
where:
:$\floor x$ denotes the floor of $x$
:$d$ is the greatest common divisor of $m$ and $n$.
== Proof ==
By definition of modulo 1:
:$\ds \sum_{0 \mathop \le k \mathop < n} \floor {\dfrac {m k + x} n} = \sum_{0 \mathop \le k \mathop < n} \dfrac {m k + x} n - \sum_{0 \mathop \le k \mathop < n} \fractpart {\dfrac {m k + x} n}$
where $\fractpart y$ in this context denotes the fractional part of $y$.
First we have:
Let $S$ be defined as:
:$\ds S := \sum_{0 \mathop \le k \mathop < n} \fractpart {\dfrac {m k + x} n}$
Thus:
:$(1): \quad \ds \sum_{0 \mathop \le k \mathop < n} \floor {\dfrac {m k + x} n} = \dfrac {m \paren {n - 1} } 2 + x - S$
Let $d = \gcd \set {m, n}$.
Let:
We have that:
Thus $S$ consists of $d$ copies of the same summation:
and so:
Thus:
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $37$
Category:Floor Function
Category:Summations
Summation over k of Floor of x plus k over y

== Theorem ==
Let $x, y \in \R$ such that $y > 0$.
Then:
:$\ds \sum_{0 \mathop \le k \mathop < y} \floor {x + \dfrac k y} = \floor {x y + \floor {x + 1} \paren {\ceiling y - y} }$
== Proof ==
When $x$ increases by $1$, both sides increase by $\ceiling y$.
So we can assume $0 \le x < 1$.
When $x = 0$, both sides are equal to $0$.
When $x$ increases past $1 - \dfrac k y$ for $0 \le k < y$, both sides increase by $1$.
Hence the result.
== Historical Note ==
== Sources ==
* 
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $38$
Category:Floor Function
Category:Summations
Summation over k to n of Harmonic Number k by Harmonic Number n-k

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n H_k H_{n - k} = \paren {n + 1} \paren { {H_n}^2 - H_n^{\paren 2} } - 2 n \paren {n_n - 1}$
where:
:$H_n$ denotes the $n$th harmonic number
:$H_n^{\paren 2}$ denotes a general harmonic number.
== Proof ==
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $22$
Category:Harmonic Numbers
Category:General Harmonic Numbers
Summation over k to n of Harmonic Numbers over n+1-k

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n \dfrac {H_k} {n + 1 - k} = {H_{n + 1} }^2 - H_{n + 1}^{\paren 2}$
where:
:$H_n$ denotes the $n$th harmonic number
:$H_n^{\paren 2}$ denotes a general harmonic number.
== Proof ==
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $21$
Category:Harmonic Numbers
Category:General Harmonic Numbers
Summation over k to n of Natural Logarithm of k

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n \ln k = \map \ln {n!}$
where $n!$ denotes the $n$th factorial.
== Proof ==
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $8$
Category:Factorials
Category:Natural Logarithms
Summation over k to n of Product of kth with n-kth Fibonacci Numbers

== Theorem ==
:$\ds \sum_{k \mathop = 0}^n F_k F_{n - k} = \dfrac {\paren {n - 1} F_n + 2n F_{n - 1} } 5$
where $F_n$ denotes the $n$th Fibonacci number.
== Proof ==
From Generating Function for Fibonacci Numbers, a generating function for the Fibonacci numbers is:
:$\map G z = \dfrac z {1 - z - z^2}$
Then:
where:
:$\phi = \dfrac {1 + \sqrt 5} 2$
:$\hat \phi = \dfrac {1 - \sqrt 5} 2$
Hence:
Since the coefficient of $z^n$ in $\paren {\map G z}^2$ is $\ds \sum_{k \mathop = 0}^n F_k F_{n - k}$, by comparing coefficients:
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: $(17)$
Category:Fibonacci Numbers
Summation to n of Power of k over k

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n \dfrac {x^k} k = H_n + \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\paren {x - 1}^k} k$
where:
:$H_n$ denotes the $n$th harmonic number
:$\dbinom n k$ denotes a binomial coefficient.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $13$
Category:Harmonic Numbers
Category:Binomial Coefficients
Category:Summation to n of Power of k over k
Summation to n of Power of k over k/Proof 1

== Theorem ==
== Proof ==
The proof proceeds by induction over $n$.
For all $n \in \Z_{\ge 1}$, let $\map P n$ be the proposition:
:$\ds \sum_{k \mathop = 1}^n \dfrac {x^k} k = H_n + \ds \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\paren {x - 1}^k} k$
=== 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 r$ is true, where $r \ge 1$, then it logically follows that $\map P {r + 1}$ is true.
So this is the induction hypothesis:
:$\ds \sum_{k \mathop = 1}^r \dfrac {x^k} k = H_r + \ds \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\paren {x - 1}^k} k$
from which it is to be shown that:
:$\ds \sum_{k \mathop = 1}^{r + 1} \dfrac {x^k} k = H_{r + 1} + \ds \sum_{k \mathop = 1}^{r + 1} \dbinom {r + 1} k \dfrac {\paren {x - 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_{\ge 1}: \ds \sum_{k \mathop = 1}^n \dfrac {x^k} k = H_n + \ds \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\paren {x - 1}^k} k$
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $13$
Category:Summation to n of Power of k over k
Summation to n of Reciprocal of k by k-1 of Harmonic Number

== Theorem ==
:$\ds \sum_{1 \mathop < k \mathop \le n} \dfrac 1 {k \paren {k - 1} } H_k = 2 - \dfrac {H_n} n - \dfrac 1 n$
where $H_n$ denotes the $n$th harmonic number.
== Proof ==
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $11$
Category:Harmonic Numbers
Summation to n of Square of kth Harmonic Number

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n {H_k}^2 = \paren {n + 1} {H_n}^2 - \paren {2 n + 1} H_n + 2 n$
where $H_k$ denotes the $k$th harmonic number.
== Proof ==
Consider:
Using Summation by Parts: 
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $15$
Category:Harmonic Numbers
Summation to n of kth Harmonic Number over k

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n \dfrac {H_k} k = \dfrac { {H_n}^2 + \harm 2 n } 2$
where:
:$H_n$ denotes the $n$th harmonic number
:$\harm 2 n$ denotes the general harmonic number of order $2$ evaluated at $n$.
== Proof ==
Hence the result.
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $14$
Category:Harmonic Numbers
Category:General Harmonic Numbers
Summation to n of kth Harmonic Number over k+1

== Theorem ==
:$\ds \sum_{k \mathop = 1}^n \dfrac {H_k} {k + 1} = \dfrac { {H_{n + 1} }^2 - \harm 2 {n + 1} } 2$
where:
:$H_n$ denotes the $n$th harmonic number
:$\harm 2 n$ denotes the general harmonic number of order $2$ evaluated at $n$.
== Proof ==
Hence the result.
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $14$
Category:Harmonic Numbers
Category:General Harmonic Numbers
Summations of Products of Binomial Coefficients

== Theorem ==
This page gathers together some identities concerning summations of products of binomial coefficients.
In the following, unless otherwise specified:
:$k, m, n \in \Z$
:$r, s, t \in \R$.
=== Chu-Vandermonde Identity ===
=== Sum over $k$ of $\dbinom r {m + k}$ by $\dbinom s {n + k}$ ===
=== Sum over $k$ of $\dbinom r k$ by $\dbinom {s + k} n$ by $\left({-1}\right)^{r - k}$ ===
=== Sum over $k$ of $\dbinom {r - k} m$ by $\dbinom s {k - t}$ by $\left({-1}\right)^{k - t}$ ===
=== Sum over $k$ of $\dbinom {r - k} m$ by $\dbinom {s + k} n$ ===
=== Sum over $k$ of $\dbinom {r - t k} k$ by $\dbinom {s - t \left({n - k}\right)} {n - k}$ by $\dfrac r {r - t k}$ ===
Category:Binomial Coefficients
Sums of Consecutive Sequences of Squares that equal Squares

== Theorem ==
The $24$th square pyramidal number is the only one which is square:
:$1^2 + 2^2 + 3^2 + \cdots + 24^2 = 70^2$
while there are several Sum of Sequence of Squares which are square, for example:
:$18^2 + 19^2 + \cdots + 28^2 = 77^2$
and:
:$25^2 + 26^2 + \cdots + 624^2 = 9010^2$
== Proof ==
We have:
and:
and:
== Sources ==
* : $24$
* : $24$
* : $9010$
Category:Square Numbers
Category:Sums of Sequences
Category:Sum of Sequence of Squares
Sums of Partial Sequences of Squares

== Theorem ==
Let $n \in \Z_{>0}$.
Consider the odd number $2 n + 1$ and its square $\paren {2 n + 1}^2 = 2 m + 1$.
Then:
:$\ds \sum_{j \mathop = 0}^n \paren {m - j}^2 = \sum_{j \mathop = 1}^n \paren {m + j}^2$
That is:
:the sum of the squares of the $n + 1$ integers up to $m$
equals:
:the sum of the squares of the $n$ integers from $m + 1$ upwards.
== Proof ==
First we express $m$ in terms of $n$:
We have:
Hence the result.
== Examples ==
== Sources ==
* : $25$
* : $25$
* : $365$
Category:Sums of Sequences
Category:Square Numbers
Category:Sums of Partial Sequences of Squares
Sums of Partial Sequences of Squares/Examples

== Examples of Sums of Partial Sequences of Squares ==
=== Example: $3^2 = 4 + 5$ ===
=== Example: $5^2 = 12 + 13$ ===
=== Example: $7^2 = 24 + 25$ ===
== Sources ==
* : $25$
* : $25$
Category:Sums of Partial Sequences of Squares