Sum of functions

**GGPaltrow** · September 9th 2011, 05:54 AM

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

**alexmahone** · September 9th 2011, 06:45 AM

Originally Posted by GGPaltrow

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}+...$

**GGPaltrow** · September 9th 2011, 07:10 AM

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?

**alexmahone** · September 9th 2011, 07:12 AM

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 $\{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.

**GGPaltrow** · September 9th 2011, 07:15 AM

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?

**alexmahone** · September 9th 2011, 07:27 AM

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

**GGPaltrow** · September 9th 2011, 07:40 AM

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

**alexmahone** · September 9th 2011, 07:49 AM

Originally Posted by GGPaltrow

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.

**GGPaltrow** · September 9th 2011, 07:55 AM

OK. So $2^{n-2}*1 + 2^{n-3}*\frac{1}{2}+...+2^0*\frac{1}{n}$ should do it?

**alexmahone** · September 9th 2011, 07:58 AM

Originally Posted by GGPaltrow

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.

**alexmahone** · September 9th 2011, 08:12 AM

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.

**Plato** · September 9th 2011, 08:19 AM

Originally Posted by GGPaltrow

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.

**alexmahone** · September 9th 2011, 03:16 PM

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

**Plato** · September 9th 2011, 03:38 PM

Originally Posted by alexmahone

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.

**GGPaltrow** · September 10th 2011, 03:15 AM

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?

Thread: Sum of functions

LinkBack

Thread Tools

Display

Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Re: Sum of functions

Similar Math Help Forum Discussions

Match the functions with their contour plots labeled A - D. Most of these functions a

Circular functions as opposed to traditionally determined trigonometric functions?

[SOLVED] Integration of Incomplete Beta Functions and Hypergeometric Functions

[SOLVED] Chain rule with functions depending on other functions

ntegration of Functions that are the Derivatives of Analytic Functions

Search Tags