Why is $ \sum_{k = 1}^{n - 1}O\left( \binom{n}{k}k^2 \right) = O(n^22^n)$?

Question

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.

Answer 1

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=...$$

Answer 2

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.

Answer 3

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.