I am supposed to prove the following:
$$\log_2\Big({1+\Theta\Big(\frac{1}{n}}\Big)\Big) = \log_2\Big(\Theta\Big(\frac{n+1}{n}\Big)\Big)$$
While I get the intuition behind it, I am struggling to write it down on paper. I understand that it is sufficient to show:
$${1+\Theta\Big(\frac{1}{n}}\Big) = \Theta\Big(\frac{n+1}{n}\Big)$$
What I have been able to do so far:
The expression on LHS is of the form $1+f(n)$ and $f(n) = \Theta\Big(\frac{1}{n}\Big)$ where by definition of $\Theta$-notation there exist constants $c_1$, $c_2$ and $n_0$ such that:
$$\frac{c_1}{n} \le f(n) \le \frac{c_2}{n} \quad \forall \quad n \ge n_0 \tag{1}$$
I think that if we can arrive at the following expression, our question will be solved; for some constants $c_3$, $c_4$ and $n_1$:
$$c_3\Big(\frac{n+1}{n}\Big) \le 1 + f(n) \le c_4\Big(\frac{n+1}{n}\Big) \quad \forall \quad n \ge n_1 \tag{2}$$
Thus, to go from eqn. $(1)$ to eqn. $(2)$, let's add $1$ on each side in equation $(1)$ which gives us:
$$1+\frac{c_1}{n} \le 1+f(n) \le 1+\frac{c_2}{n} \quad \forall \quad n \ge n_0$$
$$\frac{n+c_1}{n} \le 1+f(n) \le \frac{n+c_2}{n} \quad \forall \quad n \ge n_0 \tag{3}$$
I don't know how to proceed further……
One way I can think of is that IF we can restrict the value of $c_1$ to be $c_1 \le 1$ and $c_2$ to be $c_2 \ge 1$ then we will be able to do the following:
$$c_1 \le 1$$
$$nc_1 \le n$$
$$\frac{nc_1+c_1}{n} \le \frac{n+c_1}{n}$$
$$c_1\Big(\frac{n+1}{n}\Big) \le \frac{n+c_1}{n} \tag{4}$$
and similarly, starting from $c_2 \ge 1$ we can get:
$$c_2\Big(\frac{n+1}{n}\Big) \ge \frac{n+c_2}{n} \tag{5}$$
Now using $(3)$, $(4)$ and $(5)$ we can get the following: for some constants $c_1 \le 1$ and $c_2 \ge 1$,
$$c_1\Big(\frac{n+1}{n}\Big) \le 1 + f(n) \le c_2\Big(\frac{n+1}{n}\Big) \quad \forall \quad n \ge n_0 \tag{6}$$
This is really just equation $(2)$ with different name for the constant terms, which should in theory conclude our proof.
BUT ARE WE ALLOWED TO PLACE RESTRICTIONS ON THE VALUE OF CONSTANTS LIKE WE DID HERE FOR $c_1$ and $c_2$?
Best Answer
Let me firstly introduce that $\Theta(g)$ is set of functions $\left\lbrace f: \exists c_f,C_f>0, \ \exists N,\ n>N, c_fg \leqslant f \leqslant C_f g\right\rbrace$. We consider only non negative functions.
From definition you see, that we have "$\exists$" for constants $c_f, C_f$ so you can choose them as you want keeping non negativity.
There are some useful properties outgoing from definition: $$f \cdot \Theta(g)=\Theta(g \cdot f)$$ $$\Theta(f) + \Theta(g)=\Theta(g + f)$$ And for $g>0$ holds $\frac{\Theta(f)}{g} = \Theta \left(\frac{f}{g}\right)$
Using these properties you can achieve proof in more short way and it's good to remember, that they holds as set equalities.
Addition: Working with this equalities requires certain accuracy. For example you cannot write $1=\Theta(1)$ in usual meaning of equality. We can wrote $1 \in \Theta(1)$, or $\{1\} \subset \Theta(1)$ where under $1$ we understand $f(n)=1$ function. I.e. $\Theta(1)$ is set of all bounded functions, not only one constant. So we can write only $1+\Theta\left(\frac{1}{n}\right) \subset \Theta(1) + \Theta\left(\frac{1}{n}\right)$.
If/when you want to add one function i.e. set containing only one function to other set of functions, then, usually, you need some additional restrictions. For example: if $ \inf(f)>0 $, then $ \forall C>0 $ we have $ O(f) +C = O(f) = O(f+C) $