Number of subsets whose maximal element is $t$

Question

I have been asked to count the number of subsets of $\{1,...,n\}$ whose maximal element is $t$ for some $1 \leq t \leq n$.

I said the following:

The size of a subset whose maximal element is $1 \leq t \leq n$ can be of sizes $1,2,...,t$. The element $t$ must be in the subset, and if the subset is of size $k$ then there are $\binom{t-1}{k-1}$ ways to choose the other elements. Therefore, the answer is: $\sum_{k=0}^{t-1} \binom{t-1}{k}$, which according to the binomial coefficient theorem is equal to $2^{t-1}$.

However, I'd like to verify my above answer.

Furthermore, I am interested in computing the below sum, which is related, but I can not find a closed form. How do I go about this?

$\sum_{t=1}^{n} t \cdot 2^{t-1}$

Answer 1

It's just equal to the number of subsets of $\{1,\ldots,t{-}1\}$ (that accompany the required element $t$)

That is, $2^{t-1}$, as you have found.

Your closed form is $(n-1)*2^n + 1$, as OEIS A000337 will quickly tell you, and can be shown by induction fairly easily.

Answer 2

By taking the conditions into account, you should pick elements from this set: $\{1,...,t-1\}$

Each element of the set can be or not be in the subset, so there are 2 ways for each.

You have $t-1$ elements and each has $2$ ways, so the answer is like:

$2*2*...*2=2^{t-1}$

Answer 3

Another way to see the closed-form value of the sum you ask about at the end: Define $f(a) = \sum_{t = 1}^n t a^{t-1}.$ Then $$ f(a) = \frac{d}{da} \left[ \sum_{t = 1}^n a^t \right] = \frac{d}{da} \left[ \frac{a^{n+1} - a}{a - 1}\right] = \frac{[(n+1)a^{n} - 1](a-1) - (a^{n+1} - a)}{(a-1)^2} $$ and the sum you want is $f(2) = ((n+1) 2^n- 1) - (2^{n+1} - 2) = (n-1)2^n + 1.$