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

Thread: Sum of functions

  1. #1
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Sum of functions

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

    Re: Sum of functions

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

    $\displaystyle 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 $\displaystyle \{1,2,3,4\}$. Then, we have four "types" of subsets X:
    a) subsets containing 4 integers - there's one such subset which is $\displaystyle \{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,115
    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 $\displaystyle \{1,2,3,4\}$. Then, we have four "types" of subsets X:
    a) subsets containing 4 integers - there's one such subset which is $\displaystyle \{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 $\displaystyle 2^{n-3}$.
    Which doesn't hold here as $\displaystyle 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,115
    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 $\displaystyle 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 $\displaystyle 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,115
    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 $\displaystyle 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 $\displaystyle 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 $\displaystyle 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,115
    Thanks
    7

    Re: Sum of functions

    Quote Originally Posted by GGPaltrow View Post
    OK. So $\displaystyle 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,115
    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 $\displaystyle 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
    21,782
    Thanks
    2824
    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 $\displaystyle n=5$.
    Now $\displaystyle \frac{1}{5-(b-a)}=\frac{1}{5},~\frac{1}{4},~\frac{1}{3},~\frac{1 }{2},\text{ or }1$

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

    It equals $\displaystyle \frac{1}{4}$ in four ways: $\displaystyle 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,115
    Thanks
    7

    Re: Sum of functions

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

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

    $\displaystyle b-a=(n-1)-1=n-2$ and $\displaystyle 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 $\displaystyle 2*2^{n-3}$.

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

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

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

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

    $\displaystyle \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}$

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

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

    $\displaystyle =2^{n-1}-1+1$

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

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    Awards
    1

    Re: Sum of functions

    Quote Originally Posted by alexmahone View Post
    Following the idea of my previous posts, consider n different cases:
    $\displaystyle b-a=n-1$ and $\displaystyle f(X)=1$
    Here, the smallest and greatest elements must be 1 and n respectively.
    The number of such subsets is $\displaystyle 1*2^{n-2}$.
    $\displaystyle =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: Apr 15th 2010, 05:50 PM
  2. Replies: 3
    Last Post: Feb 23rd 2010, 04:54 PM
  3. Replies: 11
    Last Post: Nov 15th 2009, 11:22 AM
  4. Replies: 7
    Last Post: Aug 12th 2009, 04:41 PM
  5. Replies: 1
    Last Post: Apr 15th 2008, 09:00 AM

Search Tags


/mathhelpforum @mathhelpforum