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
    How do i sum it over n2011-01-31
  • 0
    How do i sum it over n2011-01-31
  • 0
    Wolfram Alpha gives $2^{m-1}m^2-2^{m-1}m+2^m-1$ but I would have to work on a derivation. The usual way to sum $n2^n$ is to do x d/dx sum 2^x and evaluate at n. For n^2 you do the x d/dx twice.2011-01-31
  • 0
    @Rishi: $\displaystyle \sum_{k=1}^{n} a^{k} = \frac{a^{n+1}-1}{a-1}$. Now differentiate both sides with respect to $a$ once or twice and plug in $a=2$ to get the desired answer.2011-01-31
  • 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