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}.$$
On the other hand, if we want to be more refined (as indicated by your comment), one can keep track of the product more carefully. Isolating the $n^{-1}$ terms gives us:
$$f_k(n) = 1 - \left(\frac{1}{n}+\cdots + \frac{k-1}{n}\right) +\text{O}(n^{-2})$$ and of course the expression in parentheses is just $\frac{k(k-1)}{n}$.