We want to find $T(n)$ given the recurrence $$T(n) = 3T(n/2) + n$$ Let us write $n= 2^m$ and call $g(m) = T(2^m)$. We then have
\begin{align}
g(m) & = 3 g(m-1) + 2^m = 2^m + 3 (2^{m-1} + 3g(m-2)) = 2^m + 3 \cdot 2^{m-1} + 3^2 g(m-2)\\
& = 2^m + 3 \cdot 2^{m-1} + 3^2 \cdot 2^{m-2} + 3^3 g(m-3)\\
& = 2^m + 3 \cdot 2^{m-1} + 3^2 \cdot 2^{m-2} + 3^3 \cdot 2^{m-3} + 3^4 g(m-4)
\end{align}
Hence, using induction, you can prove that
\begin{align}
g(m) & = 2^m + \left(\dfrac32\right) \cdot 2^m + \left(\dfrac32\right)^2 \cdot 2^m + \cdots + \left(\dfrac32\right)^{m-1} \cdot 2^m + 3^m g(0)\\
& = 2^m \dfrac{(3/2)^m-1}{3/2-1} + 3^m g(0) = 2 \cdot (3^m-2^m) + 3^m g(0)\\
& = (g(0) + 2) 3^m - 2^{m+1} = (g(0) + 2) 3^{\log_2(n)} - 2n\\
& = (g(0) + 2) n^{\log_2(3)} - 2n\\
\end{align}
Hence, $T(n)$ grows as $n^{\log_2(3)}$.
Are you familiar with differential equations? Solving linear recurrences is the same as solving linear differential equations, essentially. Linear recurrences (ie., difference equations) are discrete differential equations.
So for $a_{n} = 4a_{n-1} - 3a_{n-2}$, we start by setting up our characteristic polynomial: $\lambda^{2} - 4\lambda + 3 = 0$. You then solve for $\lambda$, getting solutions $\lambda = 1, 3$. And so your general form equation $a_{n} = c_{1}(\lambda_{1})^{n} + c_{2}(\lambda_{2})^{n}$.
To set up the characteristic polynomial, you look at the difference of the indices. So for $a_{n}$, we see indices $n, n-1, n-2$. Clearly there is a difference of two between the largest and smallest index. So we have a quadratic. The largest indexed term has the largest power. So $a_{n} \to \lambda^{2}$, $4a_{n-1} \to 4\lambda$, and $-3a_{n-2} \to -3$. Do you see how I got that?
So $a_{n} = c_{1} + c_{2}3^{n}$. Then plug in your constraints and solve for $c_{1}$ and $c_{2}$.
Now for your example with Fibonacci, we have $a_{n} = a_{n-1} + a_{n-2}$, we have another quadratic. Do you see why? So $a_{n} \to \lambda^{2}$, $a_{n-1} \to \lambda$, $a_{n-2} \to 1$. And so our characteristic polynomial is $\lambda^{2} - \lambda - 1 = 0$. Solve for $\lambda$, which gives you two distinct roots $\lambda_{1}, \lambda_{2}$, then plug in: $a_{n} = c_{1} \lambda_{1}^{n} + c_{2}\lambda_{2}^{n}$ and solve the system of equations from your initial conditions.
Now for a first order non-homogenous recurrence of the form $a_{n} = ra_{n-1} + c$, we get a solution of the form $a_{n} = kr^{n} + c \frac{r^{n}-1}{r -1 }$ for $r \neq 1$. If $r = 1$, we get $a_{n} = k + cn$.
The constant $k$ is what we solve for based on the initial conditions.
Best Answer
Yes, there is a closed-form solution to your recurrence relation. Methods to obtain this are in most texts on generating functions. (My particular favorite is Wilf's generatingfunctionology; see section 2.2 The Calculus of Formal Ordinary Power Series Generating Functions.) As a brief summary of the method, the main idea is to convert the recurrence relation about the $f_n$'s to an analogous relation about the generating function $F(x)=\sum_{n\ge0}f_nx^n$. In your recurrence relation, there are two main conversions. The first is a shift of indices, as in $f_{n+3}$. Here the generating function of the sequence $\langle f_{n+3}:n\ge0\rangle$ is $\frac{F(x)-f_0-f_1x-f_2x^2}{x^3}$. The second conversion involves multiplication by a non-constant coefficient, as in $n+3$. Here if $A(x)$ is the generating function of a sequence $\langle a_n:n\ge0\rangle$, then $xD[A(x)]$ is the generating function of the sequence $\langle n\cdot a_n:n\ge0\rangle$, where $D$ stands for the derivative. Therefore, your recurrence relation is equivalent to the following differential equation about the generating function $F(x)$:
\begin{align*}(xD+3)\frac{F(x)-f_0-f_1x-f_2x^2}{x^3}&-2(xD+2)\frac{F(x)-f_0-f_1x}{x^2}\\ +&(xD-1)\frac{F(x)-f_0}{x} +2F(x)=0. \end{align*} This relation turns out to be a first-order differential equation for the generating function $F(x)$, where the coefficients of $F(x)$ and $F'(x)$ are rational functions of $x$. The exact solution depends on the initial conditions $f_0, f_1, f_2$ of the recurrence relation (which you did not state), but in general the differential equation can be solved with standard methods from a calculus or differential equations class. Once you get this generating function $F(x)$, hopefully it will be straightforward to extract its coefficients, thereby producing an exact solution to the recurrence relation.