Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Please you apologize me by my English.

I don't know how make that: $$(n+a)^b = \Theta(n^b), b > 0$$ I know, I must to find two constants such that: $$ c_{1} n^b \leq (n+a)^b \leq c_{2} n^b $$

I do not know what else to do. I'v tried with the Newton's binomial, but I'm lost.

share|improve this question
    
What problem did you run into when using Newton's binomial? –  Alex R. Apr 7 '12 at 0:35
    
Have you considered bounding $n+a$ above and below by a constant times $n$ (a constant that can possibly be dependent on $a,b$)? If you can do this you're set. –  Alex R. Apr 7 '12 at 0:38
    
That: $(n+a)^b$ –  Albert Apr 7 '12 at 0:38
    
Please refrain from using "please," "help" and many "..." etc. Both in title and in body. Thank you. –  user2468 Apr 7 '12 at 4:06
1  
Ok... I'm sorry –  Albert Apr 7 '12 at 15:56

3 Answers 3

up vote 4 down vote accepted

If $a \geq 0$ then

$$(n+0)^b \leq (n+a)^b \,,$$

thus $c_1=1$ works.

Also, for all $n \geq a$ you have

$$(n+a)^b \leq (2n)^b =2^b n^b \,.$$

Now, fixing

$$c_2 = \max \{ 2^b, \frac{(n+1)^b}{n^b},..., \frac{(n+n-1)^b}{n^b} \}$$

you get the desired inequality.

For $a \leq 0$ you can get the inequlities the other way around, excepting that you'll have an issue if $a$ is a negative integer (what happens if $n=-a$?).

share|improve this answer

For the upper bound, $(n+a)^b = n^b(1+a/n)^b $. If $n/a > b$, $(1+a/n)^b < (1+1/b)^b < e$, so we can take $c_2 = e$ for large enough $n$.

By taking $n$ large enough compared to $a$ and $b$, we can take any value greater than 1 for $c_2$.

share|improve this answer

Here, $(n+a)^{b} = n^{b} + a^{b} + ... \geq n^{b} \Longrightarrow (n+a)^{b} = \Omega (n^{b} ),$

$ Also, by \space definition, f(n) = O (g(n)), n \rightarrow \infty \Longrightarrow |f(n)| \leq M(g(n)) $

$ As \space n \rightarrow \infty (n >> a), (n + a) \leq 2n $

$(n+a)^{b} \leq(2n)^{b}\leq k*n^{b}\Longrightarrow (n+a)^{b} = O (n^{b} ), $

$Since (n+a)^{b} = \Omega (n^{b} ), and (n+a)^{b} = O (n^{b} ),$

$\Longrightarrow(n+a)^{b} = \Theta (n^{b} )$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.