6. Zadatak

Prvo rješenje.

Primjenom binomnog teorema na izraze $(2+1)^{2022}$ i $(-2+1)^{2022}$ dobivamo

$$3^{2022}=(2+1)^{2022}=\sum_{k=0}^{2022}\binom{2022}{k}2^k\cdot1^{2022-k}=\sum_{k=0}^{2022}\binom{2022}{k}2^k,$$

te

$$1=(-1)^{2022}=(-2+1)^{2022}=\sum_{k=0}^{2022}\binom{2022}{k}(-2)^k\cdot1^{2022-k}=\sum_{k=0}^{2022}\binom{2022}{k}(-2)^k.$$

Oduzimanjem gornjih dviju jednakosti dobivamo

$$3^{2022}-1=\sum_{k=0}^{2022}\binom{2022}{k}\bigl(2^k-(-2)^k\bigr)=2\sum_{k=1}^{1011}\binom{2022}{2k-1}2^{2k-1}.$$

Dijeljenjem gornje jednakosti s $2$ dobivamo traženi rezultat:

$$\sum_{k=1}^{1011}\binom{2022}{2k-1}2^{2k-1}=\frac{3^{2022}-1}{2}.$$

Drugo rješenje.

Zadatak rješavamo koristeći kombinatornu interpretaciju.

Binomni koeficijent $\binom{2022}{2k-1}$ je broj načina da od skupa s $2022$ elemenata odaberemo podskup s $2k-1$ elemenata.

Broj $2^{2k-1}$ možemo interpretirati kao broj podskupova skupa s $2k-1$ elemenata.

Stoga je zadani zbroj jednak broju načina da odaberemo: broj $k$ između $1$ i $1011$, podskup $B$ skupa $S=\{1,2,\ldots,2022\}$ s $2k-1$ elemenata i podskup $A$ skupa $B$.

Dakle, biramo parove $(A,B)$ pri čemu je $A\subseteq B\subseteq S$ i $B$ ima neparno mnogo elemenata.

Broj parova $(A,B)$ pri čemu je $A\subseteq B\subseteq S$ (bez uvjeta da $B$ ima neparno mnogo elemenata) je jednak $3^{2022}$ jer je svaki takav par jednoznačno određen razmještanjem svakog elementa skupa $S$ u jedan od disjunktnih skupova $A$, $B\setminus A$ i $S\setminus B$.

Pokažimo da sve parove osim $(A,B)=(S,S)$ možemo povezati tako da su parovi $(A,B')$ i $(A,B'')$ povezani ako i samo ako postoji točan jedan element koji se pojavljuje u jednom od skupova $B'$ i $B''$, a ne pojavljuje se u drugom. Na taj način će biti povezani jedan par koji ima neparno elemenata u skupu $B$ s jednim parom u kojem $B$ ima parno elemenata. Dakle, traženih parova ima $\frac12(3^{2022}-1)$.

Zaista, za svaki par $(A,B)$ neka je $k$ najveći element skupa $S$ koji se ne nalazi u $A$. Ako je $k\in B$, onda povežemo $(A,B)$ i $(A,B\setminus\{k\})$, a ako vrijedi $k\notin B$, onda povežemo $(A,B)$ i $(A,B\cup\{k\})$. Drugim riječima, između skupova $B\setminus A$ i $S\setminus B$ prebacujemo najveći element $k$ koji se u njima nalazi. Na taj način možemo upariti sve parove, osim $(A,B)=(S,S)$ jer jedino u tom slučaju nema elemenata u $S$ koji se ne nalaze u $A$.