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.
Just use generating functions. Define $F(z) = \sum_{n \ge 0} f(n + 1) z^n$, write your recurrence as:
$$
f(n + 2) = f(n + 1) + 2 f(n) + n + 2 + 4 \cdot 2^n + K
$$
Multiply by $z^n$, sum over $n \ge 0$, recognize the resulting sums:
$$
\frac{F(z) - f(1) - f(2) z}{z^2}
= \frac{F(z) - f(1)}{z} + 2 F(z)
+ \frac{z}{(1 - z)^2}
+ \frac{4}{1 - 2 z}
+ \frac{K + 2}{1 - z}
$$
This because:
\begin{align}
\sum_{n \ge 0} z^n
&= \frac{1}{1 - z} \\
\sum_{n \ge 0} n z^n
&= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\
&= \frac{z}{(1 - z)^2}
\end{align}
Solving for $F(z)$, as partial fractions:
$$
F(z)
= \frac{6 K + 13}{12(1 + z)}
+ \frac{3 K - 1}{1 - 2 z}
- \frac{2 K + 5}{4 (1 - z)}
+ \frac{2}{3 (1 - 2 z)^2}
- \frac{1}{6 (1 + z)^2}
$$
Using the generalized binomial theorem you have:
$$
\binom{-m}{k} = (-1)^k \binom{m + k - 1}{m - 1}
$$
In particular:
$$
\binom{-2}{k} = (-1)^k (k + 1)
$$
This allows to read off the coefficients from the above.
Best Answer
Well, you need to find a particular solution of the inhomogeneous equation, and the rhs suggest that something of the form $c(n)3^n$ should work. The simplest form of $c$ is a constant, so try that. If it works, you are golden, if not, try a linear function, etc, then add the homogeneous solution and you are good.