Linked Questions
35 questions linked to/from Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$
11
votes
3
answers
74k
views
why is ${n+1\choose k} = {n\choose k} + {n\choose k-1}$? [duplicate]
Can someone explain to me the proof of $${n+1\choose k} = {n\choose k} + {n\choose k-1}$$?
- 163
8
votes
2
answers
819
views
What's the intuition behind this equality involving combinatorics? [duplicate]
What is the intuition behind
$$
\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}
$$
? I can't grasp why picking a group of $k$ out of $n$ bijects to first picking a group of $k-1$ out of $n-1$ ...
- 2,734
0
votes
3
answers
26k
views
Show that $C(n,k) = C(n-1,k) + C(n-1,k-1)$ [duplicate]
I'm studying for my final for Statistics, and I want to understand literally every problem in my textbook (at least in the first 7 chapters).
One of the problems asks to show that ${n}\choose {k}$ $=$...
- 335
2
votes
2
answers
28k
views
Prove that $\binom{n+1}k = \binom nk + \binom n {k-1}$ [duplicate]
As the title says.
Prove that ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$
It looks to me like induction but since there are two variables, I'm not really sure how to even set up a base case. ...
- 601
5
votes
4
answers
3k
views
What is the story behind ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$? [duplicate]
By exploring the inductive proof from this question
I came to the point where I did not understand this step:
$${n+1 \choose k} = {n \choose k} + {n \choose k-1}$$
There is a wikipedia article but ...
- 585
4
votes
3
answers
2k
views
Proving an Combination formula $ \binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}$ [duplicate]
Proving an Combination formula $\displaystyle \binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}$
$\bf{My Try}$::$\displaystyle{\binom{n-1}{k}+\binom{n-1}{k-1}=}$
$\displaystyle{\frac{\left(n-1\right)!}{...
- 53.8k
2
votes
4
answers
2k
views
Prove that $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1} $ [duplicate]
Prove that $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1} $
Thanks in advance, my professor asked us to this a couple weeks ago, but I was enable to get to the right answer.
Good luck!
Here is ...
- 103
0
votes
4
answers
1k
views
Show that ${n\choose r}={{n-1}\choose{r-1}}+{{n-1}\choose {r}}$. [duplicate]
Show that ${n\choose r}={{n-1}\choose{r-1}}+{{n-1}\choose {r}}$.
My try:
$$\dfrac{n!}{(n-r)!\;r!}=\dfrac{(n-1)!}{(n-r)!(r-1)!}+\dfrac{(n-1)!}{(n-1-r)!\;r!}$$
Multiplying all terms by $r!(n-r)!$
$$n!=...
- 6,915
3
votes
2
answers
612
views
Combinatorial Proof Of ${n \choose k}={n-1\choose {k-1}}+{n-1\choose k}$ [duplicate]
So I know that the combinatorial explanation is has following:
let there be 2 group A= x is chosen (${n-1\choose {k-1}}$) and B=x is not chosen (${n-1\choose k}$)
so $A\cup B= |A|+|B|$ therefore:
${...
- 13.1k
0
votes
4
answers
249
views
Why is ${{n+1}\choose{k}}={{n}\choose{k-1}}+{{n}\choose{k}}$? [duplicate]
My teacher showed us a proof by induction for this equation for $n\in\mathbb{N}$:
$$\sum\limits_{k=0}^n{{n}\choose{k}} = 2^n$$
In the first step, this sum is rewritten using ${{n+1}\choose{k}}={{n}\...
user63495
-1
votes
1
answer
818
views
Prove ${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$ using any particular number [duplicate]
I didn't really understand this proof to begin with, and I really don't understand what this question is asking. Do I just let n equal some number and then try to prove it from there, how do I begin ...
0
votes
1
answer
608
views
Pascal's Rule: How to prove? [duplicate]
Possible Duplicate:
Proving ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$
I have a dilemma here, how can we show Pascal's Rule :
Show that
$$
\binom{n}{r} =...
- 543
1
vote
3
answers
95
views
Proving Pascal's Rule : $\binom n k =\binom{n−1}{ k−1}+\binom{n−1} k $ [duplicate]
I have taken the R.H.S and used the combination formula $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
then I don't know other steps to solve it.
-1
votes
1
answer
164
views
How to prove Pascal's identity? [duplicate]
As I understand Pascal's identity is defined as
$$\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$$
Just as an exercise I decided to prove this identity. Here is my solution:
$$
\begin{...
- 139
-1
votes
3
answers
196
views
How to prove: $^nC_r + ^nC_{r+1} = ^{n+1}C_{r+1}$ [duplicate]
Prove: ${^n}C_r + ^nC_{r+1} = ^{n+1}C_{r+1}$
I used $^nC_r = \frac{(n!)}{(n-r)!r!}$ and then did my substitutions:
$ = \frac{(n!)}{(n-r)!r!} + \frac{(n!)}{(n-(r+1))!(r+1)!}$
$ = \frac{(n!)}{(n-r)!...
- 39