Originally Posted by

**Greg98** Hello,

the problem is to prove basic Big-O identity:

$\displaystyle (1+O(1))^n=2^{O(n)}$

I tried following combinatorial identity, but I didn't know how to continue after using it once:

$\displaystyle (1+x)^n=\displaystyle\sum\limits_{j=0}^n \binom {n} {j}x^j$

Maybe combining with this would yield some results:

$\displaystyle \displaystyle\binom {n} {0}+\binom {n} {1}+\binom {n} {2}+...+\binom {n} {n}=2^n$

Also this theorem might be useful:

$\displaystyle O(f(n)+O(g(n)))=O(f(n)+g(n))=O(max\{{f(n),g(n)\})$

Any help is appreciated. Thank you!