×

# Sum of Multisets

Prove that $\sum _{ k=1 }^{ n }{ \left( \begin{matrix} k+p-1 \\ p \end{matrix} \right) } =\left( \begin{matrix} n+p \\ p+1 \end{matrix} \right) .$

I discovered this formula in 2010. Somebody probably discovered this in the past but I'm not certain whether it is a well-known formula.

Solution

We prove by induction.

First note that

$\sum _{ k=1 }^{ n }{ \left( \begin{matrix} k+p-1 \\ p \end{matrix} \right) } = \sum _{ k=1 }^{ n }\frac{1}{p!}k(k+1)(k+2)...(k+p-1)$

and

$\left( \begin{matrix} n+p \\ p+1 \end{matrix} \right) = \frac{1}{(p+1)!}n(n+1)(n+2)...(n+p)$

When $$n=1$$, $\frac{1}{p!}1(2)(3)...(p) = 1$ $\frac{1}{(p+1)!}1(2)(3)...(p+1) = 1$

By hypothesis, when $$n=i$$, $\sum _{ k=1 }^{i }\frac{1}{p!}k(k+1)(k+2)...(k+p-1) = \frac{1}{(p+1)!}i(i+1)(i+2)...(i+p)$

If $$n=i+1$$: $\sum _{ k=1 }^{ i+1 }\frac{1}{p!}k(k+1)(k+2)...(k+p-1) = \frac{1}{(p+1)!}(i+1)(i+2)(i+3)...(i+p+1)$

then $\sum _{ k=1 }^{ i }\frac{1}{p!}k(k+1)(k+2)...(k+p-1) + \frac{1}{p!}(i+1)(i+2)(i+3)...(i+p)= \left( \begin{matrix} i+p+1 \\ p+1 \end{matrix} \right)$

$\left( \begin{matrix} i+p \\ p+1 \end{matrix} \right) + \left( \begin{matrix} i+p \\ p \end{matrix} \right) = \left( \begin{matrix} i+p+1 \\ p+1 \end{matrix} \right)$

$\left( \begin{matrix} i+p+1 \\ p+1 \end{matrix} \right) = \left( \begin{matrix} i+p+1 \\ p+1 \end{matrix} \right)$

Therefore, $\sum _{ k=1 }^{ n }{ \left( \begin{matrix} k+p-1 \\ p \end{matrix} \right) } = \left( \begin{matrix} n+p \\ p+1 \end{matrix} \right)$

Check out my other notes at Proof, Disproof, and Derivation

Note by Steven Zheng
2 years, 10 months ago

Sort by:

Solution

We prove by induction.

First note that

$\sum _{ k=1 }^{ n }{ \left( \begin{matrix} k+p-1 \\ p \end{matrix} \right) } = \sum _{ k=1 }^{ n }\frac{1}{p!}k(k+1)(k+2)...(k+p-1) = \frac{1}{(p+1)!}n(n+1)(n+2)...(n+p)$

When $$n=1$$: $\frac{1}{p!}1(2)(3)...(p) = 1$ $\frac{1}{(p+1)!}1(2)(3)...(p+1) = 1$

When $$n=2$$: $1+\frac{1}{p!}2(3)(4)...(p+1) = p+2$ $\frac{1}{(p+1)!}2(3)(4)...(p+2) = p+2$

When $$n=3$$: $(p+2)+\frac{1}{p!}3(4)(5)...(p+2) = \frac{1}{2!}(p+2)(p+3)$ $\frac{1}{(p+1)!}3(4)(5)...(p+3) = \frac{1}{2!}(p+2)(p+3)$

Let $$k=n+1$$: $\sum _{ k=1 }^{ n+1 }\frac{1}{p!}k(k+1)(k+2)...(k+p-1) = \frac{1}{(p+1)!}(n+1)(n+2)(n+3)...(n+p+1)$

$\sum _{ k=1 }^{ n }\frac{1}{p!}k(k+1)(k+2)...(k+p-1) + \frac{1}{p!}(n+1)(n+2)(n+3)...(n+p)= \left( \begin{matrix} n+p+1 \\ p+1 \end{matrix} \right)$

$\left( \begin{matrix} n+p \\ p+1 \end{matrix} \right) + \left( \begin{matrix} n+p \\ p \end{matrix} \right) = \left( \begin{matrix} n+p+1 \\ p+1 \end{matrix} \right)$

$\left( \begin{matrix} n+p+1 \\ p+1 \end{matrix} \right) = \left( \begin{matrix} n+p+1 \\ p+1 \end{matrix} \right)$

Therefore, $\sum _{ k=1 }^{ n }{ \left( \begin{matrix} k+p-1 \\ p \end{matrix} \right) } = \left( \begin{matrix} n+p \\ p+1 \end{matrix} \right)$ · 2 years, 9 months ago

Another simple proof would be :

Writing the sum as

$$\displaystyle \sum_{k=0}^{n-1}{\binom{k+p}{k}}$$

Now, we will use the Pascal's Triangle formula that $$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$ by writing $$\binom{p+n-1}{n-1} = \binom{p + n}{n-1} - \binom{p+n-1}{n-2}$$

and then adding to the previous term $$\binom{p+n-2}{n-2} - \binom{p+n-1}{n-2} = \binom{p+n-2}{n-3}$$ and so on till the first term $$\binom{p}{0} - \binom{p+1}{0} = 0$$

Hence, the only term left would be $$\binom{p+n}{n-1} = \binom{n+p}{p+1}$$ · 1 year, 7 months ago

I'm interested in combinatorial proof for this problem. · 2 years, 9 months ago

Do you mean a proof using combinations theorem and not induction? · 2 years, 9 months ago

There we go.

Let $$A = \{ 1,2,\dots,n+p \}$$ for all $$p \leq n$$. The number of subsets of $$A$$ with $$p+1$$ elements are $\dbinom {n+p}{p+1}$

We'll count this in another way.

Let $$S \subseteq A$$ such that $$S$$ has $$p+1$$ elements.

Case 1: $$1 \in S$$, we have to choose $$p$$ elements from $$n+p-1$$ left ($$\{ 2,3,\dots,n+p\}$$) for $$S$$. So we have $$\dbinom{n+p-1}{p}$$ subsets.

Case 2: $$1 \not \in S$$, but $$2 \in S$$, we have to choose $$p$$ elements from $$n+p-2$$ left ($$\{ 3,4,\dots,n+p\}$$) for $$S$$. So we have $$\dbinom{n+p-2}{p}$$ subsets.

General case: $$1,2,3,\dots,k-1 \not \in S$$, but $$k \in S$$, we have to choose $$p$$ elements from $$n+p-k$$ elements left ($$\{ k+1,k+2,\dots,n+p\}$$) for $$S$$. So we have $$\dbinom{n+p-k}{p}$$ subsets for all $$k = 1,2,\dots,n$$

Sum all these cases we get $\sum\limits_{k=1}^{n} \dbinom{n+p-k}{p} = \sum\limits_{k=1}^{n} \dbinom{k+p-1}{p}$.

From these 2 ways of counting are the same way, therefore,

$\sum\limits_{k=1}^{n} \dbinom{k+p-1}{p} = \dbinom{n+p}{p+1}$ ~~~ · 2 years, 7 months ago

Yep! · 2 years, 9 months ago

can anyone give me some notes of lessons lines and angles and triangles with inequalities and with sums · 2 years, 9 months ago

You can try typing "lines and angles" in the search. Quite a lot of people wrote notes on plane geometry. · 2 years, 9 months ago

Proof by induction:

Base case: $$n=1$$:

$$\displaystyle \sum_{i=1}^{1} \dbinom{i+P-1}{p}= \dbinom{p+1}{p+1}$$

$$\Rightarrow$$ $$\dbinom{p}{p} = 1$$

The base case clearly holds. Now the inductive case $$n=k$$:

$$\displaystyle \sum_{i=1}^{k} \dbinom{i+p-1}{p}= \dbinom{k+p}{p+1}$$

$$\Rightarrow$$ $$\displaystyle \sum_{i=1}^k \dbinom{i+p-1}{p}= \frac {(k+p)!}{(p+1)!(k-1)!}$$

$$\Rightarrow$$ $$\dbinom{k+p}{p} + \displaystyle \sum_{i=1}^k \dbinom{i+p-1}{p}=\frac{(k+p)!}{(p+1)!(k-1)!} +\dbinom{k+p}{p}$$ (By hypothesis)

$$\Rightarrow$$ $$\displaystyle \sum_{i=1}^{k+1} \dbinom{i+p-1}{p}= \frac{(k+p)!}{p!(k)(k-1)!} + \frac{(k+p)!}{(p+1)!(k-1)!}$$

$$\Rightarrow$$ $$\displaystyle \sum_{i=1}^{k+1} \dbinom{i+p-1}{p}= \frac{(k+p)!(p+1) +k(k+p)!}{(p+1)!(k)!}$$

$$\Rightarrow$$ $$\displaystyle \sum_{i=1}^{k+1} \dbinom{i+p-1}{p}= \frac{(k+p+1)!}{(p+1)!(k)!}$$

$$\Rightarrow$$ $$\displaystyle \sum_{i=1}^{k+1} \dbinom{i+p-1}{p}= \dbinom{k+p+1}{p+1}$$

Then we may conclude that the statement is true for $$n=1$$ and that if the statement is true for some $$n=k$$, then it is true for $$n=k+1$$. The proof follows by induction. QED · 2 years, 9 months ago