1. ## Simple Big-O identity

Hello,
the problem is to prove basic Big-O identity:
$(1+O(1))^n=2^{O(n)}$

I tried following combinatorial identity, but I didn't know how to continue after using it once:
$(1+x)^n=\displaystyle\sum\limits_{j=0}^n \binom {n} {j}x^j$

Maybe combining with this would yield some results:
$\displaystyle\binom {n} {0}+\binom {n} {1}+\binom {n} {2}+...+\binom {n} {n}=2^n$

Also this theorem might be useful:
$O(f(n)+O(g(n)))=O(f(n)+g(n))=O(max\{{f(n),g(n)\})$

Any help is appreciated. Thank you!

2. Originally Posted by Greg98
Hello,
the problem is to prove basic Big-O identity:
$(1+O(1))^n=2^{O(n)}$

I tried following combinatorial identity, but I didn't know how to continue after using it once:
$(1+x)^n=\displaystyle\sum\limits_{j=0}^n \binom {n} {j}x^j$

Maybe combining with this would yield some results:
$\displaystyle\binom {n} {0}+\binom {n} {1}+\binom {n} {2}+...+\binom {n} {n}=2^n$

Also this theorem might be useful:
$O(f(n)+O(g(n)))=O(f(n)+g(n))=O(max\{{f(n),g(n)\})$

Any help is appreciated. Thank you!
Does:

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

help?

Alternativly apply the definition of $f(n)=O(1)$ to the left hand side and proceed to simplify and manipulate.

CB