Analyzing time complexity of solution in tutorial Could someone explain time complexity of solution of in this tutorial?

I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$.

What I figured so far is, for computing $f(Y)$, we would require $O(\lvert Y\rvert)$ steps and for fixed set $X$ (such that $\lvert X\rvert=k$), we would have $2^{n-k}$ number of $Y$ sets that would contain set $X$. And there would be ${n \choose k}$ such $X$ sets.

So total steps should be $${n \choose k } {\sum_{r=0}^{n-k} {n-k \choose r} ({k+r})} \leq {n \choose k} n  2^{n-k}$$

But is this value tightly bounded by $3^k k$?
Let me focus on the following question:


  Is $3^nn$ a tight bound on $\binom{n}{k}n2^{n-k}$?


First, let us see that this is a valid bound. This follows from the binomial theorem:
$$
\sum_{k=0}^n \binom{n}{k} n 2^{n-k} = 3^nn.
$$

Since there are $n+1$ summands in the expression, we deduce that
$$
\max_{0 \leq k \leq n} \binom{n}{k} n 2^{n-k} \ge \frac{3^nn}{n+1}.
$$
Using Stirling's formula, we find out that
$$
\max_{0 \leq k \leq n} \binom{n}{k} n 2^{n-k} = \Theta(3^n\sqrt{n}).
$$
This is a tighter bound.