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

[RChristenk]

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.

 

[anuttarasammyak]

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 ?

 

[pasmith]

It is probably clearer to use factorial notation, noting that $n - (r - 1) = n - r + 1 = n + 1 - r$: $$\frac{n!}{(n-r)!r!} + \frac{n!}{(n-(r-1))!(r-1)!} =\frac{(n+1 - r)n! + r n!}{(n+1-r)!r!}$$

 

[BvU]

Beat me to it! Twice ! darn phone, darn $\LaTeX$ curly brackets

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

$\$

 

[anuttarasammyak]

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.

 

[PeroK]

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$$

 

[docnet]

Beat me to it! Twice ! darn phone, darn $\LaTeX$ curly brackets

You must have the patience of a god to type $LATEX$ on the phone.

 

[BvU]

Mere mortal -- after ' some frustration' had to retreat to the desktop in my study...

 

[PeroK]

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.

 

[docnet]

I'm doing all my posts on the phone this week.

Mere mortal -- after ' some frustration' had to retreat to the desktop in my study...

Now I'm wondering what you all do for day work

 

[Orodruin]

Speaking of $\LaTeX$ …

$^{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}$.

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$ …

 

[docnet]

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$?

 

[Orodruin]

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.

 

[renormalize]

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}$.

 

[Orodruin]

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.