Using Newton Binomials and Combinatorics to reach this big O result?

Question

I'm trying to understand this theorem proof:

Theorem. Given a set of n agents, the dynamic programming algorithm, DP, computes an optimal coalition structure in $O(3^n)$ time.

Proof of theorem

How can I connect the concepts to find $O(3^n)$? You don't need to understand the context to answer the question, I just need someone who knows how to extract the big O notation from sum series.

And why a = 2, and b = 1?

Full article: http://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aij2015a.pdf

Answer 1

Plug $a=2,b=1$ in the Binomial formula:

$$(2+1)^n=\sum_{k=0}^n \binom nk 2^k1^{n-1},$$

$$3^n=\sum_{k=0}^n \binom nk 2^k.$$