Show that ##^{n+1}C_r=^nC_r+^nC_{r-1}##

In summary, the identity \( ^{n+1}C_r = ^nC_r + ^nC_{r-1} \) demonstrates that the number of ways to choose \( r \) items from \( n+1 \) items can be derived by considering two cases: either the \( n+1 \)th item is included in the selection, which corresponds to choosing \( r-1 \) items from the first \( n \) items, or the \( n+1 \)th item is not included, which corresponds to choosing \( r \) items from the first \( n \) items. This combinatorial argument validates the identity using the concept of binomial coefficients.
  • #1
RChristenk
64
9
Homework Statement
Show that ##^{n+1}C_r=^nC_r+^nC_{r-1}##
Relevant Equations
Basic combination theory
##^nC_r=\dfrac{n(n-1)(n-2)...(n-r+2)(n-r+1)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}##

##^nC_{r-1}=\dfrac{n(n-1)(n-2)...(n-r+2)}{1\cdot2\cdot3...\cdot(r-1)}##

##^nC_r+^nC_{r-1}=\dfrac{[n(n-1)(n-2)...(n-r+2)](n-r+1+r)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}=\dfrac{(n+1)(n)(n-1)...(n-r+2)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}##

But ##^{n+1}C_r=\dfrac{(n+1)(n)(n-1)...(n-r+1)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}##

So where did I go wrong? Thanks.
 
Physics news on Phys.org
  • #2
RChristenk said:
Homework Statement: Show that ##^{n+1}C_r=^nC_r+^nC_{r-1}##
Relevant Equations: Basic combination theory

##^nC_r=\dfrac{n(n-1)(n-2)...(n-r+2)(n-r+1)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}##

##^nC_{r-1}=\dfrac{n(n-1)(n-2)...(n-r+2)}{1\cdot2\cdot3...\cdot(r-1)}##

##^nC_r+^nC_{r-1}=\dfrac{[n(n-1)(n-2)...(n-r+2)](n-r+1+r)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}=\dfrac{(n+1)(n)(n-1)...(n-r+2)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}##

But ##^{n+1}C_r=\dfrac{(n+1)(n)(n-1)...(n-r+1)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}##

So where did I go wrong? Thanks.
In your formula of
##^nC_r=\dfrac{n(n-1)(n-2)...(n-r+2)(n-r+1)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}##
replacing n to n+1, we get
##^{(n+1)}C_r=\dfrac{(n+1)n(n-1)(n-2)...(n+1-r+2)(n+1-r+1)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}##
, which is different from your last line. Which is correct ?
 
  • Like
Likes RChristenk
  • #3
It is probably clearer to use factorial notation, noting that [itex]n - (r - 1) = n - r + 1 = n + 1 - r[/itex]: [tex]
\frac{n!}{(n-r)!r!} + \frac{n!}{(n-(r-1))!(r-1)!} =\frac{(n+1 - r)n! + r n!}{(n+1-r)!r!}[/tex]
 
  • #4
Beat me to it! Twice ! darn phone, darn ##\LaTeX## curly brackets :wink:

Comment on the notation: it's a lot easier when you write ## ^nC_r={n \choose r}={n!\over (n-r)! r!} ## : $$
\begin{align*}
{n+1 \choose r} &={(n+1!)\over (n+1-r)!\; r!}\\ \ \\ &= {n+1\over n+1-r}{n\choose r} \\ \ \\&={n\choose r} + {r\over n+1-r}{n\choose r}\\ \ \\&={n\choose r} + {r\over n-(r-1)}{n\choose r}\\ \ \\&={n\choose r} +{n\choose r-1}\end{align*}\\ \ \\ $$


Old dutch expression: too late, like mustard when the meal is already over :frown:

##\ ##
 
  • Like
Likes PeroK
  • #5
RChristenk said:
Homework Statement: Show that ##^{n+1}C_r=^nC_r+^nC_{r-1}##
We choose r elements from n+1 elements.
Say an element we look is not chosen, we choose r elements from the rest n elements.
Say an element we look is chosen, we choose r-1 elements from the rest n elements.
 
  • #6
It's simpler to start with the right hand side:
$$\binom n r +\binom n {r-1} = \frac{n!}{(n-r)!r! }+ \frac{n!}{(n-r+1)!(r-1)!}$$$$=\frac{n!(n-r+1) +n!r}{(n-r+1)!r!}$$$$= \frac{(n+1)!}{(n+1-r)!r!} = \binom{n+1}r$$
 
  • Like
Likes BvU
  • #7
BvU said:
Beat me to it! Twice ! darn phone, darn ##\LaTeX## curly brackets :wink:
You must have the patience of a god to type ##LATEX## on the phone.
 
  • Like
Likes PeroK
  • #8
Mere mortal :smile: -- after ' some frustration' had to retreat to the desktop in my study...
 
  • Like
Likes docnet
  • #9
docnet said:
You must have the patience of a god to type ##LATEX## on the phone.
I'm doing all my posts on the phone this week.
 
  • Wow
Likes docnet
  • #10
PeroK said:
I'm doing all my posts on the phone this week.
BvU said:
Mere mortal :smile: -- after ' some frustration' had to retreat to the desktop in my study...
Now I'm wondering what you all do for day work 🤔
 
  • #11
Speaking of ##\LaTeX## …

RChristenk said:
##^{n+1}C_r=^nC_r+^nC_{r-1}##

##^nC_r+^nC_{r-1}##
This looks quite miserable. You see, ##\LaTeX## interprets ^{} as belonging to whatever came before. Rater than ##= {}^nC_r## it has interpreted it as ##=^n## and then ##C_r##, etc.

There are packages that more or less solve this, but those generally won’t be available here. The closest you will get is something like {}^nC_r, which is what was used above. You can also opt for the alternative notation {n \choose r} ##{n \choose r}##.

PeroK said:
I'm doing all my posts on the phone this week.
I would say I do about 80% of my posts on mobile. Including some pretty heavy on ##\LaTeX## …
 
  • Like
  • Informative
Likes MatinSAR and docnet
  • #12
Orodruin said:
Speaking of ##\LaTeX## …


This looks quite miserable. You see, ##\LaTeX## interprets ^{} as belonging to whatever came before. Rater than ##= {}^nC_r## it has interpreted it as ##=^n## and then ##C_r##, etc.

There are packages that more or less solve this, but those generally won’t be available here. The closest you will get is something like {}^nC_r, which is what was used above. You can also opt for the alternative notation {n \choose r} ##{n \choose r}##.


I would say I do about 80% of my posts on mobile. Including some pretty heavy on ##\LaTeX## …
Good point! I didn't notice that before. So why not just put the ##^n## on the right like ##C^n_r##?
 
  • #13
docnet said:
Good point! I didn't notice that before. So why not just put the ##^n## on the right like ##C^n_r##?
That is an alternative notation, but presumably not the one used by OP’s course material.
 
  • Informative
Likes docnet
  • #14
Orodruin said:
This looks quite miserable. You see, ##\LaTeX## interprets ^{} as belonging to whatever came before. Rater than ##= {}^nC_r## it has interpreted it as ##=^n## and then ##C_r##, etc.
You can also use the construct "{}^{a+b}_{\phantom{1}-\theta}X_{\pm}^{r+1}" to get fairly well-aligned prescripts: ##{}^{a+b}_{\phantom{1}-\theta}X_{\pm}^{r+1}##.
 
  • Like
Likes MatinSAR and docnet
  • #15
renormalize said:
You can also use the construct "{}^{a+b}_{\phantom{1}-\theta}X_{\pm}^{r+1}" to get fairly well-aligned prescripts: ##{}^{a+b}_{\phantom{1}-\theta}X_{\pm}^{r+1}##.
Sure, but that is not necessary in this case. \phantom also comes with its own limitations. Particularly when the characters you want to align have different widths, such as ##{}^{a+i}_{\phantom{a}-m}C##, which looks absolutely horrible.
 
  • Like
Likes MatinSAR and docnet

FAQ: Show that ##^{n+1}C_r=^nC_r+^nC_{r-1}##

What does the notation ##^{n+1}C_r## represent?

The notation ##^{n+1}C_r## represents the binomial coefficient, which is the number of ways to choose r elements from a set of (n+1) elements without regard to the order of selection. It is also known as a combination.

How can we interpret the identity ##^{n+1}C_r=^nC_r+^nC_{r-1}## combinatorially?

Combinatorially, this identity can be interpreted by considering a set of (n+1) elements. We can either include a specific element in our selection or not. If we include that specific element, we need to choose (r-1) elements from the remaining n elements, which is ##^nC_{r-1}##. If we do not include that specific element, we need to choose r elements from the remaining n elements, which is ##^nC_r##. Summing these two scenarios gives us the total number of ways to choose r elements from (n+1) elements, which is ##^{n+1}C_r##.

Can you derive the identity ##^{n+1}C_r=^nC_r+^nC_{r-1}## algebraically?

Yes, we can derive it algebraically using the definition of binomial coefficients. By definition, ##^{n+1}C_r = \frac{(n+1)!}{r!(n+1-r)!}##. We can rewrite the factorial terms to show that ##^{n+1}C_r = \frac{(n+1)!}{r!(n+1-r)!} = \frac{(n+1) \cdot n!}{r!(n+1-r) \cdot n!} = \frac{(n+1)}{r} \cdot \frac{n!}{(r-1)!(n-r)!} + \frac{n!}{r!(n-r)!} = ^nC_r + ^nC_{r-1}##.

How is this identity used in Pascal's Triangle?

This identity is fundamental to the construction of Pascal's Triangle. Each entry in Pascal's Triangle is the sum of the two entries directly above it. Specifically, the entry in the (n+1)th row and rth column is the sum of the entries in the nth row and rth column and the nth row and (r-1)th column, which is exactly the statement of the identity ##^{n+1}C_r=^nC_r+^nC_{r-1}##.

Why is this identity important

Back
Top