I'm trying to rigorously solve the Time Complexity $T(n)$ of the naive (no memoization) recursive algorithm that computes the Fibonacci numbers.
In other words I'm looking for $f(n):T(n)\in\Theta(f(n))$.
I see a lot of solutions online that go with the following assumption:
$$T(n) = \left\{\begin{matrix} g(n) && n=1,2 \\ T(n-1) + T(n-2) && n\geq3 && \end{matrix}\right.$$
which means that $T(n)=g(1)F_{n-2} + g(2)F_{n-1}$ for $n\ge2$, where $F_k$ is the $k$-th Fibonacci number with $F_0=0$, $F_1=1$. In other words:
$T(n) = \frac{g(1)\left(\left(\frac{1+\sqrt5}{2} \right)^{n-2}-\left(\frac{1-\sqrt5}{2} \right)^{n-2}\right) + g(2)\left(\left(\frac{1+\sqrt5}{2} \right)^{n-1}-\left(\frac{1-\sqrt5}{2} \right)^{n-1}\right)}{\sqrt5}\in\Theta\left(\left(\frac{1+\sqrt5}{2} \right)^n\right)$
My favourite way of arriving at this explicit formula is to describe the recursion as a linear mapping, diagonalizing the resulting matrix and using the eigenvalues to calculate its $n$th product.
However, there are efforts involved in every recursive step to sum both numbers. We therefore have:
$$T(n) = \left\{\begin{matrix} g(n) && n=1,2\\ T(n-1) + T(n-2) + c&& n\geq3 && \end{matrix}\right.$$
Using the linear algebra (linear mapping) method to find the solution here cannot be used, because of $c$ being an inhomogeneity.
How do I calculate the solution?
Let $h(n)=T(n)+c$ for all $n$ where $c$ is the constant in the question. Then $$h(n)=h(n-1)+h(n-2).$$ We will obtain $h(n)\in\Theta(\left(\frac{1+\sqrt5}{2} \right)^n)$. Hence, so is $T(n)=h(n)-c$.
In case you don't think that $c$ is a constant, we could assume that $c\in\Theta(1)$. That is, $c_1\le c\le c_2$ for two positive constants $c_1$ and $c_2$.
Consider $$h_1(n)=\begin{cases}T(n)+c_1&\text{if } n<3\\ h_1(n-1)+h_1(n-2)&\text{if } n\ge3\end{cases}.$$ Verify by induction that $h_1(n)\le T(n)+c_1$. We know that $h_1(n)\in\Theta(\left(\frac{1+\sqrt5}{2} \right)^n)$.
Replacing $c_1$ with $c_2$, we can define similarly $$h_2(n)=\begin{cases}T(n)+c_2&\text{if } n<3\\ h_2(n-1)+h_2(n-2)&\text{if } n\ge3\end{cases}.$$ Verify by induction that $h_2(n)\ge T(n)+c_2$. We know that $h_2(n)\in\Theta(\left(\frac{1+\sqrt5}{2} \right)^n)$.
Since $h_1(n)-c_1\le T(n)\le h_2(n)-c_2$, we know $T(n)\in\Theta(\left(\frac{1+\sqrt5}{2} \right)^n)$.
In case you are concerned that Fibonacci numbers grows exponentially such that $c\in\Theta(n)$, let us assume $c_1n\le c\le c_2n$ for two positive constants $c_1$ and $c_2$.
We will initialize $h_1(n)=T(n)+c_1(n+3)$ for $n<3$ instead. Verify by induction that $h_1(n)\le T(n)+c_1(n+3)$. We will also initialize $h_2(n)=T(n)+c_2(n+3)$ for $n<3$ instead. Verify by induction that $h_2(n)\ge T(n)+c_2(n+3)$.
Similarly to the reasoning above, we can see that $T(n)\in\Theta(\left(\frac{1+\sqrt5}{2} \right)^n)$ still.