Compute this sum $\sum\limits_{i=3}^n \binom{n}{i} \frac{i!2^{i-3}}{(i-3)!}$

Question

I'm having problems calculating this:

$$\sum_{i=3}^n \binom{n}{i} \frac{i!2^{i-3}}{(i-3)!}$$

I got that it equals to $3^n$ but it's not the correct answer.

P.S. If it is necessary I can provide my wrong calculation.

Answer 1

Because I like combinatorial arguments:

You have a box of white balls numbered $1$ through $n$. You pick at least $3$ of these balls and paint them red. Then you select $3$ of the red balls and line them up on the table. Finally, you paint a gold star on any subset of the remaining red balls and throw all of the balls back into the box except the $3$ red ones lined up on the table. How many different outcomes are possible?

If you initially pick $k$ balls to paint red, there are $\binom{n}k$ ways to choose them. Once you have them, there are

$$k(k-1)(k-2)=\frac{k!}{(k-3)!}$$

ways to choose $3$ of the $k$ red balls and line them up. Finally, there are $2^{k-3}$ ways to choose a subset of the remaining red balls to receive gold stars. The total number of outcomes with $k$ red balls is therefore

$$\binom{n}k\frac{k!2^{k-3}}{(k-3)!}\;,$$

and since the possible values of $k$ are $3,4,\ldots,n$, the total number of possible outcomes is

$$\sum_{k=3}^n\binom{n}k\frac{k!2^{k-3}}{(k-3)!}\;.$$

On the other hand, we can get exactly the same set of outcomes by a much simpler procedure. First pick $3$ balls, paint them red, and line them up on the table; this can be done in $n(n-1)(n-2)$ ways. Then divide the remaining $n-3$ balls into $3$ sets, say $W,R$, and $S$, do nothing to the balls in $W$, paint the balls in $R$ and $S$ red, and paint a gold star on the balls in $S$. (Any of these three sets can be empty, but every ball must be in exactly one of them.) This step is just making a $3$-way choice of sets for each of $n-3$ balls, so it can be carried out in $3^{n-3}$ different ways. Thus, the number of possible outcomes is $n(n-1)(n-2)3^{n-3}$, and we have

$$\sum_{k=3}^n\binom{n}k\frac{k!2^{k-3}}{(k-3)!}=n(n-1)(n-2)3^{n-3}=\frac{n!3^{n-3}}{(n-3)!}\;.$$

Answer 2

Expanding Did's comment, $$n(n-1)(n-2)\sum_{i=3}^{n}\binom{n-3}{i-3}2^{i-3}=n(n-1)(n-2)\sum_{k=0}^{n-3}\binom{n-3}{k}2^k = n(n-1)(n-2)(1+2)^{n-3}=\color{red}{n(n-1)(n-2)3^{n-3}}.$$