Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Math Help - Sum of functions

  1. #1
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Sum of functions

    A number n\ge1 is given. For a non-empty subset X of the set \{1,2,...,n\}, let a,\ b denominate respectively the smallest and the greatest element of the set X and let f(x)=\frac{1}{n-(b-a)}.
    Determine, according to n, the sum of numbers f(X) for all non-empty subsets X of the set \{1,2,...,n\}

    Could anyone help me with this? I don't even have a clue on how to approach this problem...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Sum of functions

    Quote Originally Posted by GGPaltrow View Post
    A number n\ge1 is given. For a non-empty subset X of the set \{1,2,...,n\}, let a,\ b denominate respectively the smallest and the greatest element of the set X and let f(x)=\frac{1}{n-(b-a)}.
    Determine, according to n, the sum of numbers f(X) for all non-empty subsets X of the set \{1,2,...,n\}

    Could anyone help me with this? I don't even have a clue on how to approach this problem...
    Let me start you off.

    Assume that the smallest and greatest elements of X are 1 and n respectively. The number of such sets is 2^{n-2}. (How?) f(X) = 1.
    Assume that the smallest and greatest elements of X are 1 and n-1 respectively. The number of such sets is 2^{n-3}. f(X) = 1/2.
    etc.

    Sum = 2^{n-2}*1 + 2^{n-3}*\frac{1}{2}+...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: Sum of functions

    Thank you but I don't know if I get the description right. For me, it's as follows:

    Suppose we have a set of \{1,2,3,4\}. Then, we have four "types" of subsets X:
    a) subsets containing 4 integers - there's one such subset which is \{1,2,3,4\}
    b) subsets containing 3 integers - four such subsets: 123, 134, 214, 314
    and so forth.

    And for every "type" and every possibility I should compute the f(X) and then sum all of them. Is that it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Sum of functions

    Quote Originally Posted by GGPaltrow View Post
    Thank you but I don't know if I get the description right. For me, it's as follows:

    Suppose we have a set of \{1,2,3,4\}. Then, we have four "types" of subsets X:
    a) subsets containing 4 integers - there's one such subset which is \{1,2,3,4\}
    b) subsets containing 3 integers - four such subsets: 123, 134, 214, 314
    and so forth.

    And for every "type" and every possibility I should compute the f(X) and then sum all of them. Is that it?
    Yes.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: Sum of functions

    Hmm... But in my example, for a X with the smallest and greatest elements of 1 and n-1=3, there are 4 such sets and you wrote:
    Assume that the smallest and greatest elements of X are 1 and n-1 respectively. The number of such sets is 2^{n-3}.
    Which doesn't hold here as 2^{n-3}=2 and there are four of such. Why?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Sum of functions

    Quote Originally Posted by GGPaltrow View Post
    Hmm... But in my example, for a X with the smallest and greatest elements of 1 and n-1=3, there are 4 such sets and you wrote:

    Which doesn't hold here as 2^{n-3}=2 and there are four of such. Why?
    There are only 2 sets with smallest element 1 and largest element 3. They are: {1, 3} and {1, 2, 3}.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: Sum of functions

    Yes, right, I didn't see you classification was other than mine. Sorry!

    So I suppose the sum is 2^{n-2}*2^0 + 2^{n-3}*2^{-1}+...+2^0*2^{-n}. Is that right? Because something feels incorrect here for me...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Sum of functions

    Quote Originally Posted by GGPaltrow View Post
    Yes, right, I didn't see you classification was other than mine. Sorry!

    So I suppose the sum is 2^{n-2}*2^0 + 2^{n-3}*2^{-1}+...+2^0*2^{-n}. Is that right? Because something feels incorrect here for me...
    That's not right.

    For example: Assume that the smallest and greatest elements of X are 1 and n-2 respectively. The number of such sets is 2^{n-4}. f(X) = 1/3.

    Moreover, you also need to consider the subsets where the smallest and largest elements are 2 and n respectively etc.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: Sum of functions

    OK. So 2^{n-2}*1 + 2^{n-3}*\frac{1}{2}+...+2^0*\frac{1}{n} should do it?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Sum of functions

    Quote Originally Posted by GGPaltrow View Post
    OK. So 2^{n-2}*1 + 2^{n-3}*\frac{1}{2}+...+2^0*\frac{1}{n} should do it?
    This problem is a lot harder than that. Perhaps you didn't read my last sentence in post #8.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Sum of functions

    It may be helpful to note that it is the difference between the largest and smallest element that matters for f(X).

    For example: The number of subsets having smallest and greatest elements 1 and n-1 respectively is equal to the number of subsets having smallest and greatest elements 2 and n respectively (which is equal to 2^{n-2}). f(X) = 1/2 for both these types of subsets.

    This should make the summation easier.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,913
    Thanks
    1760
    Awards
    1

    Re: Sum of functions

    Quote Originally Posted by GGPaltrow View Post
    Because something feels incorrect here for me...
    I agree with you there!
    Take the case n=5.
    Now \frac{1}{5-(b-a)}=\frac{1}{5},~\frac{1}{4},~\frac{1}{3},~\frac{1  }{2},\text{ or }1

    It equals \frac{1}{5} in five ways: X=\{5\},~\{4\},~\{3\},~\{2\},\text{ or }\{1\}.
    For each of those sets f(X)=\frac{1}{5}

    It equals \frac{1}{4} in four ways: X=\{4,5\},~\{3,4\},~\{2,3\},\text{ or }\{1,2\}.

    Then things get complicated.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Sum of functions

    Following the idea of my previous posts, consider n different cases:

    b-a=n-1 and f(X)=1
    Here, the smallest and greatest elements must be 1 and n respectively.
    The number of such subsets is 1*2^{n-2}.

    b-a=(n-1)-1=n-2 and f(X)=\frac{1}{2}
    Here, the smallest and greatest elements can be 1 and n - 1 or 2 and n respectively.
    The number of such subsets is 2*2^{n-3}.

    b-a=(n-2)-1=n-3 and f(X)=\frac{1}{3}
    The number of such subsets is 3*2^{n-4}.

    ..............................

    b-a=2-1=1 and f(X)=\frac{1}{n-1}
    The number of such subsets is (n-1)*2^{n-n}.

    b-a=1-1=0 and f(X)=\frac{1}{n} (Special case)
    The number of such subsets is n.

    \sum f(X)=1*2^{n-2}+\frac{1}{2}*2*2^{n-3}+\frac{1}{3}*3*2^{n-4}+...+\frac{1}{n-1}*(n-1)*2^{n-n}+n*\frac{1}{n}

    =2^{n-2}+2^{n-3}+2^{n-4}+...+1+1

    =1\left(\frac{2^{n-1}-1}{2-1}\right)+1

    =2^{n-1}-1+1

    =2^{n-1}
    Last edited by alexmahone; September 9th 2011 at 05:51 PM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,913
    Thanks
    1760
    Awards
    1

    Re: Sum of functions

    Quote Originally Posted by alexmahone View Post
    Following the idea of my previous posts, consider n different cases:
    b-a=n-1 and f(X)=1
    Here, the smallest and greatest elements must be 1 and n respectively.
    The number of such subsets is 1*2^{n-2}.
    =2^{n-1}
    While that is indeed the correct solution, I wish we could have allowed to original poster a chance to discover this rather well known result on her/his own.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: Sum of functions

    Thank you very much, alexmahone! So I should make something like this for other cases like those you mentioned in #11 or it summarizes it all?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: April 15th 2010, 06:50 PM
  2. Replies: 3
    Last Post: February 23rd 2010, 05:54 PM
  3. Replies: 11
    Last Post: November 15th 2009, 12:22 PM
  4. Replies: 7
    Last Post: August 12th 2009, 05:41 PM
  5. Replies: 1
    Last Post: April 15th 2008, 10:00 AM

Search Tags


/mathhelpforum @mathhelpforum