<s>[INST] $T(n) = T(n-1) + T(n-2) + n \in \Theta(2^n)$ I've tried enclosing $T(n)$ between two functions that represent the lower bound and upper bound, respectively, and prove that both of them are in $\Theta(2^n)$
I've noticed a good candidate for the upper bound would be $S(n) = S(n-1) + S(n-1) + n = 2S(n-1) + n = 4S(n-2) + 2(n-1) + n = 2^{n-1} + 2^{n-2} \cdot 2 + 2^{n-3} \cdot 3 + ... + 2^2(n-2) + 2(n-1) + n$
$2S(n) = 2^{n} + 2^{n-1} \cdot 2 + 2^{n-2} \cdot 3 + ... + 2^3(n-2) + 2^2(n-1) + 2n$
$2S(n) - S(n) = 2^n + 2^{n-1} + 2^{n-2} + 2^{n-3} + ... + 2^3 + 2^2 + 2 + n$ (and we multiply by 2 again)
$2S(n) = 2^{n+1} + 2^n + 2^{n-1} + ... + 2^4 + 2^3 + 2^2 + 2n$
$2S(n) - S(n) = 2^{n+1} + 2 + n \in \Theta(2^{n+1})$
As for the lower bound part, I tried choosing $I(n) = 2I(n-2) + n$ but haven't reached any valid result since it decreases exponentially faster. Any tip would be appreciated.
 [/INST] Note that $$T(n)+n+3=T(n-1)+n+2+T(n-2)+n+1$$ hence $S(n)=T(n)+n+3$ solves the recursion $$S(n)=S(n-1)+S(n-2)$$ The characteristic equation reads $$x^2=x+1$$ hence, except for specific initial conditions, $S(n)=\Theta(\lambda^n)$ with $$\lambda=\frac{1+\sqrt5}2\approx1.618$$ Since $\lambda>1$, one gets $$T(n)\in\Theta(\lambda^n)$$ in particular, $$T(n)\notin\Theta(2^n)$$
</s>