Asymptotic notation: A function is Θ-Notation

Question

H. Cormen, Exercise 3.1-2

The following statement is true? If yes, prove that it is true.

$$ (n+a)^b = Θ(n^b)\\ a, b \in R\\ b>0 $$

I tried to expand $(n+a)^b$ using the Binomial theorem, but I couldn't solve this.

Any help?

Answer 1

for $n>a \ (n+a)^b = (n(1+\frac{a}{n}))^b = O(n^b) \cdot O(1)$. From this you can easily deduce the lower bound.

Answer 2

Notice that $$\lim_{n\to +\infty}\frac{(n+a)^b}{n^b}=1,$$ hence there is some $n_0$ for which if $n\geqslant n_0$, $$\frac 12 n^b\leqslant (n+a)^b\leqslant \frac 32 n^b.$$ This proves that for some $M$, the inequality $$\frac 1M\leqslant \frac{(n+a)^b}{n^b}\leqslant M$$ holds for each $n\geqslant 1$.

More generally, if $(a_n)_{n\geqslant 1}$ and $(b_n)_{n\geqslant 1}$ are two sequences of positive numbers such that $(a_n/b_n)_{n\geqslant 1}$ converges to a positive number, then $a_n=\Theta(b_n)$.