Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.