Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
How do i sum it over n –  Rishi Jan 31 '11 at 15:53
    
How do i sum it over n –  Rishi Jan 31 '11 at 15:56
    
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. –  Ross Millikan Jan 31 '11 at 16:01
    
@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. –  user17762 Jan 31 '11 at 16:01
    
@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. –  Ross Millikan Jan 31 '11 at 16:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.