# Sum over k of r-kt choose k by z^k

## 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 1

From Sum over $k$ of $\dbinom r k$ by $\dbinom {s - k t} r$ by $\left({-1}\right)^k$ and renaming variables:

$\displaystyle \sum_j \left({-1}\right)^j \binom k j \binom {r - j t} k = t^k$

Thus:

 $\displaystyle \sum_{j, k} \binom k j \binom {r - j t} k \left({-1}\right)^j$ $=$ $\displaystyle \sum_{k \mathop \ge 0} t^k$ when $k < 0$ we have $\dbinom {r - j t} k = 0$ $\displaystyle \leadsto \ \$ $\displaystyle \sum_j \left({-1}\right)^j \sum_k \binom k j \binom {r - j t} k$ $=$ $\displaystyle \frac 1 {1 - t}$ Sum of Infinite Geometric Progression $\displaystyle \leadsto \ \$ $\displaystyle \sum_j \left({-1}\right)^j \sum_k \binom {r - j t} j \binom {r - j t - k} {j - k}$ $=$ $\displaystyle \frac 1 {1 - t}$ Product of $\dbinom r m$ with $\dbinom m k$ $\displaystyle \leadsto \ \$ $\displaystyle \sum_j \left({-1}\right)^j \binom {r - j t} j \sum_k \binom {r - j t - k} {j - k}$ $=$ $\displaystyle \frac 1 {1 - t}$

## Proof 2

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