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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestSolutionWe 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)\]

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}\)

Log in to reply

I'm interested in combinatorial proof for this problem.

Log in to reply

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

Log in to reply

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}\] ~~~

Log in to reply

Yep!

Log in to reply

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

Log in to reply

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

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

Log in to reply