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:

$\displaystyle \sum_k \dbinom {r - t k} k z^k = \frac {x^{r + 1} } {\left({t + 1}\right)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$:

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

\(\displaystyle \sum_k \map {A_k} {r, t} k z^{k - 1}\) \(=\) \(\displaystyle \frac {\d} {\d z} x^r\) Power Rule for Derivatives
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum_k \map {A_k} {r, t} k z^k\) \(=\) \(\displaystyle z \frac {\d} {\d z} x^r\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {x^{t + 1} - x^t} r x^{r - 1} \frac {\d x} {\d z}\) Chain Rule


We have:

\(\displaystyle z\) \(=\) \(\displaystyle x^{t + 1} - x^t\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \frac {\d z} {\d x}\) \(=\) \(\displaystyle \paren {t + 1} x^t - t x^{t - 1}\) Power Rule for Derivatives
\(\displaystyle \leadsto \ \ \) \(\displaystyle \frac {\d x} {\d z}\) \(=\) \(\displaystyle \frac 1 {\paren {t + 1} x^t - t x^{t - 1} }\) Derivative of Inverse Function


Hence:

\(\displaystyle \sum_k k \map {A_k} {r, t} z^k\) \(=\) \(\displaystyle \frac {\paren {x^{t + 1} - x^t} r x^{r - 1} } {\paren {t + 1} x^t - t x^{t - 1} }\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {\paren {x - 1} r x^r} {\paren {t + 1} x - t}\) simplifying
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum_k \map {A_k} {r, t} z^k - \frac t r \sum_k k \map {A_k} {r, t} z^k\) \(=\) \(\displaystyle x^r - \frac t r \frac {\left({x - 1}\right) r x^r} {\paren {t + 1} x - t}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum_k \paren {1 - \frac t r k} \map {A_k} {r, t} z^k\) \(=\) \(\displaystyle \frac {\paren {\paren {t + 1} x - t} x^r - t \paren {x - 1} x^r} {\paren {t + 1} x - t}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {x^{r + 1} } {\paren {t + 1} x - t}\) simplifying
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum_k \frac {r - t k} r \dbinom {r - k t} k \dfrac r {r - k t} z^k\) \(=\) \(\displaystyle \frac {x^{r + 1} } {\paren {t + 1} x - t}\) substituting for $\map {A_k} {r, t}$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum_k \dbinom {r - k t} k z^k\) \(=\) \(\displaystyle \frac {x^{r + 1} } {\paren {t + 1} x - t}\) simplifying

$\blacksquare$


Sources