Sum of r+k Choose k up to n

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $r \in \R$ be a real number.

Then:

$\ds \forall n \in \Z: n \ge 0: \sum_{k \mathop = 0}^n \binom {r + k} k = \binom {r + n + 1} n$

where $\dbinom r k$ is a binomial coefficient.


Proof

Proof by induction:

For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition

$\ds \sum_{k \mathop = 0}^n \binom {r + k} k = \binom {r + n + 1} n$


Basis for the Induction

$\map P 0$ is true, as $\dbinom r 0 = 1 = \dbinom {r + 1} 0$ by definition.

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $\map P m$ is true, where $m \ge 0$, then it logically follows that $\map P {m + 1}$ is true.


So this is our induction hypothesis:

$\ds \sum_{k \mathop = 0}^m \binom {r + k} k = \binom {r + m + 1} m$


Then we need to show:

$\ds \sum_{k \mathop = 0}^{m + 1} \binom {r + k} k = \binom {r + m + 2} {m + 1}$


Induction Step

This is our induction step:

\(\ds \sum_{k \mathop = 0}^{m + 1} \binom {r + k} k\) \(=\) \(\ds \sum_{k \mathop = 0}^m \binom {r + k} k + \binom {r + m + 1} {m + 1}\)
\(\ds \) \(=\) \(\ds \binom {r + m + 1} m + \binom {r + m + 1} {m + 1}\) from the induction hypothesis
\(\ds \) \(=\) \(\ds \binom {r + m + 2} {m + 1}\) Pascal's Rule

So $\map P m \implies \map P {m + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\ds \forall n \in \Z_{\ge 0}: \sum_{k \mathop = 0}^n \binom {r + k} k = \binom {r + n + 1} n$

$\blacksquare$


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_of_r%2Bk_Choose_k_up_to_n&oldid=533410"