msleziak.com

Zistite čomu sa rovná $\sum\limits_{j=0}^n \sum\limits_{i=j}^n \binom ni \binom ij$ (a nájdite nejaké zdôvodnenie).

Správny výsledok je, že táto suma sa rovná $3^n$.

Môžeme aj vyskúšať pre malé $n$ vypočítať hodnotu tejto sumy. Ak si označíme $S_n=\sum\limits_{j=0}^n \sum\limits_{i=j}^n \binom ni \binom ij$, tak dostaneme:
\begin{align*}
S_0&=1\\
S_1&=3\\
S_2&=9\\
S_3&=27\\
S_4&=81\\
S_5&=243
\end{align*}
Minimálne pre $n=0,1,2$ je suma ešte pomerne komfortne spočítateľná aj manuálne. Ak by sme zašli až po $n=4$ alebo aspoň po $n=3$, tak $S_n=3^n$ vyzerá už ako pomerne zmysluplný tip.
Zmena poradia sčitovania.
Asi pomerne priamočiare riešenie dostaneme ak vymeníme poradie súm. \begin{align*}
\sum_{j=0}^n \sum_{i=j}^n \binom ni \binom ij
&=\sum_{i=0}^n \sum_{j=0}^i \binom ni \binom ij\\
&=\sum_{i=0}^n \binom ni \sum_{j=0}^i \binom ij\\
&=\sum_{i=0}^n \binom ni 2^i = 3^n
\end{align*}

Ak to náhodou niekomu pomôže, aby boli vyššie uvedené úpravy jasnejšie, tu je to isté pre prípad $n=5$, pričom farebne sú vyznačené tie členy, ktoré dajú súčet $\binom ni2^i$ pre $i=0,1,\dots,3$. (A snáď sa dá vidieť podobný pattern aj pre ostatné $n$, pre ktoré som súčet $S_n$ rozpísal vyššie.) Ešte inak prepísaná suma:
Súčin vystupujúci v sume môžeme prepísať ako
$$\binom ni \binom ij = \binom nj \binom{n-j}{i-j}.$$
Využívame tu indentitu, na ktorú sme už párkrát narazili: viewtopic.php?t=987
Ak sme ho prepísali takýmto spôsobom, tak našu sumu môžeme upraviť ako:
\begin{align*}
\sum_{j=0}^n \sum_{i=j}^n \binom ni \binom ij
&=\sum_{i=0}^n \sum_{j=0}^i \binom nj \binom{n-j}{i-j}\\
&=\sum_{j=0}^n \sum_{i=j}^n \binom nj \binom{n-j}{i-j}\\
&=\sum_{j=0}^n \binom nj \sum_{i=j}^n \binom{n-j}{i-j}\\
&=\sum_{j=0}^n \binom nj \sum_{k=0}^{n-j} \binom{n-j}k\\
&=\sum_{j=0}^n \binom nj 2^{n-j} = 3^n
\end{align*}

Kombinatoricky.
Môžeme skúsiť vymyslieť niečo také, aby sme ukázali, že ľavá aj pravá strana rovnosti
$$\sum\limits_{j=0}^n \sum\limits_{i=j}^n \binom ni \binom ij=3^n$$
vyjadruje počet prvkov tej istej množiny. (Asi na takéto riešenie je ľahšie prísť ak sa nám nejako - napríklad skúšaním malých hodnôt - už podarilo prísť na to, že výsledok má byť $3^n$.)

Zoberme si nejakú $n$-prvkovú množinu, napríklad $X=\{1,2,\ldots,n\}$.

Pre ľavú stranu máme pomerne prirodzenú interpretáciu cez podmnožiny. Pre pravú stranu máme pomerne prirodzenú interpretáciu cez funkcie. Vieme tieto dve interpretácie nejako dať navzájom do súvisu? Kombinatorický prístup bol pekne vysvetlený v jednom z odovzdaných riešení cez počítanie komisíí - skopírujem sem aj takýto postup. (Skryl som ho - ak o tom náhodou najprv chcete porozmýšľať samostatne.)

Kde sa dá pozrieť na riešenie

Nejaké náhodne pozbierané linky.

• How to prove the double sum of combinations is $3^n$
• How does this summation work and what does it evaluate to?
• Find $\sum_{j=0}^{n}\sum_{i=j}^{n} {n \choose i}{i \choose j}$.

Je to príklad 5.1.2 v Loren C. Larson : Problem-Solving Through Problems. (Existuje slovenský preklad pod názvom Metódy riešenia matematických problémov.)

Komentáre k odovzdaným riešeniam

Vyskytli sa nejaké riešenia, kde ste poèítali, ako keby druhý èinite¾ $\binom ij$ bol rovný jednej. Takto by ste dostali inú sumu:
\begin{align*}
\sum_{j=0}^n \sum_{i=j}^n \binom ni
&=\sum_{i=0}^n \sum_{j=0}^i \binom ni\\
&=\sum_{i=0}^n (i+1) \binom ni\\
&\overset{(*)}=n2^{n-1}+2^n=(n+2)2^{n-1}
\end{align*}
V rovnosti $(*)$ sme využili to, že sumu $\sum\limits_{i=0}^n i \binom ni=n2^{n-1}$ sme už kedysi odvodili: viewtopic.php?t=1003