nyuuzyou/wikis huggingface dataset:
Sum over k of m+r+s Choose k by n+r-s Choose n-k by r+k Choose m+n

== Theorem ==
Let $m, n \in \Z_{\ge 0}$.
Then:
:$\ds \sum_{k \mathop \in \Z} \binom {m - r + s} k \binom {n + r - s} {n - k} \binom {r + k} {m + n} = \binom r m \binom s n$
== Proof ==
== Also see ==
* Dixon's Identity/General Case
== Sources ==
* 
* : $\S 1.2.6$: Binomial Coefficients: Exercise $31$
Category:Binomial Coefficients
Sum over k of m-n choose m+k by m+n choose n+k by Stirling Number of the Second Kind of m+k with k

== Theorem ==
Let $m, n \in \Z_{\ge 0}$.
:$\ds \sum_k \binom {m - n} {m + k} \binom {m + n} {n + k} {m + k \brace k} = {n \brack n - m}$
where:
:$\dbinom {m - n} {m + k}$ etc. denote binomial coefficients
:$\ds {m + k \brace k}$ denotes a Stirling number of the second kind
:$\ds {n \brack n - m}$ denotes an unsigned Stirling number of the first kind.
== Proof ==
The proof proceeds by induction on $m$.
For all $m \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\ds \forall n \in \Z_{\ge 0}: \sum_k \binom {m - n} {m + k} \binom {m + n} {n + k} {m + k \brace k} = {n \brack n - m}$
$\map P 0$ is the case:
So $\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 for all $m$.
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 \binom {r - n} {r + k} \binom {r + n} {n + k} {r + k \brace k} = {n \brack n - r}$
from which it is to be shown that:
:$\ds \sum_k \binom {r + 1 - n} {r + 1 + k} \binom {r + 1 + n} {n + k} {r + 1 + k \brace k} = {n \brack n - r + 1}$
=== 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:
:$\ds \forall m, n \in \Z_{\ge 0}: \sum_k \binom {m - n} {m + k} \binom {m + n} {n + k} {m + k \brace k} = {n \brack n - m}$
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: $(54)$
Category:Stirling Numbers
Category:Binomial Coefficients
Sum over k of m-n choose m+k by m+n choose n+k by Unsigned Stirling Number of the First Kind of m+k with k

== Theorem ==
Let $m, n \in \Z_{\ge 0}$.
:$\ds \sum_k \binom {m - n} {m + k} \binom {m + n} {n + k} {m + k \brack k} = {n \brace n - m}$
where:
:$\dbinom {m - n} {m + k}$ etc. denote binomial coefficients
:$\ds {m + k \brack k}$ denotes an unsigned Stirling number of the first kind
:$\ds {n \brace n - m}$ denotes a Stirling number of the second kind.
== Proof ==
The proof proceeds by induction on $m$.
For all $m \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\forall n \in \Z_{\ge 0}: \ds \sum_k \binom {m - n} {m + k} \binom {m + n} {n + k} {m + k \brack k} = {n \brace n - m}$
=== Basis for the Induction ===
$\map P 0$ is the case:
So $\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 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 \binom {r - n} {r + k} \binom {r + n} {n + k} {r + k \brack k} = {n \brace n - r}$
from which it is to be shown that:
:$\ds \sum_k \binom {r + 1 - n} {r + 1 + k} \binom {r + 1 + n} {n + k} {r + 1 + k \brack k} = {n \brace n - r + 1}$
=== 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 m, n \in \Z_{\ge 0}: \ds \sum_k \binom {m - n} {m + k} \binom {m + n} {n + k} {m + k \brack k} = {n \brace n - m}$
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: $(54)$
Category:Stirling Numbers
Category:Binomial Coefficients
Sum over k of m Choose k by k minus m over 2

== Theorem ==
:$\ds \sum_{k \mathop = 0}^n \binom m k \paren {k - \dfrac m 2} = -\dfrac m 2 \binom {m - 1} n$
where $\dbinom m k$ etc. are binomial coefficients.
== Proof ==
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: $(38)$
Category:Binomial Coefficients
Sum over k of m choose k by -1^m-k by k to the n

