Hogyan számoljuk ki egy halmaz összes részhalmazának elemszámainak összegét, illetve elemeinek összegét?

n alatt a k-t nCk-val fogom jelölni (C, mint Combination, a számológépeken szokás így).

Az összes részhalmazok elemszámainak összege:

nC0*0 + nC1*1 + nC2*2 + … + nC(n-1)*(n-1) + nCN*n.

A binomiális tétel alapján

(1 + x)^n = nC0*1^n*x^0 + nC1*1^(n-1)*x^1 + nC2*1^(n-1)*x^2 + … + nC(n-1)*1^1*x^(n-1) + nCn*1*x^n.

Ezt deriválva

n*(1 + x)^(n-1) = nC0*0 + nC1*1 + nC2*2*x + nC3*3*x^2 + … + nC(n-1)*(n - 1)*x^(n-2) + nCn*n*x^(n-1).

x = 1-et helyettesítve:

n*(1 + 1)^(n-1) = n*2^(n-1) = nC0*0 + nC1*1 + nC2*2 + … + nC(n-1)*(n-1) + nCN*n,

ami éppen nekünk kell.

Viszont a második feladatot nem értem. Mi az, hogy elemeinek összege? Például ha a halmaz az osztálytársaim halmaza, akkor hogy adom össze az elemeit?

(De azt sejtem, hogy ott még egyszer kell deriválni, és aztán helyettesíteni x = 1-et.)

Oké, akkor például

A = {4, 5}.

n = 2.

Az A részhalmazai:

{}, {4}, {5}, {4, 5}.

Ezek elemeinek összege:

4 + 5 + 4 + 5 = 18.

n*(n+1)/2*2^(n-1) = 2*3/2*2 = 6.

A kettő hírből sem ugyanaz, szóval biztos nem igaz, amit bizonyítani kéne.