0

I have to find a specific $g(n)$ such that $f(n)=\Theta(g(n))$.

$$f(n) = \sum_{i=1}^n3(4^i)+3(3^i)-i^{19}+20$$ I suppose that this can be solved as integrating this formula, but i don't know how and why we can make transition between sum and integral.

$$\lim_{n\to \infty}\sum_{i=1}^n3(4^i)+3(3^i)-i^{19}+20 \to \int ?$$

I know some basics of Riemann's transition from sum to integral with dx, but don't know what to do in this case.

UPD.1

$f(n)=\Theta(g(n))$ means that there exist $c_1 > 0, c_2 > 0$ such that $$c_1g(n)\le f(n) \le c_2g(n)$$ where $n>n_1$

Igor Konoplyanko
  • 105

1 Answers1

3

Using the formula for sum of geometric series we have $$ \begin{array}{rcl} \sum_{i=1}^n 4^i &=&\Theta(4^{n})\\ \sum_{i=1}^n 3^i &=&\Theta(3^n)=o(4^n). \end{array} $$ Here $a_n=o(b_n)$ means that $a_n/b_n\to 0$. Clearly $$\sum_{i=1}^n (i^{19}-20)\leq n (n^{19}-20)\leq n^{20}=o(4^n).$$ Since $\Theta(a_n)+o(a_n)=\Theta(a_n)$ we conclude that $$ f(n)=\Theta(4^n). $$

Lior B-S
  • 2,316