KöMaL 2010 A519

Let $n \ge$3 and $k$ be positive integers. We place $n$ coins on the table with the heads sides up. Then the following operation is performed $k$ times: we choose one of the $n$ coins randomly, with equal probabilities, and flip that coin. Prove that the probability that the procedure results in all the $n$ coins lying with tails up is less than $\frac{1}{2^{n-1}}$.