Show that ${n+1 \choose r+1}={n \choose r}+{n \choose r+1}$, from a more intuitive sense From a more intuitive sense, why the following formula is true? 
$${n+1 \choose r+1}={n \choose r}+{n \choose r+1}$$
Although I can prove the above formula by using ${n \choose r}=\frac{n!}{r!(n-r)!}$, but the following explanation makes no sense to me:

Let A be a set containing n+1 elements, and suppose
  $x\in A$. The left side of above formula counts the number of
  (r+1)-element subsets of A. We can separate these subsets into two groups: 
(1) those containing x, and (2) those not containing x. 
If x is in the subset, then we must select r other elements
  from the remaining n elements of A to form an (r+1)-element
  subset. There are ${n \choose r}$ ways of choosing these r elements. 
If x is not in the subset, we must select r+1 elements from
  the remaining n elements of A. There are ${n \choose r+1}$ ways of
  choosing these elements. 
Thus, the number of (r+1)-element subsets from the (n+1)-element set A
  equals the number of (r+1)-element subsets containing x plus the
  number of (r+1)-element subsets not containing x.

So, in the cases of x is in the subset, and x is not in the subset, how do we obtain ${n \choose r}$ and ${n \choose r+1}$? 
Above quoted explanation sounds confusing to me. What are the "remaining n elements"? Don't we have n+1 elements in this case, how can we choose r+1 elements from n?
 A: A size-$r+1$ subset $S$ of $A$ is said to own those $y$ for which $y\in S$. Then $S$ is specified by identifying which $r$ elements of $A\setminus\{x\}$ it owns if $x\in S$, or which $r+1$ elements of $A\setminus\{x\}$ it owns if $x\not\in S$. The former case comprises $\binom{|A\setminus\{x\}|}{r}=\binom{|A|-1}{r}=\binom{n}{r}$ choices for $S$, the latter $\binom{n}{r+1}$ of them.
A: 
What are the "remaining n elements"?

That are all elements of $A$ that differ from $x\in A$. 
You could say that $A=B\cup\{x\}$ where $B$ has $n$ elements that all differ from $x$. 
There are $\binom{n}{r}$ subsets of $B$ that contain exactly $r$ elements and each of these sets induces a subset of $A$ that contains $r+1$ elements by adding $x$ as element to that set (so any set $C\subseteq B$ with $|C|=r$ induces set $C\cup\{x\}\subseteq A$).
Further there are $\binom{n}{r+1}$ subsets of $B$ that contain exactly $r+1$ elements and they are also subsets of $A$ (so any set $C\subseteq B$ with $|C|=r+1$ induces set $C\subseteq A$).
Each subset of $A$ that contains exactly $r+1$ elements belongs to one of the sort so that $$\binom{n+1}{r+1}=\binom{n}{r}+\binom{n+1}{r+1}$$I hope this spreads some light.
A: This can be seen really simply by replacing all of the variables with small numbers.
$\binom{5}{3}=10$ is the number of 3 element subsets of {1,2,3,4,5}.  Ten isn't too many, so let's list them: {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}.
Now, let's split them into two different categories: those that contain 5 and those that don't.  


*

*The second category is {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}.  Clearly those are just the 3 element subsets of {1,2,3,4}, so there are $\binom{4}{3}$ of them.  

*The first category is {1,2,5}, {1,3,5}, {1,4,5}, {2,3,5}, {2,4,5}, {3,4,5}.  If you think about it, those are all of the 2 element subsets of {1,2,3,4} combined with the singleton {5}.  Since there is a one-to-one correspondence there, there must be $\binom{4}{2}$ of those.


Since we have accounted for every 3 element subset of {1,2,3,4,5} exactly once, we have demonstrated that $\binom{5}{3}=\binom{4}{3}+\binom{4}{2}$.
