Intereting Posts

Evaluate $\int_{0}^{\infty} \mathrm{e}^{-x^2-x^{-2}}\, dx$
Calculate sums of inverses of binomial coefficients
Prove that the limit of $\sqrt{n+1}-\sqrt{n}$ is zero
Recursive Mapping
Simple examples of $3 \times 3$ rotation matrices
Is the $\mathfrak m$-adic completion of a radical ideal again a radical ideal?
Explicit examples of infinitely many irreducible polynomials in k
Limits of sequences connected with real and complex exponential
Hartshorne Exercise II. 3.19 (c)
Negative × Negative = Positive… right?
Hard binomial sum
how to solve $\sum _{m=0}^{k-1}mC_{k-1}^{m}C_{N-k}^{m}$?
What is the derivative of: $f(x)=x^{2x^{3x^{4x^{5x^{6x^{7x^{.{^{.^{.}}}}}}}}}}$?
If a function $f(x)$ is Riemann integrable on $$, is $f(x)$ bounded on $$?
Show that $\mathbb{Q}(6^{1/3})$ and $\mathbb{Q}(12^{1/3})$ have the same degree and discriminant but are not isomorphic.

Prove that $\binom{n+0}0 + \binom{n+1}1 +\binom{n+2}2

+\ldots+\binom{n+r}r = \binom{n+r+1}r$ using combinatoric arguments.

**(EDITED)**

I want to see if I understood Brian M. Scott’s approach so I will try again using an analogical approach.

- How to show $\binom{2p}{p} \equiv 2\pmod p$?
- Number of monomials of certain degree
- proving an invloved combinatorial identity
- Proving $\sum_{k=0}^n{2k\choose k}{2n-2k\choose n-k}=4^n$
- Proving the total number of subsets of S is equal to $2^n$
- Sum of products of binomial coefficients: $ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $

$\binom{n+0}0 + \binom{n+1}1 +\binom{n+2}2

+\ldots+\binom{n+r}r = \binom{n+r+1}r$ can be rewritten as $\binom{n+0}n + \binom{n+1}n +\binom{n+2}n

+\ldots+\binom{n+r}n = \binom{n+r+1}{n+1}$

We can use the analogy of people lining up to buy tickets to see a concert. Let’s say there are only $n$ number of tickets available for sale. “Choosing” who gets to attend the concert can be done in two ways.

The first way (the RHS), we have $n+1$ number of tickets for sale but $n+r+1$ people who wants to buy the tickets. Thus, there are $\binom{n+r+1}{n+1}$ ways to “choose” who gets to attend the concert.

The second way (the LHS) is to select the last person in line to buy the first ticket (I think this was the step I missed in my first attempt). Then, we choose $n$ from the remaining $n+r$ people to buy tickets. Or we can ban the last person in line from buying a ticket and choose the second-to-last person in line to buy the first ticket. Then, we have $\binom{n+r-1}n$ ways. This continues until we reach the case where we choose the $n+1$ person in line to buy the first ticket (banning everyone behind him/her from buying a ticket). This can be done in $\binom{n+0}n$ ways.

Therefore, adding up each case on the LHS is equal to the RHS.

- How many ways to put 20 things to different 4 boxes?
- What is the number of ways to select ten distinct letters from the alphabet $\{a, b, c, \ldots, z\}$, if no two consecutive letters can be selected?
- Combinatorially prove that $\sum_{i=0}^n {n \choose i} 2^i = 3^n $
- Combination problem distributing
- How prove binomial cofficients $\sum_{k=0}^{}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=}^n\binom{n+1}{k}\binom{k}{n-k}$
- Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?
- Negative Exponents in Binomial Theorem
- Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even
- Show this equality (The factorial as an alternate sum with binomial coefficients).
- Evaluate a sum with binomial coefficients: $\sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$

You’re on the right track, but you have a discrepancy between choosing $r$ from $n+r+1$ on the right, and choosing $r$ from $n+r$ on the left, so what you have doesn’t quite work. Here’s an approach that does work and is quite close in spirit to what you’ve tried.

Let $A=\{0,1,\ldots,n+r\}$; clearly $|A|=n+r+1$, so $\binom{n+r+1}r$ is the number of $r$-sized subsets of $A$. Now let’s look at a typical term on the lefthandside. The term $\binom{n+k}k$ is the number of ways to choose a $k$-sized subset of $\{0,1,\ldots,n+k-1\}$; how does that fit in with choosing an $r$-sized subset of $A$?

