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

p r o v e t h a t

Extra \left or missing \right

- - - -

Answered by mr W last updated on 19/Jan/22

{(1 + x)}^{2 k} = {(1 + x)}^{k} {(1 + x)}^{k}

\underset{q = 0}{\sum^{2 k}} (\begin{matrix} 2 k \\ q \end{matrix}) x^{q} = [\underset{r = 0}{\sum^{k}} (\begin{matrix} k \\ r \end{matrix}) x^{r}] [\underset{p = 0}{\sum^{k}} (\begin{matrix} k \\ p \end{matrix}) x^{p}]

{l e t}^{'} s s e e t e r m x^{q} w i t h q = k - 1

r + p = k - 1

\Rightarrow p = k - 1 - r ⩾ 0 \Rightarrow r ⩽ k - 1

(\begin{matrix} 2 k \\ k - 1 \end{matrix}) = \underset{r = 0}{\sum^{k - 1}} (\begin{matrix} k \\ r \end{matrix}) (\begin{matrix} k \\ k - r - 1 \end{matrix})

(\begin{matrix} 2 k \\ k - 1 \end{matrix}) = \underset{r = 0}{\sum^{k - 1}} (\begin{matrix} k \\ r \end{matrix}) (\begin{matrix} k \\ r + 1 \end{matrix}) ✓

Commented by mnjuly1970 last updated on 19/Jan/22

e x c e l l e n t s i r W

g r a t e f u l \dots

Answered by hmrsh last updated on 18/Jan/22

First of all, I would like to review

a basic combinatorial identity .

∙ (\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ n - k \end{matrix})

Well, {It}^{'} s interesting to point out

that the question is relevant to a

famous combinatorial identity, {that}^{'} s

called “ {Vandermonde}^{'} s {Identity}^{″} .

* \underset{k = 0}{\sum^{r}} (\begin{matrix} m \\ k \end{matrix}) (\begin{matrix} n \\ r - k \end{matrix}) = (\begin{matrix} m + n \\ r \end{matrix})

If we replace n with r and m, we have :

∙ \underset{k = 0}{\sum^{n}} (\begin{matrix} n \\ k \end{matrix}) (\begin{matrix} n \\ n - k \end{matrix}) = \underset{k = 0}{\sum^{n}} {(\begin{matrix} n \\ k \end{matrix})}^{2} = (\begin{matrix} 2 n \\ n \end{matrix})

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 :

\underset{r = 0}{\sum^{k - 1}} (\begin{matrix} k \\ r \end{matrix}) (\begin{matrix} k \\ r + 1 \end{matrix}) = \underset{r = 0}{\sum^{k - 1}} (\begin{matrix} k \\ r \end{matrix}) (\begin{matrix} k \\ (k - 1) - r \end{matrix}) = (\begin{matrix} 2 k \\ k - 1 \end{matrix})

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 .

Commented by mnjuly1970 last updated on 19/Jan/22

t h a n k s a l o t s i r

Commented by Rasheed.Sindhi last updated on 19/Jan/22

W i t h g o o d e x p l a n a t i o n!