Sum over k of r-kt choose k by z^k/Proof 2

From ProofWiki
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