## 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:

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.