1
$\begingroup$

Let G(S) denote the sum of the elements of set S and F(n) be the sum of G(s) for all subsets of the set consisting of the first n natural numbers. For example, F(3) = (1) + (2) + (3) + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24. Given n, calculate F(1) + F(2) + ... + F(n).

Input:
1
2
3
Output:
1
7
31

How do i go about solving for an equation for sum of F(n) n = 1 to n.
I know the answer - but no idea how to arrive at it

1 Answers 1

1

Each element of $\{1,2,3, \ldots,n\}$ is part of $2^{(n-1)}$ subsets. So you are looking for $F(n)=\sum_{i=1}^n i2^{(n-1)}=2^{(n-1)}\frac{n(n+1)}{2}=2^{n-2}n(n+1)$ Then you need to sum this over $n$ for your final answer.

  • 0
    @Sivaram: Thanks. I dashed mine off as I ran out the door. As you say, you need to take the derivative with respect to the base, not the exponent.2011-01-31