# Thread: Simple Big-O identity

1. ## Simple Big-O identity

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!

2. 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!
Does:

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

help?

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

CB