0

I am reading a Gambler's ruin probability question but do not really understand difference equation. So I am reading the link here:https://www.cl.cam.ac.uk/teaching/2003/Probability/prob07.pdf

enter image description here

I understand how to get the two roots of $w_1$ and $w_2$. But I don't understand the below process: enter image description here

What $A_1$ and what $A_2$ are we doing here, and why do we do so?

Also how does the author conclude that the general solution is below: enter image description here

It seems the author is skipping several key reasoning and I just don't follow the steps here..

SayMyNameHeisenberg
  • 517
  • Have you tried substituting back, like the author suggested? – user619894 Jul 19 '20 at 18:17
  • Are we using: $A_1w_1^n+A_1w_1^{n-1}+A_1w_1^{n-2}=0$ and $A_2w_2^n+A_2w_2^{n-1}+A_2w_2^{n-2}=0$? But how does this tell us the general solution... – SayMyNameHeisenberg Jul 19 '20 at 18:27
  • 1
    For a homogeneous recurrence relation like this one, if a solution satisfies it then any constant multiple of that solution will also satisfy it (you can check this yourself). As to why we know we can stop at two guesses that work, there is a theorem of linear difference equations which is analogous to a theorem of linear differential equations which states the order of the equation (in this case the highest difference term that appears) gives us the number of linearly independent solutions we will have. – Ninad Munshi Jul 19 '20 at 18:34
  • so that means if I haven't studied differential equations..then it's pretty hard to understand it... – SayMyNameHeisenberg Jul 19 '20 at 18:44
  • The theorem isn't that hard to understand, provided you know some linear algebra (the proof for the linear difference equations case can be found in your favorite discrete math textbook). Otherwise without linear algebra it is out of reach. – Ninad Munshi Jul 19 '20 at 18:51
  • See my answer at https://math.stackexchange.com/questions/37157/recurrence-relation-linear-second-order-constant-coefficients/3763175#3763175 – Jog Jul 22 '20 at 10:57

0 Answers0