S
=
{
1
,
2
,
3
,
…
n
}
Let
S
be a set of first
n
natural numbers.
Let
max
(
P
)
be the maximal element of the subset
P
.
Find the sum of
max
(
P
)
for all subsets of
S
except the Empty Set.
Let the sum be denoted by
f
(
n
)
.
Submit the value of
f
(
1
9
)
Example f ( 2 ) = max ( { 1 } ) + max ( { 2 } ) + max ( { 1 , 2 } ) = 1 + 2 + 2 = 5
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
We'll try to find a recursive relation for
f
(
n
)
.
Note that for a natural
n
added to the set
S
=
{
1
,
2
,
3
…
n
−
1
}
, there are exactly
2
n
−
1
new sets created for which
n
is the maximal element. So, we can say that:
f
(
n
)
=
f
(
n
−
1
)
+
n
2
n
−
1
This recursion can be solved using a program or we can find a closed form to it.
We can see that since
f
(
1
)
=
1
f
(
n
)
=
i
=
1
∑
n
i
2
i
−
1
Consider,
g
(
n
,
a
)
=
i
=
1
∑
n
a
i
=
a
−
1
a
(
a
n
−
1
)
for some real
a
and
a
=
1
Differentiating w.r.t
a
∂
a
∂
g
(
n
,
a
)
=
g
′
(
n
,
a
)
=
i
=
1
∑
n
i
a
i
−
1
=
(
a
−
1
)
2
(
a
−
1
)
(
(
n
+
1
)
a
n
−
1
)
−
(
a
n
+
1
−
a
)
We see that,
g
′
(
n
,
2
)
=
f
(
n
)
=
1
(
n
+
1
)
2
n
−
1
−
2
n
+
1
+
2
=
(
n
+
1
)
2
n
−
2
n
+
1
+
1
Plugging in
n
=
1
9
f
(
1
9
)
=
9
4
3
7
1
8
5
Problem Loading...
Note Loading...
Set Loading...
Let S = { 1 , 2 , … , N } . For any n < N , the number of subsets of S for which n is the maximal element is 2 n − 1 , since each natural number less than n is either in the subset, or it isn't. So 1 will occur 1 time in the computation of f ( N ) , 2 will occur 2 times, 3 will occur 4 times, etc. Thus f ( 1 9 ) = n = 1 ∑ 1 9 n 2 n − 1 = 9 4 3 7 1 8 5