Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $r, s, t \in \R, n \in \Z$.

Then:

$\displaystyle \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$

where $\dbinom {r - t k} k$ etc. are binomial coefficients.


Proof 1

For all $n \in \Z$, let $P \left({n}\right)$ be the proposition:

$\displaystyle \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$

Let the left hand side of this equation be denoted $\left({r, s, t, n}\right)$.


Let $n = 0$.

Then:

\(\displaystyle \) \(\) \(\displaystyle \left({r, s, t, 0}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s + t k} {- k} \frac r {r - t k}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s + t k} {- k} \frac r {r - t k} \delta_{k 0}\) N Choose Negative Number is Zero: $\dbinom {s + t k} {- k} = 0$ for all $k > 0$
\(\displaystyle \) \(=\) \(\displaystyle \binom r 0 \binom s 0\) Definition of Kronecker Delta
\(\displaystyle \) \(=\) \(\displaystyle 1\) Binomial Coefficient with Zero
\(\displaystyle \) \(=\) \(\displaystyle \binom {r + s} 0\) Binomial Coefficient with Zero
\(\displaystyle \) \(=\) \(\displaystyle \binom {r + s - t n} n\) putting $n = 0$

Thus $P \left({0}\right)$ holds.


Let $n < 0$.

Let $n = -m$ where $m > 0$.

Then:

\(\displaystyle \) \(\) \(\displaystyle \left({r, s, t, n}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \left({- m - k}\right)} {- m - k} \frac r {r - t k}\)
\(\displaystyle \) \(=\) \(\displaystyle 0\) N Choose Negative Number is Zero: $\dbinom {s - t \left({- m - k}\right)} {- m - k} = 0$
\(\displaystyle \) \(=\) \(\displaystyle \binom {r + s + t m} {-m}\) N Choose Negative Number is Zero: $\dbinom {r + s + t m} {-m} = 0$ for all $m$

Thus $P \left({n}\right)$ holds for all $n < 0$.


It remains to demonstrate that $P \left({n}\right)$ 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 $P \left({m}\right)$ be the proposition:

$\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {\left({n - r + n t + m}\right) - t \left({n - k}\right)} {n - k} \frac r {r - t k} = \binom {r + \left({n - r + n t + m}\right) - t n} n$

That is:

$\displaystyle \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$.


Substituting $n - 1 - r + n t$ for $s$ in the right hand side:

\(\displaystyle \binom {r + s - t n} n\) \(=\) \(\displaystyle \binom {r + \left({n - 1 - r + n t}\right) - t n} n\)
\(\displaystyle \) \(=\) \(\displaystyle \binom {r + n - 1 - r + n t - t n} n\)
\(\displaystyle \) \(=\) \(\displaystyle \binom {n - 1} n\)


Substituting $n - 1 - r + n t$ for $s$ in the left hand side:

\(\displaystyle \) \(\) \(\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - 1 - r + t k} {n - k} \frac r {r - t k}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop \ge 0} \dfrac {\left({r - t k}\right)! \left({n - 1 - r + t k}\right)! \, r} {k! \left({r - t k - k}\right)! \left({n - k}\right)! \left({k - 1 - r + t k}\right)! \left({r - t k}\right)}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \dfrac {\left({r - t k - 1}\right)! \left({n - 1 - r + t k}\right)!} {\left({r - t k - k}\right)! \left({k - 1 - r + t k}\right)!}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \prod_{0 \mathop < j \mathop < k} \left({r - t k - j}\right) \prod_{0 \mathop < j \mathop < n \mathop - k} \left({n - 1 - r + t k - j}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \left({-1}\right)^{k - 1} \prod_{0 \mathop < j \mathop < k} \left({-r + t k + j}\right) \prod_{k \mathop \le j \mathop < n} \left({- r + t k + j}\right)\)


The two products give a polynomial of degree $n - 1$ in $k$.

Hence the sum for all $k$ is $0$.


Thus we have:

\(\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - 1 - r + t k} {n - k} \frac r {r - t k}\) \(=\) \(\displaystyle 0\)
\(\displaystyle \) \(=\) \(\displaystyle \binom {n - 1} n\) Definition of Binomial Coefficient

Thus the equation indeed holds for the special case where $s = n - 1 - r + n t$.

$\Box$


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $P \left({j}\right)$ is true, for all $j$ such that $0 \le j \le m$, then it logically follows that $P \left({m + 1}\right)$ is true.


This is the induction hypothesis:

$\displaystyle \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:

$\displaystyle \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:

Let this hold for $\left({r, s, t, n}\right)$:

$\displaystyle \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$

and also for $\left({r, s - t, t, n - 1}\right)$.

Then it also holds for $\left({r, s + 1, t, n}\right)$.


Induction Step

This is the induction step:

We have that $\left({r, n - 1 - r + n t, t, n}\right)$ holds.

We have also determined that if:

$\left({r, s, t, n}\right)$ holds

and:

$\left({r, s - t, t, n - 1}\right)$ holds

then:

$\left({r, s + 1, t, n}\right)$ holds.


So $P \left({m}\right) \implies P \left({m + 1}\right)$.


Thus $\left({r, s, t, n}\right)$ is shown to hold for infinitely many $s$.

As both the left hand side and right hand side are polynomials in $s$ it follows that $\left({r, s, t, n}\right)$ holds for all $s$.

Therefore:

$\displaystyle \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$.

$\blacksquare$


Proof 2

From Sum over $k$ of $\dbinom {r - k t} k$ by $\dfrac r {r - k t}$ by $z^k$:

$\displaystyle \sum_k A_k \left({r, t}\right) z^k = x^r$

where:

$A_n \left({x, t}\right)$ is the polynomial of degree $n$ defined as:
$A_n \left({x, t}\right) := \dbinom {x - n t} n \dfrac x {x - n t}$
for $x \ne n t$
$z = x^{t + 1} - x^t$.


From Sum over $k$ of $\dbinom {r - k t} k$ by $z^k$:

$\displaystyle \sum_k \dbinom {r - t k} k z^k = \frac {x^{r + 1} } {\left({t + 1}\right)x - t}$


Thus:

\(\displaystyle \sum_k A_k \left({r, t}\right) z^k \sum_k \dbinom {s - t k} k z^k\) \(=\) \(\displaystyle \frac {x^r x^{s + 1} } {\left({t + 1}\right)x - t}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {x^{\left({r + s}\right) + 1} } {\left({t + 1}\right)x - t}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_k \dbinom {r + s - t k} k z^k\)


Equating coefficients of $z$:

\(\displaystyle \sum_k A_k \left({r, t}\right) z^k \sum_k \dbinom {s - \left({n - k}\right) t} k z^{n - k}\) \(=\) \(\displaystyle \binom {r + s - n t} n z^n\)
\(\displaystyle \sum_k \dbinom {r - k t} k \dfrac r {r - k t} z^k \dbinom {s - \left({n - k}\right) t} k z^{n - k}\) \(=\) \(\displaystyle \binom {r + s - n t} n z^n\)
\(\displaystyle \sum_k \dbinom {r - k t} k \dbinom {s - \left({n - k}\right) t} k \dfrac r {r - k t}\) \(=\) \(\displaystyle \binom {r + s - t n} n\)

$\blacksquare$


Sources