Let's consider the set of integers less or equal than a given one:
$latex \displaystyle A=\{1,2,3,...,n\}\:\:n\in\mathbb{N} $
If we add all the elements in this set, we have:
$latex \displaystyle S=\sum_{i\in A}{i}=\sum_{i=1}^n{i}=\frac{n^2+n}{2} $
If we look, at the figure, we can see how the sum ,is equal to the area below the "ladder" plotted:
$latex \displaystyle S=S_{(i)}+S_{(ii)} $
Where $latex S_{(i)} $ is the area formed for $latex n$ small triangles, with a $latex \displaystyle \frac{1}{2}$ area, each one; And $latex S_{(ii)} $ is the area of an isosceles triangle with an equal base and height of $latex n$.
$latex \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:
$latex \displaystyle P(A) = \{X:X\subseteq A=\{1,2,3,...,n\}\}$
There are $latex 2^n$ subsets in $latex \displaystyle P(A) $, (see [3] and [4]):
$latex \displaystyle |P(A)| = 2^{|A|} =2^n$
If $latex \displaystyle i\in A$, then this element is in half of the subsets of $latex \displaystyle P(A)$ (observe the relation between the binary digits and the power set [3]): $latex \displaystyle 2^{n-1}$
To get the final result, it is only necessary to multiply both expresions [2]:
$latex \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:
$latex \displaystyle h(n)=A001788(n)$
$latex \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.
