Sum over k of r-kt choose k by z^k/Proof 2
Jump to navigation
Jump to search
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
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)$ with respect to $z$:
\(\ds \sum_k \map {A_k} {r, t} k z^{k - 1}\) | \(=\) | \(\ds \frac \d {\d z} x^r\) | Power Rule for Derivatives | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_k \map {A_k} {r, t} k z^k\) | \(=\) | \(\ds z \frac \d {\d z} x^r\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {x^{t + 1} - x^t} r x^{r - 1} \frac {\d x} {\d z}\) | Chain Rule for Derivatives |
We have:
\(\ds z\) | \(=\) | \(\ds x^{t + 1} - x^t\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \frac {\d z} {\d x}\) | \(=\) | \(\ds \paren {t + 1} x^t - t x^{t - 1}\) | Power Rule for Derivatives | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \frac {\d x} {\d z}\) | \(=\) | \(\ds \frac 1 {\paren {t + 1} x^t - t x^{t - 1} }\) | Derivative of Inverse Function |
Hence:
\(\ds \sum_k k \map {A_k} {r, t} z^k\) | \(=\) | \(\ds \frac {\paren {x^{t + 1} - x^t} r x^{r - 1} } {\paren {t + 1} x^t - t x^{t - 1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {x - 1} r x^r} {\paren {t + 1} x - t}\) | simplifying | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_k \map {A_k} {r, t} z^k - \frac t r \sum_k k \map {A_k} {r, t} z^k\) | \(=\) | \(\ds x^r - \frac t r \frac {\paren {x - 1} r x^r} {\paren {t + 1} x - t}\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_k \paren {1 - \frac t r k} \map {A_k} {r, t} z^k\) | \(=\) | \(\ds \frac {\paren {\paren {t + 1} x - t} x^r - t \paren {x - 1} x^r} {\paren {t + 1} x - t}\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {x^{r + 1} } {\paren {t + 1} x - t}\) | simplifying | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_k \frac {r - t k} r \dbinom {r - k t} k \dfrac r {r - k t} z^k\) | \(=\) | \(\ds \frac {x^{r + 1} } {\paren {t + 1} x - t}\) | substituting for $\map {A_k} {r, t}$ | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_k \dbinom {r - k t} k z^k\) | \(=\) | \(\ds \frac {x^{r + 1} } {\paren {t + 1} x - t}\) | simplifying |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $26$