Menu Close

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




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}! \\ $$

Leave a Reply

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