Задача Brainstorming Комбинаторика

[dextur33]

Докажете,че : Комбинация на r елементи от клас r + Комбинация на (r+1) елементи от клас n + .....+ комбинация от n елементи от клас r = комбинация на (n+1) елементи от клас (r+1).

Съжалявам, че е написано с думи, но не можаш да намеря правилната функция.

Благодаря предварително !!!

[Martin Nikovski]

Докажете, че [tex]C_r^r+C_{r+1}^n+...+C_n^r=C_{n+1}^{r+1}[/tex]
Сигурен ли си, че условието е така?
За да съществува [tex]C_{r+1}^n[/tex], е необходимо [tex]r+1>n[/tex].
За да съществува [tex]C_{n}^r[/tex], е необходимо [tex]n>r[/tex].
Тогава [tex]r+1>n>r[/tex], т.е. [tex]n\in \left(r;r+1\right)[/tex]
[tex]r[/tex] и [tex]r+1[/tex] са две последователни естествени числа, тогава [tex]n[/tex] не е естествено??

[dextur33]

Докажете, че [tex]C_r^r+C_{r+1}^n+...+C_n^r=C_{n+1}^{r+1}[/tex]
Сигурен ли си, че условието е така?
За да съществува [tex]C_{r+1}^n[/tex], е необходимо [tex]r+1>n[/tex].
За да съществува [tex]C_{n}^r[/tex], е необходимо [tex]n>r[/tex].
Тогава [tex]r+1>n>r[/tex], т.е. [tex]n\in \left(r;r+1\right)[/tex]
[tex]r[/tex] и [tex]r+1[/tex] са две последователни естествени числа, тогава [tex]n[/tex] не е естествено??

Съжалявам, грешката е моя. Правилното условие е [tex]C_r^r+C_{r+1}^r+...+C_n^r=C_{n+1}^{r+1}[/tex]

Упътването на задачата гласи : Използвайте,че [tex]C_n^k+C_n^{k+1}=C_{n+1}^{k+1}[/tex] и докажете равенството с индукция по n

[Martin Nikovski]

ОК... така е по-добре...
Докажете, че [tex]C_r^r+C_{r+1}^r+...+C_n^r=C_{n+1}^{r+1}[/tex].
Използваме метода на математическата индукция (по [tex]n[/tex])...

1. Доказваме, че равенството е изпълнено за най-малкото възможно [tex]n[/tex].
За да съществува [tex]C_n^r[/tex], е необходимо [tex]n\ge r[/tex]. Тогава най-малкото възможно [tex]n[/tex] е [tex]n=r[/tex].
При [tex]n=r[/tex]: [tex]C_r^r\stackrel{?}{=}C_{r+1}^{r+1}[/tex].
[tex]C_r^r=C_{r+1}^{r+1}=1[/tex] (изпълнено)! - комбинация на [tex]k[/tex] елементи от клас [tex]k[/tex] е равна на [tex]1[/tex].

2. Допускаме, че за [tex]n=k[/tex] равенството е изпълнено.
[tex]C_r^r+C_{r+1}^r+...+C_k^r=C_{k+1}^{r+1}[/tex]

3. Доказваме, че за [tex]n=k+1[/tex] равенството е изпълнено.
[tex]C_r^r+C_{r+1}^r+...+C_{k+1}^r \stackrel{?}{=}C_{k+1+1}^{r+1}[/tex]
[tex]C_r^r+C_{r+1}^r+...+C_{k+1}^r \stackrel{?}{=}C_{k+2}^{r+1}[/tex]
В редицата отляво записваме и предпоследния член...
[tex]C_r^r+C_{r+1}^r+...+C_{k}^r+C_{k+1}^r \stackrel{?}{=}C_{k+2}^{r+1}[/tex]
От стъпка 2. (допуснатото твърдение) имаме, че [tex]C_r^r+C_{r+1}^r+...+C_k^r=C_{k+1}^{r+1}[/tex]
Лявата страна на това равенство присъства и в лявата страна на равенството, което искаме да докажем (в червено).
[tex]\red{C_r^r+C_{r+1}^r+...+C_{k}^r}[/tex][tex]+C_{k+1}^r \stackrel{?}{=}C_{k+2}^{r+1}[/tex]
Заместваме [tex]C_r^r+C_{r+1}^r+...+C_k^r[/tex] с [tex]C_{k+1}^{r+1}[/tex] и получаваме:
[tex]C_{k+1}^{r+1}+C_{k+1}^r \stackrel{?}{=}C_{k+2}^{r+1}[/tex] или записано по малко по-различен начин:
[tex]C_{k+1}^r+C_{k+1}^{r+1} \stackrel{?}{=}C_{k+2}^{r+1}[/tex]
Това равенство е всъщност даденото в указанието: [tex]C_n^k+C_n^{k+1}=C_{n+1}^{k+1}[/tex],
като в равенството, което искаме да докажем [tex]n=k+1[/tex] и [tex]k=r[/tex].
Равенството 3. е изпълнено, следователно [tex]C_r^r+C_{r+1}^r+...+C_n^r=C_{n+1}^{r+1}[/tex] за всяко [tex]n\ge r[/tex].