matematikk.net

Definer [tex]S(A)[/tex] som summen av elementene i [tex]A[/tex], der [tex]A\subseteq \mathbb{N}[/tex] er en endelig undermengde av de naturlige tallene. La [tex]P(n)[/tex] være mengden av alle undermengdene til [tex]\{1,2,...,n\}\subseteq\mathbb{N}[/tex].

Definér så [tex]\Sigma(n)=\sum_{A\in P(n)} S(A)[/tex].

Finn et lukket uttrykk for [tex]\Sigma(n)[/tex].

Hvert element opptrer [tex]n-1\choose j[/tex] ganger i undermengder av kardinalitet j+1
Altså totalt [tex]\sum_{j=0}^{n-1}{n-1\choose j}=2^{n-1}[/tex] ganger. Da blir

[tex]\Sigma(n)=\sum_{i=1}^n i2^{n-1}=2^{n-2}n(n+1)[/tex]

Selvfølgelig riktig.