3
$\begingroup$

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.

  • 1
    Ok... I'm sorry2012-04-07

4 Answers 4

5

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

0

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

0

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

-1

I proved it using the binomial expansion , which is

(x+y)n=nC0xny0+nC1xn−1y1+nC2xn−2y2+......nCnx0yn now for the above problem (n+a)b=bC0nba0+nC1nb−1a1+nC2nb−2a2+......nCnn0an

we also now that for any polynomial a0x1+a1x2+a2x2+⋯+anxn≤(a0+a1+a2+⋯+an)xn

substituting bC0a0 with C0, bC1a1 with C1

and so on (because that is a constant) we would get

(n+a)b=C0nb+C1nb−1+C2nb−2+......Cnn0

now i would jump to the following conclusion

C0nb≤C0nb+C1nb−1+C2nb−2+......Cnn0≤(C0+C1+C2+......Cn)nb

which makes (n+a)b=θ(nb)

  • 1
    You do realize that this is a 4 years old question, with 3 more answers, among which an accepted one, do you?2016-11-29