I have this recurrence relation to solve:
$$a_{n+1}=3a_n+2^{n-1}-1.$$
The homogeneous part's solution is obviously $a_n=k3^n.$ Now I don't know how to solve the original equation, but I do know what to do in the case of a seemingly analogous differential equation. Consider the equation $$y'=3y+2^{x-1}-1.$$ The homogenous part is solved by $y=Ce^{3x}.$ To find the solution of the non-homogeneous equation, I put $y=C(x)e^{3x}$. Then $y'=C'(x)e^{3x}+C(x)3e^{3x}$. But then, substituting, I get $$C'(x)e^{3x}+C(x)3e^{3x}=3C(x)e^{3x}+2^{x-1}-1,$$ or $$C'(x)e^{3x}=2^{x-1}-1,$$ which can be easily solved.
Now, I thought what I should do for my recurrence relation is just take $a_n=k(n)3^n$ like for the differential equation, but this doesn't seem to work. The problem is that now the equation doesn't simplify after the analgous substitution. Simply, if $a_n=k(n)3^n$, then $a_{n+1}=k(n+1)3^{n+1},$ and not $k(n+1)3^n+k(n)3^{n+1}.$
So what's the algorithm here? If possible, please make the algorithm easy to remember by analogy with the algorithm for differential equations given above (for an example equation, but I hope it's clear what I do in the general case). I'm looking more for a way to remember this than for a way to understand it fully. Sorry if this approach offends anyone, but I'm sure that if I know the answer and have an easy way to remember it, then I can figure out a way to understand it.
Best Answer
Your approach will work fine for the difference equation. $$k(n+1)3^{n+1}=k(n)3^{n+1}+2^{n-1}-1$$
Hence $3^{n+1}(k(n+1)-k(n))=2^{n-1}-1$, which you can solve the same way as in the differential equation case. In discrete-land $f(n+1)-f(n)$ serves the same role that $\frac{d}{dx}f(x)$ does in continuous-land.
Nb. In neither case would I choose this approach to use; it's usually easiest to use undetermined coefficients with a suitable guess, as @Qiaochu suggests.