Question

Say you have the recurrence relation \[a_n-2 a_{n-1}=e^{n} \text{ with } a_0=\frac{2e-2}{e-2} \]... And we want to find a explicit form for the relation. The only way I know of is...

Answer 1

\[\text{ charecterisitc equation is } r-2=0 \\ r=2 \\ \text{ so } a_{n_h}=c(2)^n \\ \text{ now particular solution } a_{n_{p}} \\ \text{ so } a_{n_p}=k e^{n} \\ a_{{n-1}_p}=ke^{n-1} \\ ke^{n}-2ke^{n-1}=e^{n} \\ k-2ke^{-1}=1 \\ k=\frac{1}{1-2e^{-1}}=\frac{e}{e-2} \\ \text{ so the solution is } \\ a_n=c (2)^n+\frac{e}{e-2} e^{n} \\ \text{ where we need to apply the } a_0=\frac{2e-2}{e-2} \text{ thing } \\ a_0=c(2)^0+\frac{e}{e-2}e^0 \\ \frac{2e-2}{e-2}=c+\frac{e}{e-2} \\ \frac{2e-2-e}{e-2}=c \\ c=\frac{e-2}{e-2}=1 \\ \text{ so the solution is } a_n=(2)^n+\frac{e}{e-2}e^{n}\]

Answer 2

my question is what are other ways of finding this...

Answer 3

or names of the ways

Answer 4

by the way that one thing above meant homegenous solution
the whole
\[a_{n_h}\]

Answer 5

i believe ganeshia does it by use of a generating function ... but its all hocus pocus to me

Answer 6

hmmm... that is going to take a little reading
if I figure it out, I will post the way by generating function thingy

maybe I'm not a good googler, but it is hard for me to search what are the ways to find explicit solutions for recurrence relations

Answer 7

pattern recognition if possible?

a{n} -2a{n-1} = e^n

a{n} = 2a{n-1} + e^n
-------------------

a0 = k

a1 = 2k + e^1

a2 = 2(2k+e^1) + e^2
= 4k + 2e^1 + e^2
= 4k + 2e^1 + e^2

a3 = 8k + 4e^1 + 2e^2 + e^3

a4 = 2^4 k + 2^3 e^1 + 2^2 e^2 + 2^1 e^3 + 2^0 e^4

an = 2^n k + (A)

Answer 8

\[A=\sum_{k=1}^n 2^{n-k}e^{k}\]
not sure how thats useful yet

Answer 9

2^3 e * e/2 = 2^2 e^2

2^2 e^2 * e/2 = 2^1 e^3

its a geometric sum isnt it

Answer 10

\[\sum_{n=0}^{\infty} a_n x^{n}=a(x) \\ \text{ so we have } \\ a_n-2 a_{n-1}=e^{n} \\ \text{ multiply } x^{n} \text{ on both sides } \\ a_n x^{n}-2a_{n-1}x^n =e^{n} x^{n} \\ \text{ now...} \\ \sum_{n=1}^{\infty} (a_n x^{n}-2a_{n-1}x^{n})=\sum_{n=1}^{\infty} e^n x^{n} \\ \sum_{n=1}^{\infty} a_n x^{n} - 2 \sum_{n=1}^{\infty} a_{n-1} x^{n} =\sum_{n=1}^{\infty} e^{n} x^{n} \\ \\ a(x)=\sum_{n=0}^{\infty}a_n x^{n} \\ \sum_{n=1}^{\infty} a_n x^{n}=a(x)-a_0=a(x)-\frac{2e-2}{e-2} \\ 2 \sum_{n=1}^{\infty} a_{n-1}x^{n}=2x \sum_{n=1}^{\infty} a_{n-1}x^{n-1}=2x(a(x)-a_0)=2x(a(x)-\frac{2e-2}{e-2}) \\ \]
so we have the equation:
\[a(x)-\frac{2e-2}{e-2}-2x(a(x)-\frac{2e-2}{e-2})= \sum_{n=1}^{\infty}e^{n} x^{n} \\ a(x)(1-2x)-\frac{2e-2}{e-2}+2x \frac{2e-2}{e-2}= \sum_{n=1}^{\infty} e^{n} x^{n}\]
I could go ahead and solve for a(x) but I'm not sure what to do what the sum thingy on the right hand side

