# Non-homogeneous linear recurrence relation

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.

-
The algorithm involves substituting terms that resemble the non-homogeneous parts up to polynomial factors, which here means trying something like $a_n = C(n) 2^n + D(n)$ where $C, D$ will end up being polynomials. There's a good reason for this but it requires a little mathematical sophistication to appreciate in full generality. – Qiaochu Yuan May 13 '13 at 2:10
@QiaochuYuan Does it mean that linear recurrence relations are inherently more difficult or complicated than linear differential equations? I didn't give a proof that my way of solving the differential equation works, but I could produce a proof without much trouble. It seems, from what you're saying that here both the algorithm and its justification are more complicated. Do I understand you correctly? – Bartek May 13 '13 at 2:15
No, they're exactly as complicated; you can translate from one to the other by taking Taylor series resp. by constructing exponential generating functions (en.wikipedia.org/wiki/Generating_function). – Qiaochu Yuan May 13 '13 at 2:42

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.

-
Oh, fantastic, I completely missed that. So solving for $k$ will involve a summation instead of the continuous-case integration, right? – Bartek May 13 '13 at 2:19
That's right, @Bartek. – vadim123 May 13 '13 at 2:19
Oh, and that's not good, because, while I know how to integrate, I don't really know how to sum. But in this particular case, I get partial sums of geometric progressions, so I can do it. Great! Thank you very much! :) – Bartek May 13 '13 at 2:27
My pleasure, glad to be of service. – vadim123 May 13 '13 at 2:28

Can use generating functions directly, no guessing. Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get, after recognizing a few sums: $$\frac{A(z) - a_0}{z} = 3 A(z) + \frac{1}{2} \cdot \frac{1}{1 - 2 z} - \frac{1}{1 - z}$$ Solve as partial fractions: $$A(z) = \frac{a_0}{1 - 3 z} - \frac{1}{2} \cdot \frac{1}{1 - 2 z} + \frac{1}{2} \cdot \frac{1}{1 - z}$$ Everything in sight is a geometric series: $$a_n = a_0 \cdot 3^n - \frac{2^n - 1}{2}$$

-