Waste less time on Facebook — follow Brilliant.
×

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
3 years ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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)\] Steven Zheng · 2 years, 11 months ago

Log in to reply

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}\) Kartik Sharma · 1 year, 9 months ago

Log in to reply

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

Log in to reply

@Samuraiwarm Tsunayoshi Do you mean a proof using combinations theorem and not induction? Steven Zheng · 2 years, 11 months ago

Log in to reply

@Steven Zheng 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}\] ~~~ Samuraiwarm Tsunayoshi · 2 years, 9 months ago

Log in to reply

@Steven Zheng Yep! Samuraiwarm Tsunayoshi · 2 years, 11 months ago

Log in to reply

can anyone give me some notes of lessons lines and angles and triangles with inequalities and with sums Ṡḁḧḭtḧ Ṙṏẏal · 2 years, 11 months ago

Log in to reply

@Ṡḁḧḭtḧ Ṙṏẏal You can try typing "lines and angles" in the search. Quite a lot of people wrote notes on plane geometry. Steven Zheng · 2 years, 11 months ago

Log in to reply

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 Ethan Robinett · 2 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...