Answer 11

would you want to solve the homogenous first? or is that redundant?

Answer 12

for this method I'm not sure yet

Answer 13

so anyways you were trying to do a pattern thingy...

Answer 14

\[a_n-2a_{n-1}=e^{n} \\ a_0=\frac{2e-2}{e-2} \\ a_1-2a_0=e^{1} \\ a_1-\frac{4e-4}{e-2}=e \\ a_1=e+\frac{4e-4}{e-2}=\frac{e(e-2)+4e-4}{e-2}=\frac{e^2+2e-4}{e-2} \\ a_2-2a_1=e^{2} \\ a_2=e^2+\frac{2e^2+4e-8}{e-2}=\frac{e^3-2e^2+2e^2+4e-8}{e-2} \\ a_2=\frac{e^3+4e-8}{e-2} \\ a_3=e^{3}+\frac{2e^3+8e-16}{e-2}=\frac{e^4-2e^3+2e^3+8e-16}{e-2}=\frac{e^4+8e-16}{e-2} \\ \text{hmmm.... } \\ a_n=\frac{e^{n+1}+2^{n}-2^{n+1}}{e-2}\]

Answer 15

one sec checking...

Answer 16

oops missed that e thingy

Answer 17

\[a_n=\frac{e^{n+1}+2^n e-2^{n+1}}{e-2}\]

Answer 18

yep that is the exact same result
the pattern thingy worked well here

Answer 19

usually it is harder to see the pattern

Answer 20

the generating function might be the most applicable :)

Answer 21

I couldn't get that way to work

Answer 22

because I don't know what to do with the sum(x^n*e^n)

Answer 23

actually as n goes to infinity that series diverges

Answer 24

unless x is in (-1/e,1/e)

Answer 25

The recurrence relation \(a_n-la_{n-1} = f(n)\) has the general solution :

\(a_n = l^{n}a_0 + \sum\limits_{i=1}^nl^{n-i}f(n)\)

Answer 26

\[a(x)-\frac{2e-2}{e-2}-2x(a(x)-\frac{2e-2}{e-2})= \sum_{n=1}^{\infty}e^{n} x^{n} \\ a(x)(1-2x)-\frac{2e-2}{e-2}+2x \frac{2e-2}{e-2}= \sum_{n=1}^{\infty} e^{n} x^{n}\]
\[a(x)(1-2x)-\frac{2e-2}{e-2}(1-2x)=-\frac{ex}{ex-1} \\ \text{ where } x \in (\frac{-1}{e},\frac{1}{e}) \\ a(x)=\frac{-ex}{(ex-1)(1-2x)}+\frac{2e-2}{e-2}\]

Answer 27

\[\frac{-ex}{(ex-1)(1-2x)}=\frac{A}{ex-1}+\frac{B}{1-2x} \\ -ex=A-2Ax+Bex-B \\ -ex=A-B+x(-2A+Be) \\ A-B=0 \\ A=B \\ -2B+Be=-e \\ B(-2+e)=-e \\ B=\frac{-e}{-2+e}\]

Answer 28

\[a(x)=\frac{e}{e-2} \cdot \frac{1}{ex-1}+\frac{e}{e-2} \cdot \frac{1}{1-2x}+\frac{2e-2}{e-2}\]

Answer 29

I have to play a little more with this later
I have to go to a thingy with some thingy

Answer 30

I'm a big fan of using GFs whenever possible. Here's a question I answered recently with the method, maybe it'll give you a good idea of how it works?
http://openstudy.com/study#/updates/5600180fe4b0ed58e276f560

Answer 31

Another example I posted to MSE a few weeks ago:
http://math.stackexchange.com/questions/1482664/how-to-solve-these-recurrence-relations-by-using-generating-function/1483774#1483774

