# Sum over k of -1^k by n choose k by r-kt choose n by r over r-kt

Jump to navigation
Jump to search

## Theorem

- $\displaystyle \sum_k \left({-1}\right)^k \dbinom n k \dbinom {r - k t} n \dfrac r {r - k t} = \delta_{n 0}$

where $\delta_{n 0}$ is the Kronecker delta.

## Proof

The proof proceeds by induction.

For all $n \in \Z_{\ge 0}$, let $P \left({n}\right)$ be the proposition:

- $\displaystyle \sum_k \left({-1}\right)^k \dbinom n k \dbinom {r - k t} n \dfrac r {r - k t} = \delta_{n 0}$

### Basis for the Induction

$P \left({0}\right)$ is the case:

\(\displaystyle \sum_k \left({-1}\right)^k \dbinom 0 k \dbinom {r - k t} 0 \dfrac r {r - k t}\) | \(=\) | \(\displaystyle \sum_k \left({-1}\right)^k \delta_{0 k} \dbinom {r - k t} 0 \dfrac r {r - k t}\) | Zero Choose n | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \dbinom r 0 \dfrac r r\) | All terms but for $k = 0$ vanish | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle 1\) | Binomial Coefficient with Zero | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \delta_{0 0}\) |

Thus $P \left({0}\right)$ is seen to hold.

### Induction Hypothesis

Now it needs to be shown that, if $P \left({j}\right)$ is true, where $j \ge 0$, then it logically follows that $P \left({j + 1}\right)$ is true.

So this is the induction hypothesis:

- $\displaystyle \sum_k \left({-1}\right)^k \dbinom j k \dbinom {r - k t} j \dfrac r {r - k t} = \delta_{j 0}$

from which it is to be shown that:

- $\displaystyle \sum_k \left({-1}\right)^k \dbinom {j + 1} k \dbinom {r - k t} {j + 1} \dfrac r {r - k t} = \delta_{\left({j + 1}\right) 0}$

### Induction Step

This is the induction step:

\(\displaystyle \) | \(\) | \(\displaystyle \sum_k \left({-1}\right)^k \dbinom {j + 1} k \dbinom {r - k t} {j + 1} \dfrac r {r - k t}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_k \left({-1}\right)^k \left({\dbinom j k + \dbinom j {k - 1} }\right) \dbinom {r - k t} {j + 1} \dfrac r {r - k t}\) | Definition of Binomial Coefficient |

So $P \left({r}\right) \implies P \left({r + 1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore:

- $\displaystyle \forall n \in \Z_{\ge 0} \sum_k \left({-1}\right)^k \dbinom n k \dbinom {r - k t} n \dfrac r {r - k t} = \delta_{n 0}$