SUMS INSIDE POWER SET

6 02 2009

Let´s consider the set of integers less or equal than a given one:

\displaystyle A=\{1,2,3,...,n\}\:\:n\in\mathbb{N}

If we add all the elements in this set, we have:

\displaystyle S=\sum_{i\in A}{i}=\sum_{i=1}^n{i}=\frac{n^2+n}{2}

If we take a look, at the figure, to the right, we can see how the sum ,is equal to the area below the “ladder” plotted:

\displaystyle S=S_{(i)}+S_{(ii)}

Where S_{(i)} is the area formed for n small triangles, with a \displaystyle \frac{1}{2} area, each one; And S_{(ii)} is the area of an isosceles triangle with an equal base and height of n.

\displaystyle S_{(i)}=\frac{1}{2}\cdot n;\quad S_{(ii)}=\frac{1}{2}\cdot n \cdot n;

And if the aim, of this blog, where to be rigurous instead of, to give simple ideas, an induction proof, should fit here, perfectly [1].
To extend this result to the sum of all the elements, in the subsets included, in the Power Set of integers less or equal to a given one:

\displaystyle P(A) = \{X:X\subseteq A=\{1,2,3,...,n\}\}

There are 2^n subsets in \displaystyle P(A) , (see [3] and [4]):

\displaystyle |P(A)| = 2^{|A|} =2^n

If \displaystyle i\in A, then this element is in half of the subsets of \displaystyle P(A) (observe the relation between the binary digits and the power set [3]): \displaystyle 2^{n-1}
To get the final result, it is only necessary to multiply both expresions [2]:

\displaystyle h(n)=\sum_{i\in X\subseteq P(A)}{i}= \frac{n^2+n}{2} \cdot 2^{n-1}=(n^2+n) \cdot 2^{n-2}


NOTE:

 

\displaystyle h(n)=A001788(n)

\displaystyle\lim_{x \to{+}\infty}{\frac{h(n+1)}{h(n)}}\displaystyle\lim_{x \to{+}\infty}{2+\frac{4}{x}}=2


Archives:

[a]-020609-SUMSINSIDEPOWERSET.nb


References:

[1]-A000217 The On-Line Encyclopedia of Integer Sequences!
[2]-A001788 The On-Line Encyclopedia of Integer Sequences!
[3]-Powerset Construction Algorithm Shriphani Palakodety.
[4]-Course Notes 8: Size of the Power Set. Chris Nowlin.

Advertisements

Actions

Information




%d bloggers like this: