Proof of asymptotic expansion of binomial coefficient

Question

here's the problem I'm currently stuck on:

Prove that (for $k$ fixed):

$$\binom{N}{k}=\frac{N^{k}}{k!}+O(N^{k-1})$$

I know that:

$$\binom{N}{k}\le\frac{N^{k}}{k!}$$

But I'm not sure how to rigorously acquire that $O(N^{r-1})$ term. Any help? Question is exercise 4.4 of Sedgewick & Flagolet's "Analysis of Algorithms", 2nd Edition, if that helps.

Answer 1

Just expand the definition of the binomial coefficient in terms of factorials: $$\binom{N}{k} = \frac{N(N-1)(N-2)\cdots(N-k+1)}{k!} = \frac{N^k + aN^{k-1} + bN^{k-2} + \cdots}{k!}$$ since the numerator is just a polynomial.