Sum of Multisets

Prove that k=1n(k+p1p)=(n+pp+1).\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

k=1n(k+p1p)=k=1n1p!k(k+1)(k+2)...(k+p1)\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

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

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

By hypothesis, when n=in=i, k=1i1p!k(k+1)(k+2)...(k+p1)=1(p+1)!i(i+1)(i+2)...(i+p)\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+1n=i+1: k=1i+11p!k(k+1)(k+2)...(k+p1)=1(p+1)!(i+1)(i+2)(i+3)...(i+p+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 k=1i1p!k(k+1)(k+2)...(k+p1)+1p!(i+1)(i+2)(i+3)...(i+p)=(i+p+1p+1)\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)

(i+pp+1)+(i+pp)=(i+p+1p+1)\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)

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

Therefore, k=1n(k+p1p)=(n+pp+1)\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
4 years, 11 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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 </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Solution

We prove by induction.

First note that

k=1n(k+p1p)=k=1n1p!k(k+1)(k+2)...(k+p1)=1(p+1)!n(n+1)(n+2)...(n+p)\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=1n=1: 1p!1(2)(3)...(p)=1\frac{1}{p!}1(2)(3)...(p) = 1 1(p+1)!1(2)(3)...(p+1)=1\frac{1}{(p+1)!}1(2)(3)...(p+1) = 1

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

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

Let k=n+1k=n+1: k=1n+11p!k(k+1)(k+2)...(k+p1)=1(p+1)!(n+1)(n+2)(n+3)...(n+p+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)

k=1n1p!k(k+1)(k+2)...(k+p1)+1p!(n+1)(n+2)(n+3)...(n+p)=(n+p+1p+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)

(n+pp+1)+(n+pp)=(n+p+1p+1)\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)

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

Therefore, k=1n(k+p1p)=(n+pp+1)\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 - 4 years, 10 months ago

Log in to reply

Proof by induction:

Base case: n=1n=1:

i=11(i+P1p)=(p+1p+1)\displaystyle \sum_{i=1}^{1} \dbinom{i+P-1}{p}= \dbinom{p+1}{p+1}

\Rightarrow (pp)=1\dbinom{p}{p} = 1

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

i=1k(i+p1p)=(k+pp+1)\displaystyle \sum_{i=1}^{k} \dbinom{i+p-1}{p}= \dbinom{k+p}{p+1}

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

\Rightarrow (k+pp)+i=1k(i+p1p)=(k+p)!(p+1)!(k1)!+(k+pp)\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 i=1k+1(i+p1p)=(k+p)!p!(k)(k1)!+(k+p)!(p+1)!(k1)! \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 i=1k+1(i+p1p)=(k+p)!(p+1)+k(k+p)!(p+1)!(k)!\displaystyle \sum_{i=1}^{k+1} \dbinom{i+p-1}{p}= \frac{(k+p)!(p+1) +k(k+p)!}{(p+1)!(k)!}

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

\Rightarrow i=1k+1(i+p1p)=(k+p+1p+1)\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=1n=1 and that if the statement is true for some n=kn=k, then it is true for n=k+1n=k+1. The proof follows by induction. QED

A Brilliant Member - 4 years, 10 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 - 4 years, 10 months ago

Log in to reply

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

Steven Zheng - 4 years, 10 months ago

Log in to reply

I'm interested in combinatorial proof for this problem.

Samuraiwarm Tsunayoshi - 4 years, 9 months ago

Log in to reply

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

Steven Zheng - 4 years, 9 months ago

Log in to reply

There we go.

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

We'll count this in another way.

Let SAS \subseteq A such that SS has p+1p+1 elements.

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

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

General case: 1,2,3,,k1∉S1,2,3,\dots,k-1 \not \in S, but kSk \in S, we have to choose pp elements from n+pkn+p-k elements left ({k+1,k+2,,n+p}\{ k+1,k+2,\dots,n+p\}) for SS. So we have (n+pkp)\dbinom{n+p-k}{p} subsets for all k=1,2,,nk = 1,2,\dots,n

Sum all these cases we get k=1n(n+pkp)=k=1n(k+p1p)\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,

k=1n(k+p1p)=(n+pp+1)\sum\limits_{k=1}^{n} \dbinom{k+p-1}{p} = \dbinom{n+p}{p+1} ~~~

Samuraiwarm Tsunayoshi - 4 years, 7 months ago

Log in to reply

Yep!

Samuraiwarm Tsunayoshi - 4 years, 9 months ago

Log in to reply

Another simple proof would be :

Writing the sum as

k=0n1(k+pk)\displaystyle \sum_{k=0}^{n-1}{\binom{k+p}{k}}

Now, we will use the Pascal's Triangle formula that (nk)=(n1k)+(n1k1)\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} by writing (p+n1n1)=(p+nn1)(p+n1n2)\binom{p+n-1}{n-1} = \binom{p + n}{n-1} - \binom{p+n-1}{n-2}

and then adding to the previous term (p+n2n2)(p+n1n2)=(p+n2n3)\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 (p0)(p+10)=0\binom{p}{0} - \binom{p+1}{0} = 0

Hence, the only term left would be (p+nn1)=(n+pp+1)\binom{p+n}{n-1} = \binom{n+p}{p+1}

Kartik Sharma - 3 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...