Apologies if the question is ambiguous; English is not my native language. My partial solution to the problem may convey the issue more accurately: the recurrence to solve is
$$g(n) - g(n-1) - 2g(n-2) + 2g(n-3) = 0.$$
Its polynomial is thus
$$x^3 - x^2 - 2x + 2$$
and the roots I obtain are
$$(x - 1)(x - \sqrt{2})(x + \sqrt{2}).$$
With the initial conditions being
$$g(0) = 106$$ $$g(1) = 100$$ $$g(2) = 112$$
the general form is therefore
$$g(n) = 3\sqrt{2}^n + 3(-\sqrt{2})^n + 100.$$
The issue arises when I try to prove the exact order of the recurrence ($\Theta(\sqrt{2}^n)$) using the limit test. My attempt goes as such:
$$ \begin{align*} \lim_{n\to\infty} \frac{3\sqrt{2}^n + 3(-\sqrt{2})^n + 100}{\sqrt{2}^n} & = \lim_{n\to\infty} \frac{3\sqrt{2}^n}{\sqrt{2}^n} + \lim_{n\to\infty} \frac{3(-\sqrt{2})^n}{\sqrt{2}^n} + \lim_{n\to\infty} \frac{100}{\sqrt{2}^n}\\ & = 3 + \lim_{n\to\infty} \frac{3(-\sqrt{2})^n}{\sqrt{2}^n} + 0\\ & = 3 + \lim_{n\to\infty} \frac{3(-\sqrt{2})^n}{\sqrt{2}^n} \end{align*} $$
The remaining limit diverges and I am confused at this point. I expect the explanation will be something relatively simple in retrospect and also that it will be more closely related to the notion of limits than anything else, but I nonetheless phrased my question in terms of recurrence because my uncertainty partially stems from the fact that I am now unsure whether it is possible or not to give a Big-Theta for every recurrence out there.
Thank you very much for your time and hopefully your help as well. :)
The function $g$ isn’t $\Theta(f(n))$ for any $f$. This is especially clear when you write the function like this:
$$g(n)=\begin{cases} 6\cdot 2^{n/2},&\text{if }n\text{ is even}\\ 100,&\text{if }n\text{ is odd:} \end{cases}$$
this makes it clear that $g(n)$ is $O(\sqrt2^n)$ and $\Omega(1)$, and that neither estimate can be improved.
In fact if $f(n)=g(2n)$ and $h(n)=g(2n+1)$, then $f(n)$ is $\Theta(2^n)$ and $h(n)$ is $\Theta(1)$. The function $g$ restricted to even arguments grows at an entirely different rate from the function $g$ restricted to odd arguments.