# 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 2011. 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
5 years, 6 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

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

- 5 years, 5 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

- 5 years, 5 months ago

can anyone give me some notes of lessons lines and angles and triangles with inequalities and with sums

- 5 years, 5 months ago

You can try typing "lines and angles" in the search. Quite a lot of people wrote notes on plane geometry.

- 5 years, 5 months ago

I'm interested in combinatorial proof for this problem.

- 5 years, 5 months ago

Do you mean a proof using combinations theorem and not induction?

- 5 years, 5 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}$ ~~~

- 5 years, 2 months ago

Yep!

- 5 years, 5 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}$

- 4 years, 3 months ago