Why is $ \sum_{k = 1}^{n - 1}O\left( \binom{n}{k}k^2 \right) = O(n^22^n)$? In the analysis of an exact dynamic programming analysis for the Travelling Salesman problem in Exact Exponential Algorithms by Fomin and Kratsch, it is stated on p. 6 that
$$ \sum_{k = 1}^{n - 1}O\left( \binom{n}{k}k^2 \right) = O(n^22^n)$$
I would like some help to see why this is true. I understand that 
$$ \sum_{k = 1}^{n - 1} \binom{n}{k} = O(2^n) \qquad \text{and} \qquad \sum_{k = 1}^{n - 1} k^2 = O(n^3) $$
I figure the former in particular is relevant, but I can't see how multiplying by the $k^2$ term inside the sum gets the $n^2$ term in the right-hand side.
 A: The Big - O notation is additive, so you just need to prove:
$$\sum_{k=1}^{n-1}\binom{n}{k}k^2 = O(n^22^n).$$
Note that you don't even need to explicitly calculate the sum, though it is possible. 
Here is a start: 
$$\sum_{k=1}^{n-1}\binom{n}{k}k^2\leq \sum_{k=1}^{n-1}\binom{n}{k}n^2=...$$
A: Edit: after reading the first and second comment of @MishaLavrov I decided to change accordingly my answer and remove inaccuracy regarding the bounding constant.
An approach to the solution to the problem could be this: first remember that
$$
f(n,k)=O\left(\binom{n}{k}k^2\right)\iff |\,f(n,k)|\le M\binom{n}{k}k^2
$$
where $M$ is an absolute bounding constant. Despite not being clearly stated in Fomin & Kratsch book, $n$ and $k$ must be allowed to go to $\infty$: intuitively this is due to the fact that $n$ expresses the number of cities, i.e. the effective difficulty of the task, while the  $k$ expresses the result of partial travel optimization, thus the complexity depends on both. Now we can infer that
$$
\left|\sum_{k=1}^{n-1}f(n,k)\right|=\left|\sum_{k=1}^{n-1}O\left(\binom{n}{k}k^2\right)\right|\le M\sum_{k=1}^{n-1}\binom{n}{k}k^2\iff \sum_{k=1}^{n-1}O\left(\binom{n}{k}k^2\right)=O\left(\sum_{k=1}^{n-1}\binom{n}{k}k^2\right)
$$
Finally, it is an interesting exercise (which can be proved by mathematical induction) that
$$
\sum_{k=1}^{n-1}\binom{n}{k}k^2=(n-1)n2^{n-3}=O(n^2 2^n)
$$
and this should answer to the question.
A: The use of $\mathcal O$-notation in this text bothers me somewhat, because it is sloppy about specifying which variables are going to infinity. So this is a bit of a nonstandard answer. The entire first paragraph of p.6 could be changed to:

Let us come back to $\texttt{TSP}$. The amount of steps required to compute (1.1) for a
  fixed set $S$ of size $\le n$ and all vertices $c_i \in S$ is $\mathcal O(n^2)$. The algorithm computes (1.1) for all subsets $S$ of cities, which is $2^n$ computations of (1.1). Therefore the total time to compute $OPT$ is $$\mathcal O(n^2) \cdot 2^n = \mathcal O(n^2 2^n).$$

This should be easier to understand; it avoids any use of the binomial theorem and avoids writing $\mathcal O$-expressions with respect to two non-constant variables.