== Theorem ==
Let $m, n \in \Z_{\ge 0}$.
:$\ds \sum_k \binom m k \paren {-1}^{m - k} k^n = m! {n \brace m}$
where:
:$\dbinom m k$ denotes a binomial coefficient
:$\ds {n \brace m}$ etc. denotes a Stirling number of the second kind
:$m!$ denotes a factorial.
== Proof ==
The proof proceeds by induction on $m$.
For all $m \in \Z_{\ge 0}$, let $\map P m$ be the proposition:
:$\ds \forall n \in \Z_{\ge 0}: \sum_k \binom m k \paren {-1}^{m - k} k^n = m! {n \brace m}$
=== Basis for the Induction ===
$\map P 0$ is the case:
So $\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 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 \binom r k \paren {-1}^{r - k} k^n = r! {n \brace r}$
from which it is to be shown that:
:$\ds \sum_k \binom {r + 1} k \paren {-1}^{r + 1 - k} k^n = \paren {r + 1}! {n \brace r + 1}$
=== 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:
:$\ds \forall m, n \in \Z_{\ge 0}: \sum_k \binom m k \paren {-1}^{m - k} k^n = m! {n \brace m}$
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: $(53)$
Category:Stirling Numbers
Category:Binomial Coefficients
Sum over k of n+k Choose 2 k by 2 k Choose k by -1^k over k+1

== Theorem ==
Let $n \in \Z_{\ge 0}$.
Then:
:$\ds \sum_k \binom {n + k} {2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1} = \sqbrk {n = 0}$
where:
:$\dbinom {n + k} {2 k}$ etc. are binomial coefficients
:$\sqbrk {n = 0}$ is Iverson's convention.
== Proof 1 ==
== Proof 2 ==
Category:Binomial Coefficients
Category:Sum over k of n+k Choose 2 k by 2 k Choose k by -1^k over k+1
Sum over k of n+k Choose 2 k by 2 k Choose k by -1^k over k+1/Proof 1

== Theorem ==
== Proof ==
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Example $2$
Category:Sum over k of n+k Choose 2 k by 2 k Choose k by -1^k over k+1
Sum over k of n+k Choose 2 k by 2 k Choose k by -1^k over k+1/Proof 2

== Theorem ==
== Proof ==
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Example $2$
Category:Sum over k of n+k Choose 2 k by 2 k Choose k by -1^k over k+1
Sum over k of n+k Choose m+2k by 2k Choose k by -1^k over k+1

== Theorem ==
Let $m, n \in \Z_{\ge 0}$.
Then:
:$\ds \sum_k \binom {n + k} {m + 2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1} = \binom {n - 1} {m - 1}$
where $\dbinom {n + k} {m + 2 k}$ and so on are binomial coefficients.
== Proof 1 ==
== Proof 2 ==
Category:Binomial Coefficients
Category:Sum over k of n+k Choose m+2k by 2k Choose k by -1^k over k+1
Sum over k of n+k Choose m+2k by 2k Choose k by -1^k over k+1/Proof 1