Answer 32

I just noticed I made a mistake above:
\[a(x)=\frac{e}{2-e} \cdot \frac{1}{ex-1}+\frac{e}{2-e} \cdot \frac{1}{1-2x}+\frac{2e-2}{e-2} \\ a(x)=\frac{e}{2-e} \cdot \sum_{n=0}^{\infty}-e^nx^n +\frac{e}{2-e} \cdot \sum_{n=0}^{\infty} 2^{n} x^{n} +\frac{2e-2}{e-2} \\ \sum_{n=0}^{\infty} a_n x^{n}=\frac{e}{2-e} \cdot \sum_{n=0}^{\infty} -e^{n} x^n+\frac{e}{2-e} \sum_{n=0}^{\infty} 2^n x^n +\frac{2e-2}{e-2} \\ \text{ somehow this means } \\ a_n=\frac{e}{2-e}(-e^n)+\frac{e}{2-e}2^{n}+\frac{2e-2}{e-2} \\\]
I think I did something wrong
I will go back over it after reading those links you have posted

Answer 33

\[a_n-2 a_{n-1}=e^n \text{ with } a_0=\frac{2e-2}{e-2} \\ \sum_{n=1}^{\infty}(a_n-2 a_{n-1})x_n=\sum_{n=1}^\infty e^{n} x^n \\ \\ \sum_{n=1}^{\infty} (ex)^n \text{ assume } |e x|<1 \implies |x|<\frac{1}{e} \\ \text{ then } \sum_{n=1}^{\infty} (ex)^n=\frac{ex}{1-ex} \\ \text{ Let } a(x)=\sum_{n=0}^{\infty} a_n x^n \\ \sum_{n=1}^{\infty} a_n x^{n}=a(x)-a_0=a(x)-\frac{2e-2}{e-2} \\ -2 \sum_{n=1}^{\infty} a_{n-1}x^{n}= -2 x \sum_{n=1}^{\infty} a_{n-1}x^{n-1}=-2x[ \sum_{k=0}^\infty a_k x^k]=-2x[a(x)]=-2x a(x) \]
so I think I see my mistake...
\[a(x)-\frac{2e-2}{e-2}-2 x a(x)= \frac{ex}{1-ex} \\ a(x)(1-2x)=\frac{ex}{1-ex}+\frac{2e-2}{e-2} \\ \\ a(x)= \frac{ex}{(1-2x)(1-ex)}+\frac{2e-2}{e-2} \cdot \frac{1}{1-2x} \\ a(x)=\frac{e}{2-e} \cdot \frac{1}{1-2x}-\frac{e}{2-e } \cdot \frac{1}{1-ex}+ \cdot \frac{2e-2}{e-2} \cdot \frac{1}{1-2x}\]
\[a(x)=\frac{e}{2-e} \sum_{n=0}^{\infty} 2^n x^n -\frac{e}{2-e} \sum_{n=0}^{\infty} e^n x^n +\frac{2e-2}{e-2} \cdot \sum_{n=0}^{\infty} 2^n x^n \\ a_n=\frac{e}{2-e} 2^{n} -\frac{e}{2-e}( e^n) +\frac{2e-2}{e-2} 2^n \\ a_n =2^n \cdot (\frac{2e-2-e}{e-2})+\frac{e e^n}{e-2 } \\ a_n=2^n + \frac{e^{n+1}}{e-2}\]
got it! definitely made a mistake before..
---partial fraction break down below for that one term:
\[\frac{ex}{(1-2x)(1-ex)}=\frac{A}{1-2x}+\frac{B}{1-ex} \\ ex=(A+B)+x(-Ae-2B) \\ A=-B \\ -Ae-2B=e \\ -Ae+2A=e \\ A=\frac{e}{2-e} \\ B=\frac{-e}{2-e}\]

Answer 34

I would like to see other strategies if there are any others
but I still kinda prefer that homogeneous/particular solution way.

Answer 35

This looks like a scary mess :O

Answer 36

but solving fun scary things make you seem more intimidating and isn't that the whole point