Let $n+k$ be the largest member of $A$ that we do *not* pick for our $r$-sized subset; then we’ve chosen all of the $(n+r)-(n+k)=r-k$ members of $A$ that are bigger than $n+k$, so we must fill out our set by choosing $k$ members of $A$ that are smaller than $n+k$, i.e., $k$ members of the set $\{0,1,\ldots,n+k-1\}$. In other words, there are $\binom{n+k}k$ ways to choose our $r$-sized subset of $A$ so that $n+k$ is the largest member of $A$ that is *not* in our set. And that largest number not in our set cannot be any larger than $n$, so the choices for it are $n+0,\ldots,n+r$. Thus, $\sum_{k=0}^r\binom{n+k}k$ counts the $r$-sized subsets of $A$ by classifying them according to the largest member of $A$ that they do *not* contain.

It may be a little easier to see what’s going on if you make use of symmetry to rewrite the identity as

$$\sum_{k=0}^r\binom{n+k}n=\binom{n+r+1}{n+1}\;.\tag{1}$$

Let $A$ be as above; the righthand side of $(1)$ is clearly the number of $(n+1)$-sized subsets of $A$. Now let $S$ be an arbitrary $r$-sized subset of $A$. The largest element of $S$ must be one of the numbers $n,n+1,\ldots,n+r$, i.e., one of the numbers $n+k$ for $k=0,\ldots,r$. And if $n+k$ is the largest element of $S$, there are $\binom{n+k}n$ ways to choose the $n$ smaller members of $S$. Thus, the lefthand side of $(1)$ also counts the $(n+1)$-sized subsets of $A$, classifying them according to their largest elements.

The relationship between the two arguments is straightforward: the sets that I counted in the first argument are the complements in $A$ of the sets that I counted in the second argument. There’s a bijection between the $r$-subsets of $A$ and their complementary $(n+1)$-subsets of $A$, so your identity and $(1)$ are essentially saying the same thing.

Let $d=n+1$. Try to find out the dimension of the space of polynomials of degree less than or equal to $r$ in two different ways: Method A is direct and gives the RHS. Method B sums up the polynomials that have degree exactly equal to $k$ for $0\leq k\leq r$.

Method A: Check that the map $x^{\alpha}\mapsto \{1+\alpha_1,2+\alpha_1+\alpha_2,\dots,d+\alpha_1+\dots+\alpha_d\}$ is a bijection of the space of polynomials to the subsets of cardinality $r$ of $\{1,\dots,d+r\}$.

Method B: For each $k$ find a similar (but not at all equivalent) map to find the numbers of polynomials that have exactly degree $k$. Hint: Think of the degree 6 polynomial $x_1^2 x_2^3x_3$ for example as $(1,1,2,2,2,3)$. This thinking gives you an identification of polynomials with degree $k=6$ with $6$ drawings out of $d=3$ balls, with replacing balls after every draw. The trick now is again to identify something like $(1,1,2,2,2,3)$ with a subset of $\{1,\dots,k+d=6+3\}$ by adding to each element of the ordered list in order to avoid repeats.

Fix any $r$ of the $n+r+1$ objects and label them $A_1,A_2,…A_r.$Now, $n+r+1$ may or may not contain all or any number from the set {$A_1,A_2,…A_r$}.

Case 1-It does not contain $A_1$

This will happen in $n+r\choose r$ ways as $r$ things are to be chosen from remaining $n+r$ things.

Case 2-It does not contain $A_2$ but contains $A_1$.

This happens in $n+r-1\choose r-1$ ways.

Case r-It contains $A_1,A_2…A_{r-1}$ but not $A_r$.

This will happen in $n+r-(r-1)\choose 1$ ways=$n+1\choose 1$ ways.

Case r+1- It contains $A_1,A_2,A_3…A_r$

This happens in $n\choose 0$ ways.

Thus,adding we get,

$$\binom n 0 + \binom {n+1} 1 + \binom {n+2} 2+\cdots+ \binom {n+r} r=\binom {n+r+1} r$$

- Higher Dimenional Tic Tac Toe
- A very general method for proving inequalities. Too good to be true?
- Having a plane equation equaled to zero for calculating its angle with another plane
- Volume of the projection of the unit cube on a hyperplane
- measurability of supremum of a class of functions
- Prove that $\lim_{N\rightarrow\infty}(1/N)\sum_{n=1}^N f(nx)=\int_{0}^1f(t)dt$
- Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a function such that $f'(x)$ is continuous and $|f'(x)|\le|f(x)|$ for all $x\in\mathbb{R}$
- If space of bounded operators L(V,W) is Banach, V nonzero, then W is Banach (note direction of implication)
- Why characters are continuous
- Non-integer order derivative
- Finding a closed form for $\cos{x}+\cos{3x}+\cos{5x}+\cdots+\cos{(2n-1)x}$
- How to geometrically show that there are $4$ $S_3$ subgroups in $S_4$?
- Suppose that each of the row sums of an $n\times n$ matrix $A$ is equal to zero. Show that $A$ must be singular.
- The transpose of a linear injection is surjective.
- Completness and Set of Result of One Set ?!?