== Theorem ==
== Proof ==
From Sum over $k$ of $\dbinom {r - k} m \dbinom {s + k} n$:
:$\ds \sum_{k \mathop = 0}^r \binom {r - k} m \binom {s + k} n = \binom {r + s + 1} {m + n + 1}$
Setting $r = n + k - 1$, $m = 2 k$, $s = 0$, $n = m - 1$ and using $j$ as the index variable, this gives us:
:$\ds \sum_{j \mathop = 0}^{n + k - 1} \binom {n + k - 1 - j} {2 k} \binom j {m - 1} = \dbinom {n + k} {m + 2 k}$
This leads to:
:$\ds \sum_k \binom {n + k} {m + 2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1} = \sum_k \sum_{j \mathop = 0}^{n + k - 1} \binom {n + k - 1 - j} {2 k} \binom {2 k} k \binom j {m - 1} \frac {\paren {-1} } {k + 1}$
Note that the terms of the above are $0$ when $n \le j < n + k - 1$.
This means that $k \ge 1$.
So:
:$0 \le n + k - 1 - j \le k - i < 2 k$
Thus the first binomial coefficient in the above will vanish.
The condition on the second summation can then be replaced by $0 \le j < n$.
After exchange of summation and application of Sum over $k$ of $\dbinom {n + k} {2 k} \dbinom {2 k} k \dfrac {-1^k} {k + 1}$ converts it into:
:$\ds \sum_{0 \mathop \le j \mathop < n} \binom j {m - 1} \delta_{\paren {n \mathop - 1} \mathop j}$
where $\delta_{\paren {n \mathop - 1} \mathop j}$ denotes the Kronecker delta.
All terms are therefore $0$ except where $j = n - 1$.
Hence the result.
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Example $3$
Category:Sum over k of n+k Choose m+2k by 2k Choose k by -1^k over k+1
Sum over k of n+k Choose m+2k by 2k Choose k by -1^k over k+1/Proof 2

== Theorem ==
== Proof ==
Let:
:$\ds S := \sum_k \binom {n + k} {m + 2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1}$
Then:
Also:
Reassembling $S$:
:$\ds S = \sum_k \binom {1 + 2 k} k \binom {-m - 2 k - 1} {n - m - k} \frac {\paren {-1}^{n - m} } {1 + 2 k}$
Recall Sum over $k$ of $\dbinom {r - t k} k$ by $\dbinom {s - t \paren {n - k} } {n - k}$ by $\dfrac r {r - t k}$:
:$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$
Making the following substitutions:
:$r \gets 1$
:$t \gets -2$
:$n \gets n - m$
we obtain:
Thus:
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $30$
Category:Sum over k of n+k Choose m+2k by 2k Choose k by -1^k over k+1
Sum over k of n Choose k by Fibonacci Number with index m+k

== Theorem ==
:$\ds \sum_{k \mathop \ge 0} \binom n k F_{m + k} = F_{m + 2 n}$
where:
:$\dbinom n k$ denotes a binomial coefficient
:$F_n$ denotes the $n$th Fibonacci number.
== Proof ==
From Sum over k of n Choose k by Fibonacci t to the k by Fibonacci t-1 to the n-k by Fibonacci m+k:
:$(1): \quad \ds \sum_{k \mathop \ge 0} \binom n k {F_t}^k {F_{t - 1} }^{n - k} F_{m + k} = F_{m + t n}$
Letting $t = 2$ in $(1)$:
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $22$
Category:Fibonacci Numbers
Category:Binomial Coefficients
Sum over k of n Choose k by Fibonacci t to the k by Fibonacci t-1 to the n-k by Fibonacci m+k

