# Help proving that $(n+a)^b = \Theta(n^b)$

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.

-
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
Ok... I'm sorry –  Albert Apr 7 '12 at 15:56

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$?).

-

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$.

-

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} )$

-