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

## 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$ by $\dbinom {s - k t} r$ by $\paren {-1}^k$ and renaming variables:

$\displaystyle \sum_j \paren {-1}^j \binom k j \binom {r - j t} k = t^k$

Thus:

 $\displaystyle \sum_{j, k} \binom k j \binom {r - j t} k \paren {-1}^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 \paren {-1}^j \sum_k \binom k j \binom {r - j t} k$ $=$ $\displaystyle \frac 1 {1 - t}$ Sum of Infinite Geometric Sequence $\displaystyle \leadsto \ \$ $\displaystyle \sum_j \paren {-1}^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 \paren {-1}^j \binom {r - j t} j \sum_k \binom {r - j t - k} {j - k}$ $=$ $\displaystyle \frac 1 {1 - t}$