== Theorem ==
:$\ds \sum_{k \mathop \ge 0} \binom n k {F_t}^k {F_{t - 1} }^{n - k} F_{m + k} = F_{m + t n}$
where:
:$\dbinom n k$ denotes a binomial coefficient
:$F_n$ denotes the $n$th Fibonacci number.
== Proof ==
The proof proceeds by induction on $n$.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\forall m, t \in \N: \ds \sum_{k \mathop \ge 0} \binom n k {F_t}^k {F_{t - 1} }^{n - k} F_{m + k} = F_{m + t n}$
$\map P 0$ is the case:
:$\ds \binom 0 0 {F_t}^0 {F_{t - 1} }^0 F_{m + 0} = F_m$
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 q$ is true, where $q \ge 1$, then it logically follows that $\map P {q + 1}$ is true.
So this is the induction hypothesis:
:$\forall m, t \in \N: \ds \sum_{k \mathop \ge 0} \binom q k {F_t}^k {F_{t - 1} }^{q - k} F_{m + k} = F_{m + t q}$
from which it is to be shown that:
:$\forall m, t \in \N: \ds \sum_{k \mathop \ge 0} \binom {q + 1} k {F_t}^k {F_{t - 1} }^{q + 1 - k} F_{m + k} = F_{m + t \paren {q + 1} }$
=== Induction Step ===
This is the induction step:
So $\map P q \implies \map P {q + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall m, n, t \in \N: \ds \sum_{k \mathop \ge 0} \binom n k {F_t}^k {F_{t - 1} }^{n - k} F_{m + k} = F_{m + t n}$
== Also see ==
The following are corollaries to this theorem:
* Sum over k of n Choose k by Fibonacci Number with index m+k
* Sum of Sequence of Product of Fibonacci Number with Binomial Coefficient
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $23$
Category:Fibonacci Numbers
Category:Binomial Coefficients
Sum over k of n Choose k by p^k by (1-p)^n-k by Absolute Value of k-np

== Theorem ==
Let $n \in \Z_{\ge 0}$ be a non-negative integer.
Then:
:$\ds \sum_{k \mathop \in \Z} \dbinom n k p^k \paren {1 - p}^{n - k} \size {k - n p} = 2 \ceiling {n p} \dbinom n {\ceiling {n p} } p^{\ceiling {n p} } \paren {1 - p}^{n - 1 - \ceiling {n p} }$
== Proof ==
Let $t_k = k \dbinom n k p^k \paren {1 - p}^{n + 1 - k}$.
Then:
:$t_k - t_{k + 1} = \dbinom n k p^k \paren {1 - p}^{n - k} \paren {k - n p}$
Thus the stated summation is:
:$\ds \sum_{k \mathop < \ceiling {n p} } \paren {t_{k + 1} - t_k} + \sum_{k \mathop \ge \ceiling {n p} } \paren {t_k - t_{k + 1} } = 2 t_{\ceiling {n p} }$
== Historical Note ==
== Sources ==
* 
* 
* 
* : $\S 1.2.6$: Binomial Coefficients: Exercise $68$
Category:Binomial Coefficients
Sum over k of n Choose k by p^k by (1-p)^n-k by Absolute Value of k-np/Historical Note

== Historical Note on Sum over $k$ of $\dbinom n k$ by $p^k$ by $\left({1 - p}\right)^{n-k}$ by $\left\lvert{k - n p}\right\rvert$ ==
This result was stated by in his $1730$ work for the case where $n p$ is an integer.
The general case was proved by in his of $1896$.
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $68$
Category:Historical Notes
Sum over k of n Choose k by x to the k by kth Harmonic Number

== Theorem ==
Let $x \in \R_{> 0}$ be a real number.
Then:
:$\ds \sum_{k \mathop \in \Z} \binom n k x^k H_k = \paren {x + 1}^n \paren {H_n - \map \ln {1 + \frac 1 x} } + \epsilon$
where:
:$\dbinom n k$ denotes a binomial coefficient
:$H_k$ denotes the $k$th harmonic number
:$0 < \epsilon < \dfrac 1 {x \paren {n + 1} }$
=== Result for $x = -1$ ===
== Proof ==
Let $S_n := \ds \sum_{k \mathop \in \Z} \binom n k x^k H_k$.
Then:
As $S_1 = x$, we have that:
From Corollary to Power Series Expansion for $\map \ln {1 + x}$ we have:
:$\ds \map \ln {1 - z} = -\sum_{k \mathop \ge 1} \frac {z^k} k$
Hence by Logarithm of Reciprocal we have:
:$\ds \ln \frac 1 {1 - z} = -\map \ln {1 - z} = \sum_{k \mathop \ge 1} \frac {z^k} k$
Thus:
So as $n \to \infty$, $\ds \sum_{k \mathop \ge 1} \frac 1 {k \paren {x + 1}^k}$ converges, and so:
The result follows.
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Theorem $\text A$
Category:Harmonic Numbers
Category:Binomial Coefficients
Sum over k of n Choose k by x to the k by kth Harmonic Number/x = -1

== Theorem ==
While for $x \in \R_{>0}$ be a real number:
:$\ds \sum_{k \mathop \in \Z} \binom n k x^k H_k = \paren {x + 1}^n \paren {H_n - \map \ln {1 + \frac 1 x} } + \epsilon$
when $x = -1$ we have:
:$\ds \sum_{k \mathop \in \Z} \binom n k x^k H_k = \dfrac {-1} n$
where:
:$\dbinom n k$ denotes a binomial coefficient
:$H_k$ denotes the $k$th harmonic number.
== Proof ==
When $x = -1$ we have that $1 + \dfrac 1 x = 0$, so $\map \ln {1 + \dfrac 1 x}$ is undefined.
Let $S_n = \ds \sum_{k \mathop \in \Z} \binom n k x^k H_k$
Then:
Setting $x = -1$:
== Sources ==
* : $\S 1.2.7$: Harmonic Numbers: Exercise $9$
Category:Harmonic Numbers
Category:Binomial Coefficients
Sum over k of r+tk choose k by s-tk choose n-k

== Theorem ==
Let $n \in \Z_{\ge 0}$ be a non-negative integer.
Then:
:$\ds \sum_k \dbinom {r + t k} k \dbinom {s - t k} {n - k} = \sum_{k \mathop \ge 0} \dbinom {r + s - k} {n - k} t^k$
where $\dbinom {r + t k} k$ and so on denotes a binomial coefficient.
== Proof ==
Let $\map f {r, s, t, n}$ be the function defined as:
:$\ds \map f {r, s, t, n} := \sum_k \dbinom {r + t k} k \dbinom {s - t k} {n - k}$
We have:
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $28$
Category:Binomial Coefficients
Sum over k of r-k Choose m by s+k Choose n

== Theorem ==
Let $m, n, r, s \in \Z_{\ge 0}$ such that $n \ge s$.
Then:
:$\ds \sum_{k \mathop = 0}^r \binom {r - k} m \binom {s + k} n = \binom {r + s + 1} {m + n + 1}$
where $\dbinom {r - k} m$ etc. are binomial coefficients.
== Proof ==
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: $\text {I} \ (25)$
Category:Binomial Coefficients
Sum over k of r-k Choose m by s Choose k-t by -1^k-t

== Theorem ==
Let $s \in \R, r, t, m \in \Z_{\ge 0}$.
Then:
:$\ds \sum_{k \mathop = 0}^r \binom {r - k} m \binom s {k - t} \paren {-1}^{k - t} = \binom {r - t - s} {r - t - m}$
where $\dbinom {r - k} m$ etc. are binomial coefficients.
== Proof ==
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: $\text {I} \ (24)$
Category:Binomial Coefficients
Sum over k of r-kt Choose k by r over r-kt by s-(n-k)t Choose n-k by s over s-(n-k)t

== Theorem ==
For $n \in \Z_{\ge 0}$:
:$\ds \sum_k \map {A_k} {r, t} \map {A_{n - k} } {s, t} = \map {A_n} {r + s, t}$
where $\map {A_n} {x, t}$ is the polynomial of degree $n$ defined as:
:$\map {A_n} {x, t} = \dbinom {x - n t} n \dfrac x {x - n t}$
where $x \ne n t$.
== Proof 1 ==
== Proof 2 ==
Category:Binomial Coefficients
Category:Sum over k of r-kt Choose k by r over r-kt by s-(n-k)t Choose n-k by s over s-(n-k)t
Sum over k of r-kt Choose k by r over r-kt by s-(n-k)t Choose n-k by s over s-(n-k)t/Proof 1

== Theorem ==
== Proof ==
Let:
:$\ds S = \sum_k \map {A_k} {r, t} \map {A_{n - k} } {s, t}$
Both sides of the statement of the theorem are polynomials in $r$, $s$ and $t$.
Therefore it can be assumed that $r \ne k t \ne s$ for $0 \le k \le n$ or something will become undefined.
By replacing the polynomials $A_n$ with their binomial coefficient definitions, the theorem can be expressed as:
:$\ds S = \sum_k \dbinom {r - k t} k \dbinom {s - \paren {n - k} t} {n - k} \dfrac r {r - k t} \dfrac s {s - \paren {n - k} t}$
Using the technique of partial fractions:
:$\dfrac 1 {r - k t} \dfrac 1 {s - \paren {n - k} t} = \dfrac 1 {r + s - n t} \paren {\dfrac 1 {r - k t} + \dfrac 1 {s - \paren {n - k} t} }$
Thus:
:$\ds S = \frac s {r + s - n t} \sum_k \dbinom {r - k t} k \dbinom {s - \paren {n - k} t} {n - k} \dfrac r {r - k t} + \frac r {r + s - n t} \sum_k \dbinom {r - k t} k \dbinom {s - \paren {n - k} t} {n - k} \dfrac s {s - \paren {n - k} t}$
From Sum over $k$ of $\dbinom {r - t k} k \dbinom {s - t \paren {n - k} } {n - k} \dfrac r {r - t k}$:
:$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$
for $r, s, t \in \R, n \in \Z$.
Thus we have:
:$S = \dfrac s {r + s - n t} \dbinom {r + s - t n} n + \dfrac r {r + s - n t} \dbinom {s + r - t n} n$
after changing $k$ to $n - k$ in the second term.
That is:
:$S = \dbinom {r + s - n t} n \dfrac {r + s} {r + s - n t}$
which is $\map {A_n} {r + s, t}$.
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Example $4$
Category:Sum over k of r-kt Choose k by r over r-kt by s-(n-k)t Choose n-k by s over s-(n-k)t
Sum over k of r-kt Choose k by r over r-kt by s-(n-k)t Choose n-k by s over s-(n-k)t/Proof 2

== Theorem ==
== Proof ==
From Sum over $k$ of $\dbinom {r - k t} k$ by $\dfrac r {r - k t}$ by $z^k$:
:$\ds \sum_k \map {A_k} {r, t} z^k = x^r$
and:
:$\ds \sum_k \map {A_k} {s, t} z^k = x^s$
Hence:
Taking the $z^n$ coefficient:
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $27$
Category:Sum over k of r-kt Choose k by r over r-kt by s-(n-k)t Choose n-k by s over s-(n-k)t
Sum over k of r-kt choose k by r over r-kt by z^k

== Theorem ==
Let $n \in \Z_{\ge 0}$ be a positive integer.
Let $\map {A_n} {x, t}$ be the polynomial of degree $n$ defined as:
:$\map {A_n} {x, t} := \dbinom {x - n t} n \dfrac x {x - n t}$
for $x \ne n t$.
Let $z = x^{t + 1} - x^t$.
Then:
:$\ds \sum_k \map {A_k} {r, t} z^k = x^r$
for sufficiently small $z$.
== Proof ==
From Sum over $k$ of $\paren {-1}^k$ by $\dbinom n k$ by $\dbinom {r - k t} n$ by $\dfrac r {r - k t}$ and renaming variables:
:$\ds \sum_j \paren {-1}^j \dbinom k j \dbinom {r - j t} k \dfrac r {r - j t} = \delta_{k 0}$
where $\delta_{k 0}$ is the Kronecker delta.
Thus:
:$\ds \sum_{j, k} \paren {-1}^j \dbinom k j \dbinom {r - j t} k \dfrac r {r - j t} w^k = 1$
We have:
Now let:
:$x = \dfrac 1 {1 + w}$
Thus:
== Also see ==
* Binomial Theorem: obtained by setting $t = 0$ in this result
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $25$
* : $\S 1.2.9$: Generating Functions: $(21)$
Category:Binomial Coefficients
Sum over k of r-kt choose k by z^k

== Theorem ==
Let $n \in \Z_{\ge 0}$ be a non-negative integer.
Then:
:$\ds \sum_k \dbinom {r - t k} k z^k = \frac {x^{r + 1} } {\paren {t + 1} x - t}$
where $\dbinom {r - t k} k$ denotes a binomial coefficient.
== Proof 1 ==
== Proof 2 ==
Category:Binomial Coefficients
Category:Sum over k of r-kt choose k by z^k
Sum over k of r-kt choose k by z^k/Proof 1

== Theorem ==
== Proof ==
From Sum over $k$ of $\dbinom r k$ by $\dbinom {s - k t} r$ by $\paren {-1}^k$ and renaming variables:
:$\ds \sum_j \paren {-1}^j \binom k j \binom {r - j t} k = t^k$
Thus:
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $26$
Category:Sum over k of r-kt choose k by z^k
Sum over k of r-kt choose k by z^k/Proof 2

== Theorem ==
== Proof ==
From Sum over $k$ of $\dbinom {r - k t} k$ by $\dfrac r {r - k t}$ by $z^k$:
:$\ds (1): \quad \sum_k \map {A_k} {r, t} z^k = x^r$
where:
:$\map {A_n} {x, t}$ is the polynomial of degree $n$ defined as:
::$\map {A_n} {x, t} := \dbinom {x - n t} n \dfrac x {x - n t}$
:for $x \ne n t$
:$z = x^{t + 1} - x^t$.
Differentiating $(1)$ $z$:
We have:
Hence:
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $26$
Category:Sum over k of r-kt choose k by z^k
Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk

== Theorem ==
Let $r, s, t \in \R, n \in \Z$.
Then:
:$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$
where $\dbinom {r - t k} k$ and so on are binomial coefficients.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: $\text {I} \ (26)$
Category:Binomial Coefficients
Category:Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk
Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk/Proof 1

== Theorem ==
== Proof ==
For all $n \in \Z$, let $\map P n$ be the proposition:
:$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$
Let the of this equation be denoted $\tuple {r, s, t, n}$.
Let $n = 0$.
Then:
Thus $\map P 0$ holds.
Let $n < 0$.
Let $n = -m$ where $m > 0$.
Then:
Thus $\map P n$ holds for all $n < 0$.
It remains to demonstrate that $\map P n$ holds for all $n > 0$.
The proof continues by strong induction on $n$.
The procedure is to substitute $n - r + n t + m$ for the variable $s$ and establish that the identity holds for all $m \ge 0$.
For all $m \in \Z_{\ge 0}$, let $\map P m$ be the proposition:
:$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {\paren {n - r + n t + m} - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + \paren {n - r + n t + m} - t n} n$
That is:
:$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - r + m + t k} {n - k} \frac r {r - t k} = \binom {n + m} n$
=== Basis for the Induction ===
Consider the special case where $s = n - 1 - r + n t$.
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 m$, then it logically follows that $\map P {m + 1}$ is true.
This is the induction hypothesis:
:$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - r + m + t k} {n - k} \frac r {r - t k} = \binom {n + m} n$
from which it is to be shown that:
:$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - r + m + 1 + t k} {n - k} \frac r {r - t k} = \binom {n + m + 1} n$
=== Lemma ===
First a lemma:
=== Induction Step ===
This is the induction step:
We have that $\tuple {r, n - 1 - r + n t, t, n}$ holds.
We have also determined that if:
:$\tuple {r, s, t, n}$ holds
and:
:$\tuple {r, s - t, t, n - 1}$ holds
then:
:$\tuple {r, s + 1, t, n}$ holds.
So $\map P m \implies \map P {m + 1}$.
Thus $\tuple {r, s, t, n}$ is shown to hold for infinitely many $s$.
As both the and are polynomials in $s$ it follows that $\tuple {r, s, t, n}$ holds for all $s$.
Therefore:
:$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \left({n - k}\right)} {n - k} \frac r {r - t k} = \binom {r + s - t n} n$
for all $r, s, t \in \R, n \in \Z$.
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $24$
Category:Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk