Menu Close

prove-that-k-1-2k-r-0-k-1-r-k-r-1-k-

Tinku Tara 0 Comments
Pin




Question Number 164555 by mnjuly1970 last updated on 18/Jan/22
prove that ( _( k−1) ^(2k) ) =^? Σ_(r=0) ^(k−1) ( _( r) ^( k) ) (^( ) _( r+1) ^( k) ) −−−−
$$ \\ $$$$\:\:\:{prove}\:\:{that} \\ $$$$\: \\ $$$$\:\:\:\:\:\:\left(\underset{\:{k}−\mathrm{1}} {\overset{\mathrm{2}{k}} {\:}}\:\right)\:\overset{?} {=}\:\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\:\left(\:\underset{\:{r}} {\overset{\:{k}} {\:}}\:\:\:\right)\:\overset{\:\:} {\left(}\underset{\:{r}+\mathrm{1}} {\overset{\:\:{k}} {\:}}\:\right) \\ $$$$\:\:−−−− \\ $$
Answered by mr W last updated on 19/Jan/22
(1+x)^(2k) =(1+x)^k (1+x)^k Σ_(q=0) ^(2k) (((2k)),(q) )x^q =[Σ_(r=0) ^k ((k),(r) )x^r ][Σ_(p=0) ^k ((k),(p) )x^p ] let′s see term x^q with q=k−1 r+p=k−1 ⇒p=k−1−r≥0 ⇒r≤k−1 (((2k)),((k−1)) )=Σ_(r=0) ^(k−1) ((k),(r) ) ((k),((k−r−1)) ) (((2k)),((k−1)) )=Σ_(r=0) ^(k−1) ((k),(r) ) ((k),((r+1)) ) ✓
$$\left(\mathrm{1}+{x}\right)^{\mathrm{2}{k}} =\left(\mathrm{1}+{x}\right)^{{k}} \left(\mathrm{1}+{x}\right)^{{k}} \\ $$$$\underset{{q}=\mathrm{0}} {\overset{\mathrm{2}{k}} {\sum}}\begin{pmatrix}{\mathrm{2}{k}}\\{{q}}\end{pmatrix}{x}^{{q}} =\left[\underset{{r}=\mathrm{0}} {\overset{{k}} {\sum}}\begin{pmatrix}{{k}}\\{{r}}\end{pmatrix}{x}^{{r}} \right]\left[\underset{{p}=\mathrm{0}} {\overset{{k}} {\sum}}\begin{pmatrix}{{k}}\\{{p}}\end{pmatrix}{x}^{{p}} \right] \\ $$$${let}'{s}\:{see}\:{term}\:{x}^{{q}} \:{with}\:{q}={k}−\mathrm{1} \\ $$$${r}+{p}={k}−\mathrm{1} \\ $$$$\Rightarrow{p}={k}−\mathrm{1}−{r}\geqslant\mathrm{0}\:\Rightarrow{r}\leqslant{k}−\mathrm{1} \\ $$$$\begin{pmatrix}{\mathrm{2}{k}}\\{{k}−\mathrm{1}}\end{pmatrix}=\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\begin{pmatrix}{{k}}\\{{r}}\end{pmatrix}\begin{pmatrix}{{k}}\\{{k}−{r}−\mathrm{1}}\end{pmatrix} \\ $$$$\begin{pmatrix}{\mathrm{2}{k}}\\{{k}−\mathrm{1}}\end{pmatrix}=\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\begin{pmatrix}{{k}}\\{{r}}\end{pmatrix}\begin{pmatrix}{{k}}\\{{r}+\mathrm{1}}\end{pmatrix}\:\checkmark \\ $$
Commented by mnjuly1970 last updated on 19/Jan/22
excellent sir W grateful...
$$\:\:\:{excellent}\:{sir}\:{W}\: \\ $$$$\:\:{grateful}… \\ $$
Answered by hmrsh last updated on 18/Jan/22
First of all, I would like to review a basic combinatorial identity. • ((n),(k) ) = ((( n)),((n−k)) ) Well, It′s interesting to point out that the question is relevant to a famous combinatorial identity, that′s called “Vandermonde′s Identity”. ∗Σ_(k=0) ^r ((m),(( k)) ) ((( n)),((r−k)) ) = (((m+n)),(( r)) ) If we replace n with r and m, we have: •Σ_(k=0) ^n ((n),(k) ) ((( n)),((n−k)) ) = Σ_(k=0) ^n ((n),(k) )^2 = (((2n)),(( n)) ) Now let′s prove the Vandermonde′s identity with combinatorial reasons. Note that it′s easier to use combinatorial reason than to use induction or expand the equation. Just enough to use your creativity and make a counting problem that both LHS and RHS of the identity applied that problem. Like this for prove ∗ : “We want to form a r-member team from m men and n women. In how many ways we can make that team?” Note that the RHS of ∗ is directly the answer. How about the LHS? You can count the ways with moderate the number of men. e.g no men is in team, just 1 man is in team and so on. Summarize the different states with sigma. Now your Question: Σ_(r=0) ^(k−1) ((k),(r) ) ((( k)),((r+1)) ) = Σ_(r=0) ^(k−1) ((k),(r) ) ((( k)),(((k−1)−r)) ) = ((( 2k)),((k−1)) ) Of course you can prove your equation without using the Vandermonde′s identity. Just use the proof which we say in terms that solves your problem.
$$ \\ $$$$ \\ $$$$\mathrm{First}\:\mathrm{of}\:\mathrm{all},\:\mathrm{I}\:\mathrm{would}\:\mathrm{like}\:\mathrm{to}\:\mathrm{review} \\ $$$$\mathrm{a}\:\mathrm{basic}\:\mathrm{combinatorial}\:\mathrm{identity}. \\ $$$$\bullet\:\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}\:=\:\begin{pmatrix}{\:\:\:\:{n}}\\{{n}−{k}}\end{pmatrix} \\ $$$$ \\ $$$$\mathrm{Well},\:\mathrm{It}'\mathrm{s}\:\mathrm{interesting}\:\mathrm{to}\:\mathrm{point}\:\mathrm{out} \\ $$$$\mathrm{that}\:\mathrm{the}\:\mathrm{question}\:\mathrm{is}\:\mathrm{relevant}\:\mathrm{to}\:\mathrm{a}\: \\ $$$$\mathrm{famous}\:\mathrm{combinatorial}\:\mathrm{identity},\:\mathrm{that}'\mathrm{s} \\ $$$$\mathrm{called}\:“\mathrm{Vandermonde}'\mathrm{s}\:\mathrm{Identity}''. \\ $$$$ \\ $$$$\ast\underset{{k}=\mathrm{0}} {\overset{{r}} {\sum}}\begin{pmatrix}{{m}}\\{\:{k}}\end{pmatrix}\begin{pmatrix}{\:\:\:{n}}\\{{r}−{k}}\end{pmatrix}\:=\:\begin{pmatrix}{{m}+{n}}\\{\:\:\:\:\:{r}}\end{pmatrix} \\ $$$$ \\ $$$$\mathrm{If}\:\mathrm{we}\:\mathrm{replace}\:\boldsymbol{{n}}\:\mathrm{with}\:\boldsymbol{{r}}\:\mathrm{and}\:\boldsymbol{{m}},\:\mathrm{we}\:\mathrm{have}: \\ $$$$ \\ $$$$\bullet\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}\begin{pmatrix}{\:\:\:{n}}\\{{n}−{k}}\end{pmatrix}\:=\:\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}^{\mathrm{2}} =\begin{pmatrix}{\mathrm{2}{n}}\\{\:{n}}\end{pmatrix} \\ $$$$ \\ $$$$\mathrm{Now}\:\mathrm{let}'\mathrm{s}\:\mathrm{prove}\:\mathrm{the}\:\mathrm{Vandermonde}'\mathrm{s} \\ $$$$\mathrm{identity}\:\mathrm{with}\:\mathrm{combinatorial}\:\mathrm{reasons}. \\ $$$$ \\ $$$$\mathrm{Note}\:\mathrm{that}\:\mathrm{it}'\mathrm{s}\:\mathrm{easier}\:\mathrm{to}\:\mathrm{use}\:\mathrm{combinatorial} \\ $$$$\mathrm{reason}\:\mathrm{than}\:\mathrm{to}\:\mathrm{use}\:\mathrm{induction}\:\mathrm{or}\:\mathrm{expand} \\ $$$$\mathrm{the}\:\mathrm{equation}. \\ $$$$ \\ $$$$\mathrm{Just}\:\mathrm{enough}\:\mathrm{to}\:\mathrm{use}\:\mathrm{your}\:\mathrm{creativity} \\ $$$$\mathrm{and}\:\mathrm{make}\:\mathrm{a}\:\mathrm{counting}\:\mathrm{problem}\:\mathrm{that} \\ $$$$\mathrm{both}\:\mathrm{LHS}\:\mathrm{and}\:\mathrm{RHS}\:\mathrm{of}\:\mathrm{the}\:\mathrm{identity} \\ $$$$\mathrm{applied}\:\mathrm{that}\:\mathrm{problem}. \\ $$$$ \\ $$$$\mathrm{Like}\:\mathrm{this}\:\mathrm{for}\:\mathrm{prove}\:\ast\:: \\ $$$$“\mathrm{We}\:\mathrm{want}\:\mathrm{to}\:\mathrm{form}\:\mathrm{a}\:\boldsymbol{{r}}-\mathrm{member}\:\mathrm{team}\: \\ $$$$\mathrm{from}\:\boldsymbol{{m}}\:\mathrm{men}\:\mathrm{and}\:\boldsymbol{{n}}\:\mathrm{women}. \\ $$$$\mathrm{In}\:\mathrm{how}\:\mathrm{many}\:\mathrm{ways}\:\mathrm{we}\:\mathrm{can}\:\mathrm{make}\:\mathrm{that}\:\mathrm{team}?'' \\ $$$$ \\ $$$$\mathrm{Note}\:\mathrm{that}\:\mathrm{the}\:\mathrm{RHS}\:\mathrm{of}\:\ast\:\mathrm{is}\:\mathrm{directly} \\ $$$$\mathrm{the}\:\mathrm{answer}. \\ $$$$\mathrm{How}\:\mathrm{about}\:\mathrm{the}\:\mathrm{LHS}? \\ $$$$\mathrm{You}\:\mathrm{can}\:\mathrm{count}\:\mathrm{the}\:\mathrm{ways}\:\mathrm{with}\:\mathrm{moderate} \\ $$$$\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{men}. \\ $$$$\mathrm{e}.\mathrm{g}\:\:\:\mathrm{no}\:\mathrm{men}\:\mathrm{is}\:\mathrm{in}\:\mathrm{team},\:\mathrm{just}\:\mathrm{1}\:\mathrm{man} \\ $$$$\mathrm{is}\:\mathrm{in}\:\mathrm{team}\:\mathrm{and}\:\mathrm{so}\:\mathrm{on}. \\ $$$$\mathrm{Summarize}\:\mathrm{the}\:\mathrm{different}\:\mathrm{states} \\ $$$$\mathrm{with}\:\mathrm{sigma}. \\ $$$$ \\ $$$$\mathrm{Now}\:\mathrm{your}\:\mathrm{Question}: \\ $$$$\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\begin{pmatrix}{{k}}\\{{r}}\end{pmatrix}\begin{pmatrix}{\:\:\:{k}}\\{{r}+\mathrm{1}}\end{pmatrix}\:=\:\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\begin{pmatrix}{{k}}\\{{r}}\end{pmatrix}\begin{pmatrix}{\:\:\:\:\:\:\:\:\:{k}}\\{\left({k}−\mathrm{1}\right)−{r}}\end{pmatrix}\:=\:\begin{pmatrix}{\:\:\mathrm{2}{k}}\\{{k}−\mathrm{1}}\end{pmatrix} \\ $$$$ \\ $$$$\mathrm{Of}\:\mathrm{course}\:\mathrm{you}\:\mathrm{can}\:\mathrm{prove}\:\mathrm{your}\:\mathrm{equation} \\ $$$$\mathrm{without}\:\mathrm{using}\:\mathrm{the}\:\mathrm{Vandermonde}'\mathrm{s} \\ $$$$\mathrm{identity}.\:\mathrm{Just}\:\mathrm{use}\:\mathrm{the}\:\mathrm{proof}\:\mathrm{which} \\ $$$$\mathrm{we}\:\mathrm{say}\:\mathrm{in}\:\mathrm{terms}\:\mathrm{that}\:\mathrm{solves}\:\mathrm{your}\:\mathrm{problem}. \\ $$
Commented by mnjuly1970 last updated on 19/Jan/22
thanks alot sir
$${thanks}\:{alot}\:{sir} \\ $$
Commented by Rasheed.Sindhi last updated on 19/Jan/22
With good explanation!
$$\mathcal{W}{ith}\:{good}\:{explanation}! \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *