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

by MSR   Last Updated October 17, 2018 20:20 PM

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.

Tags :

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

October 16, 2018 20:54 PM

Edit: after reading the comments 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(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.

Daniele Tampieri
October 16, 2018 21:35 PM

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.

Misha Lavrov
October 17, 2018 00:35 AM