Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$?Also, why is $f(n) = \Theta(g(n))$ where $f(n) = n^{\log_49}$ and $g(n) = 3^{\log_2 n}$?I know what notations mean - I just want to prove them.
Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$?
asymptotics
Since you get  $$g(n) = \sum_{i=1}^n (n/i)^2\geq n^2\sum_{i=1}^1 (1/i)^2=n^2\cdot H_n^{(2)}$$Where $H_n^{(2)}$ is the second generalized harmonic number.Since $$\forall n\geq 1:\ \  1 < H_n^{(2)} < \frac{\pi^2}{6}$$You get that $$n^2 < g(n) < n^2 \cdot \frac{\pi^2}{6}$$and $$f(n)=\frac{n(n+1)}{2}\leq \frac{(n+1)^2}{2}\leq \frac{(2n)^2}{2}\leq 2n^2$$$$f(n)=\frac{n(n+1)}{2} \geq \frac{n^2}{2}$$Then $$\forall n\geq 1: \frac{3}{\pi^2} g(n) \leq f(n)\leq 2\cdot g(n)$$And thus $f(n)=\Theta(g(n))$.As for the second part of the question:Since $$\forall x,y,z>0:x^{\log_z y}=(z^{\log_z x})^{\log_z y}=z^{\log_z x\cdot {\log_z y}}=(z^{\log_z y})^{\log_z x}=y^{\log_z x}$$ you get that:$$g(x)=3^{\log_2 n}=n^{\log_2 3}=n^{\log_4 9}$$And thus $$f(n)=\Theta(g(n))$$