Show that for any real constants a and b, where b > 0, (n + a) b = Θ(n b ).

Question

Show that for any real constants a and b, where b > 0,

$(n + a)^b = Θ(n^b)$.

So taking a stab at this.. I let $a = 0$, and $b = 1$

So I got $f(n) = (n + a)^b \implies f(n) = (n+0)^1$ which we know $\implies n^1$ or $O(n) \implies \Theta(n^1)$ ? I just took a guess. I'm not sure if that's even close to being right.

Answer 1

From the generalized binomial theorem, we have $$(n+a)^b = \sum_{k=0}^\infty\binom bk n^{b-k}a^k. $$ If $b$ is not an integer, we define $$\binom bk := \frac{(b)_k}{k!} $$ where $$(b)_k := \prod_{i=0}^{k-1} (r-i).$$ From this it follows that $$(n+a)^b = n^b + \Omega(n^{b-1}),$$ and hence $(n+a)^b \in\Theta(n^b)$.