1. ## 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...

2. ## Re: Sum of functions

Originally Posted by GGPaltrow
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}+...$

3. ## 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?

4. ## Re: Sum of functions

Originally Posted by GGPaltrow
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.

5. ## 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?

6. ## Re: Sum of functions

Originally Posted by GGPaltrow
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}.

7. ## 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...

8. ## Re: Sum of functions

Originally Posted by GGPaltrow
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.

9. ## 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?

10. ## Re: Sum of functions

Originally Posted by GGPaltrow
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.

11. ## 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.

12. ## Re: Sum of functions

Originally Posted by GGPaltrow
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.

13. ## 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}$

14. ## Re: Sum of functions

Originally Posted by alexmahone
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.

15. ## 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?

Page 1 of 2 12 Last