$F(x) = .5 F(x+1) + .5F(x-1)$.. How to solve I saw this in an mit open courseware video for approximating the probability of Reaching one value versus another in a coin flip game.
For example, if $f(10) = 1$ and $f(-5)=0$  what is $f(0)$ (you earn a dollar on each coin flip of heads, lose a dollar on tails.  Game is over at $10$ dollars won or $5$ dollars lost.  What is probability of winning?)
In other words, if $f(a)=1$ and $f(-b)=0$, the solution is $b/a+b$. However, I don't understand how he arrived at that.  I can do recurrence relations, but this one is infinitely recursive when I write it out.  Any tips?
 A: Note that $f(x+1)-f(x)=f(x)-f(x-1)$
Then
$f(a)-f(a-1)=k$
$f(a-1)-f(a-2)=k$
$...$
$f(-b+1)-f(-b)=k$
Add them up,
$f(a)-f(-b)=(a+b)k=1\implies k=\large{1\over a+b}\implies f(0)=f(-b)+k\cdot b=0+\large{b\over a+b}$
A: Multiply by $2$ and rewrite it as $f(n+1)=2f(n)-f(n-1)$. This homogeneous linear recurrence with constant coefficients has the characteristic equation $x^2=2x-1$, i.e., $x^2-2x+1=0$, which is $(x-1)^2=0$. Since both roots are $1$, by a standard theorem the general solution to the recurrence is 
$$f(n)=A(1)^n+Bn(1)^n=A+Bn\;,\tag{1}$$
where $A$ and $B$ depend on the initial values, or in fact on any pair of values.
Suppose that $f(a)=1$ and $f(-b)=0$, where $a,b>0$. Then $(1)$ says that $A+Ba=1$ and $A-Bb=0$, and we have a system of two linear equations in the unknowns $A$ and $B$. Multiply the first by $b$ and the second by $a$ and add, and you find that $A(a+b)=b$, so $A=\frac{b}{a+b}$. Substitute that into the second equation to find that
$$B=\frac{A}b=\frac1{a+b}\;.$$
Thus, 
$$f(n)=\frac{b}{a+b}+\frac{n}{a+b}=\frac{n+b}{a+b}\;,$$
and 
$$f(0)=\frac{b}{a+b}\;.$$
Added: For a more elementary analysis, notice that original recurrence can be written
$$f(n)=\frac{f(n+1)+f(n-1)}2\;,$$
meaning that each term of the sequence is the arithmetic mean of the neighboring terms. This is possible precisely when the gaps between adjacent terms are equal:
$$f(n+1)-f(n)=f(n)-f(n-1)\;.$$
That in turn says that the sequence must be an arithmetic sequence, so it must satisfy $f(n)=A+Bn$ for some constants $A$ and $B$. Now you can use the known values of $f(a)$ and $f(-b)$ to find $A$ and $B$ just as I did above.
A: For reasonable $n$, we have $f(n+1)=2f(n)-f(n-1)$. Now we compute.
Let $f(-4)=k$. Then $f(-3)=2f(-4)-f(-5)=2k$. But $f(-2)=2f(-3)-f(-4)=3k$. But $f(-1)=2f(-2)-f(-3)=4k$. But $f(0)=2f(-1)-f(-2)=5k$. 
And so on. We get $f(1)=6k$, $f(2)=7k$, and so on up to $f(10)=15k$.
This is equal to $1$, so $k=\frac{1}{15}$. But $f(0)=5k=\frac{5}{15}$.
