Too long to fit in a comment and render all the math correctly... but why can't we just expand out $f_k(n)$ to 
$$ f_k(n) = \frac{n!}{n^k(n-k)!} = \prod_{j=1}^{k}\left(1-\frac{j-1}{n}\right) $$
Since the terms in this product expansion are indexed in decreasing order, for any $k$ we immediately have, for instance:
$$ \left(1-\frac{k-1}{n}\right)^{k-1} \leq f_k(n) \leq \left(1-\frac{1}{n}\right)^{k-1}.$$
Aren't things easy from here?