Viackrát som v súvislosti s písomkou spomenul, že mnohé identity sa dajú odvodiť veľa spôsobmi - a na niektorých príkladoch sme to aj videli. (Napríklad sme používali kombinatorické úvahy, úpravy sčítancov, prechádzky po mriežke, binomická veta. Dá sa použiť aj indukcia - hoci pri niektorých identitách môže byť dôkaz indukciou vcelku komplikovaný.) Chcel by som ukázať dôkaz nejakej identity aspoň dvoma spôsobmi a aby tam bola ako jeden zo spôsobov indukcia. (Skôr to má slúžiť ako odstrašujúci príklad, že komplikovanejších identitách nie je indukcia zvyčajne ten najjednoduchší spôsob. Aj keď neviem, či som vybral dostatočne odstrašujúci.)
Samozrejme, ak sa budete na fóre pýtať vy na nejaké príklady, ktoré ste riešili a nedarilo sa vám, tak sa bude snažiť radšej odpovedať na tie, než aby som pridával k tejto úlohe nejaké ďalšie riešenia. (Nižšie som pridal aj linky na nejaké riešenia, ktoré sa dajú nájsť na internete.)
Skúsime sa pozrieť na identitu, ktorú sme odvodili na cviku pomocou mriežok. (Toto som robil na cvičeniach s oboma skupinami. Je to úloha 7 z 07cvicenie_cesty.pdf.)
$$\sum_{k=0}^{n-m} \binom{s+k}{k} \binom{n-k}{m} = \binom{s+n+1}{s+m+1}\tag{1}$$
Podobne ako keď sme to robili na cviku pomocou mriežok, oplatí sa uvedomiť si, že pre $m>n$ je to rovnosť $0=0$ a už zostáva riešiť len prípad $n\ge m$.
Vďaka symetrii Pascalovho trojuholníka môžeme tú istú sumu prepísať aj ako.
$$\sum_{k=0}^{n-m} \binom{s+k}{s} \binom{n-k}{m} = \binom{s+n+1}{s+m+1}\tag{2}$$
Môžeme si ju prepísať aj po jednotlivých členoch, ak nám to pomôže lepšie vidieť do toho, čo robíme:
$$\binom{s}{s}\binom{n}m+\binom{s+1}{s}\binom{n-1}m+\dots+\binom{s+n-m-1}{s}\binom{m-1}m+\binom{s+n-m}{s}\binom{m}m$$
Čiže si môžeme všimnúť že horné "indexy" majú v každom sčítanci rovnaký súčet, konkrétne $s+n$, dolné indexy zostávajú rovnaké.
Azda sa oplatí všimnúť aj to, že pre $s=0$ dostaneme $\binom{s+k}s=\binom k0 =1$ a suma (2) má tvar
$$\sum_{k=0}^{n-m} \binom{n-k}{m} = \binom{n+1}{m+1}$$
čo môžeme ekvivalentne prepísať ak ako
$$\sum_{j=m}^n \binom jm = \binom{n+1}{m+1}.$$
Toto je identita, pre ktorú sme videli nejaké dôkazy na prednáške - hokejková identita.
Ak sme si všimli toto, tak možno je šanca, že nejaké podobné metódy ako pri odvodení tejto identity by mohli zabrať aj tu.
Nejaké linky, kde sa dá pozrieť riešenie tejto (alebo veľmi podobnej identity):
Suma z cvičení $\sum\limits_{k=0}^{n-m} \binom{s+k}{k} \binom{n-k}{m} = \binom{s+n+1}{s+m+1}$
-
Martin Sleziak
- Posts: 5517
- Joined: Mon Jan 02, 2012 5:25 pm
-
Martin Sleziak
- Posts: 5517
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Suma z cvičení $\sum\limits_{k=0}^{n-m} \binom{s+k}{k} \binom{n-k}{m} = \binom{s+n+1}{s+m+1}$
Skúsme najprv kombinatorické riešenie.
Riešenie.
Pravá strana očividne počíta podmnožiny množiny $\{1,2,\dots,s+n+1\}$, ktoré majú $s+m+1$ prvkov. Chceli by sme ich nejako rozdeliť tak, aby nám vyšla ľavá suma.
Čiže máme podmnožiny, ktoré obsahujú nejaké prvky $$1\le x_1<x_2<\dots<x_s<x_{s+1}<x_{s+2}<\dots<x_{s+m+1}\le s+n+1.$$
Skúsme sa pozrieť na to, ako to vyzerá v závislosti od hodnoty prvku $x_{s+1}$. Inak povedané, ak si zvolíme $(s+1)$-vý najmenší prvok vo vybratej množine, koľko máme potom možností výberu.
Je jasné, že $(s+1)$-vý najmenší prvok musí mať hodnotu aspoň $s+1$ (aby sme do našej množiny zmestili aspoň $s$ menších prvkov). Súčasne tam musíme dať ešte $m$ prvkov, ktoré sú od neho väčšie (konkrétne $x_{s+2},\dots,x_{s+m+1}$), aby sme ich tam mali šancu zmestiť, tak $x_{s+1}$ môže byť najviac $(s+n+1)-m=s+1+(n-m)$.
Teda vidíme, že $x_{s+1}$ môže nadobúdať hodnoty
$$x_{s+1}=s+1+k \qquad\text{pre}\qquad k=0,1,\dots,n-m.$$
Koľko máme možností pre danú hodnotu $k$? Vlastne potrebujeme vybrať $s$ prvkov, ktoré sú pred $x_{s+1}$. Vyberáme is z množiny $\{1,2,\dots,s+k\}$, pretože majú byť menšie ako $s+k+1$. Teda máme $\binom{s+k}s$ možností. Ďalej potrebujeme vybrať prvky, ktoré sú väčšie ako $x_{s+1}=s+k+1$. Pretože majú byť väčšie ako toto číslo, tak ich vlastne vyberáme z množiny $\{s+k+2,\dots,s+n+1\}$, ktorá má $(n-k)$ prvkov. A potrebujeme vybrať prvky $x_{s+2},\dots,x_{s+m+1}$, ktorých je $(s+m+1)-(s+1)=m$. Teda máme $\binom{n-k}{m}$ možností.
Celkove teda pre každé zvolené $k$ máme
$$\binom{s+k}s\binom{n-k}m$$
možností. Stačí nám už ich iba sčítať cez všetky prípustné hodnoty $k$. Dostaneme
$$\sum_{k=0}^{n-m} \binom{s+k}s\binom{n-k}m.$$
Zistili sme, že ľavá a pravá strana rovnosti (2) predstavujú počet prvkov tej istej množiny, takže sa musia rovnať. $\square$
Riešenie.
Pravá strana očividne počíta podmnožiny množiny $\{1,2,\dots,s+n+1\}$, ktoré majú $s+m+1$ prvkov. Chceli by sme ich nejako rozdeliť tak, aby nám vyšla ľavá suma.
Čiže máme podmnožiny, ktoré obsahujú nejaké prvky $$1\le x_1<x_2<\dots<x_s<x_{s+1}<x_{s+2}<\dots<x_{s+m+1}\le s+n+1.$$
Skúsme sa pozrieť na to, ako to vyzerá v závislosti od hodnoty prvku $x_{s+1}$. Inak povedané, ak si zvolíme $(s+1)$-vý najmenší prvok vo vybratej množine, koľko máme potom možností výberu.
Je jasné, že $(s+1)$-vý najmenší prvok musí mať hodnotu aspoň $s+1$ (aby sme do našej množiny zmestili aspoň $s$ menších prvkov). Súčasne tam musíme dať ešte $m$ prvkov, ktoré sú od neho väčšie (konkrétne $x_{s+2},\dots,x_{s+m+1}$), aby sme ich tam mali šancu zmestiť, tak $x_{s+1}$ môže byť najviac $(s+n+1)-m=s+1+(n-m)$.
Teda vidíme, že $x_{s+1}$ môže nadobúdať hodnoty
$$x_{s+1}=s+1+k \qquad\text{pre}\qquad k=0,1,\dots,n-m.$$
Koľko máme možností pre danú hodnotu $k$? Vlastne potrebujeme vybrať $s$ prvkov, ktoré sú pred $x_{s+1}$. Vyberáme is z množiny $\{1,2,\dots,s+k\}$, pretože majú byť menšie ako $s+k+1$. Teda máme $\binom{s+k}s$ možností. Ďalej potrebujeme vybrať prvky, ktoré sú väčšie ako $x_{s+1}=s+k+1$. Pretože majú byť väčšie ako toto číslo, tak ich vlastne vyberáme z množiny $\{s+k+2,\dots,s+n+1\}$, ktorá má $(n-k)$ prvkov. A potrebujeme vybrať prvky $x_{s+2},\dots,x_{s+m+1}$, ktorých je $(s+m+1)-(s+1)=m$. Teda máme $\binom{n-k}{m}$ možností.
Celkove teda pre každé zvolené $k$ máme
$$\binom{s+k}s\binom{n-k}m$$
možností. Stačí nám už ich iba sčítať cez všetky prípustné hodnoty $k$. Dostaneme
$$\sum_{k=0}^{n-m} \binom{s+k}s\binom{n-k}m.$$
Zistili sme, že ľavá a pravá strana rovnosti (2) predstavujú počet prvkov tej istej množiny, takže sa musia rovnať. $\square$
-
Martin Sleziak
- Posts: 5517
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Suma z cvičení $\sum\limits_{k=0}^{n-m} \binom{s+k}{k} \binom{n-k}{m} = \binom{s+n+1}{s+m+1}$
Pozrime sa na riešenie indukciou.
V podstate vždy, ak robíte dôkaz indukciou a máte tam viac premenných, treba sa zamyslieť nad tým, vzhľadom na ktorú premennú budem robiť indukciu. A niekedy sa môže stať to, že treba robiť indukciu na viac premenných. (Napríklad dokazujeme niečo, čo obsahuje premenné $i$, $j$ a potrebujeme predpokladať, že to platí pre všetky menšie hodnoty obochpremenných. Alebo sa môže stať, že robíme dôkaz indukciou na $i$, ale v indukčnom kroku zistíme, že tam musím dokázať nejaké pomocné tvrdenie, ktoré budem robiť indukciou vzhľadom na $j$.)
Riešenie
Chceme teda dokazovať rovnosť:
$$\sum_{k=0}^{n-m} \binom{s+k}{k} \binom{n-k}{m} = \binom{s+n+1}{s+m+1}\tag{1}$$
Budem sa snažiť dokázať indukciou na $n$, že toto tvrdenie platí pre ľubovoľné $m$, $s$. (Môžete si vyskúšať, či sa vám podarí urobiť dôkaz, ak by ste robili indukciu na $s$ alebo indukciu na $m$. A ak sa vám ho podarí urobiť, či sa tým dôkaz zjednodušil alebo skomplikoval. A poznamenám, že možnosti výberu premennej na indukciu je veľa. Napríklad by sme mohli označiť $l=m+n$, prepísať identitu po tejto substitúcii a pozrieť sa na to, ako indukcia bude fungovať ak by sme ju robili vzhľadom na $l$.)
Pripomeniem, že sme si už uvedomili, že tvrdenie platí pre $m>n$.
Možno sa oplatí samostatne si rozmyslieť aj prípad $m=0$; ak to skúsite, mali by ste vidieť, že dostanete hokejkovú identitu. (Hlavne kvôli tomu, že v indukčnom kroku nám vyjde $(m-1)$. Ak budeme mať rovnosť už dokázanú pre $m=0$.)
$1^\circ$ Báza indukcie. Ak dosadíme $m=0$ tak máme
$$\sum_{k=0}^{n} \binom{s+k}{k} = \binom{s+n+1}{s+1},$$
čo je opäť hokejková identita.
$2^\circ$ Indukčný krok. Predpokladajme, že (1) platí pre $n$ a chceme sa pozrieť na to, čo sa stane pre $n+1$. Skúsme upravovať:
\begin{align*}
\sum_{k=0}^{n+1-m} \binom{s+k}{k} \binom{n+1-k}{m}
&= \sum_{k=0}^{n+1-m} \binom{s+k}{k} \left[\binom{n-k}{m}+\binom{n-k}{m-1}\right] \\
&= \sum_{k=0}^{n+1-m} \binom{s+k}{k} \binom{n-k}{m}+\sum_{k=0}^{n+1-m} \binom{s+k}{k} \binom{n-k}{m-1} \\
&= \sum_{k=0}^{n-m} \binom{s+k}{k} \binom{n-k}{m}+\sum_{k=0}^{n-(m-!)} \binom{s+k}{k} \binom{n-k}{m-1} \\
&\overset{IP}= \binom{s+n+1}{s+m+1} + \binom{s+n+1}{s+m} = \binom{s+n+2}{s+m+1}
\end{align*}
V podstate vždy, ak robíte dôkaz indukciou a máte tam viac premenných, treba sa zamyslieť nad tým, vzhľadom na ktorú premennú budem robiť indukciu. A niekedy sa môže stať to, že treba robiť indukciu na viac premenných. (Napríklad dokazujeme niečo, čo obsahuje premenné $i$, $j$ a potrebujeme predpokladať, že to platí pre všetky menšie hodnoty obochpremenných. Alebo sa môže stať, že robíme dôkaz indukciou na $i$, ale v indukčnom kroku zistíme, že tam musím dokázať nejaké pomocné tvrdenie, ktoré budem robiť indukciou vzhľadom na $j$.)
Riešenie
Chceme teda dokazovať rovnosť:
$$\sum_{k=0}^{n-m} \binom{s+k}{k} \binom{n-k}{m} = \binom{s+n+1}{s+m+1}\tag{1}$$
Budem sa snažiť dokázať indukciou na $n$, že toto tvrdenie platí pre ľubovoľné $m$, $s$. (Môžete si vyskúšať, či sa vám podarí urobiť dôkaz, ak by ste robili indukciu na $s$ alebo indukciu na $m$. A ak sa vám ho podarí urobiť, či sa tým dôkaz zjednodušil alebo skomplikoval. A poznamenám, že možnosti výberu premennej na indukciu je veľa. Napríklad by sme mohli označiť $l=m+n$, prepísať identitu po tejto substitúcii a pozrieť sa na to, ako indukcia bude fungovať ak by sme ju robili vzhľadom na $l$.)
Pripomeniem, že sme si už uvedomili, že tvrdenie platí pre $m>n$.
Možno sa oplatí samostatne si rozmyslieť aj prípad $m=0$; ak to skúsite, mali by ste vidieť, že dostanete hokejkovú identitu. (Hlavne kvôli tomu, že v indukčnom kroku nám vyjde $(m-1)$. Ak budeme mať rovnosť už dokázanú pre $m=0$.)
$1^\circ$ Báza indukcie. Ak dosadíme $m=0$ tak máme
$$\sum_{k=0}^{n} \binom{s+k}{k} = \binom{s+n+1}{s+1},$$
čo je opäť hokejková identita.
$2^\circ$ Indukčný krok. Predpokladajme, že (1) platí pre $n$ a chceme sa pozrieť na to, čo sa stane pre $n+1$. Skúsme upravovať:
\begin{align*}
\sum_{k=0}^{n+1-m} \binom{s+k}{k} \binom{n+1-k}{m}
&= \sum_{k=0}^{n+1-m} \binom{s+k}{k} \left[\binom{n-k}{m}+\binom{n-k}{m-1}\right] \\
&= \sum_{k=0}^{n+1-m} \binom{s+k}{k} \binom{n-k}{m}+\sum_{k=0}^{n+1-m} \binom{s+k}{k} \binom{n-k}{m-1} \\
&= \sum_{k=0}^{n-m} \binom{s+k}{k} \binom{n-k}{m}+\sum_{k=0}^{n-(m-!)} \binom{s+k}{k} \binom{n-k}{m-1} \\
&\overset{IP}= \binom{s+n+1}{s+m+1} + \binom{s+n+1}{s+m} = \binom{s+n+2}{s+m+1}
\end{align*}