Správny výsledok je, že táto suma sa rovná $3^n$.Zistite čomu sa rovná $\sum\limits_{j=0}^n \sum\limits_{i=j}^n \binom ni \binom ij$ (a nájdite nejaké zdôvodnenie).
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.
Spoiler:
Asi pomerne priamočiare riešenie dostaneme ak vymeníme poradie súm.
Spoiler:
\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.)
Spoiler:
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.
Spoiler:
Spoiler:
Spoiler:
Spoiler: