Results 1 to 2 of 2

Math Help - Simple Big-O identity

  1. #1
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Greg98 View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Another simple trig identity
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: November 21st 2010, 07:43 AM
  2. Simple Trig Identity - help
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: April 24th 2010, 08:05 PM
  3. A simple identity to verify
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: January 25th 2010, 08:08 PM
  4. simple trig identity
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 10th 2008, 07:13 PM
  5. Simple identity
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: May 21st 2007, 02:46 AM

Search Tags


/mathhelpforum @mathhelpforum