Weird 'undefined behaviour' on recurrence formula The problem: You play a game, where you start with two coins. Every round, you bet a coin. You have a 1/4 chance of losing your coin and a 3/4 chance of winning a new coin. So, if you have 3 coins, you can end the round with 2 or 4 coins. You play the game, either forever or until you go bankrupt. What is the probability you go bankrupt?
The idea: define $f(i)$ the probability you go bankrupt, given that you have i coins. Obviously, 
f(0)=1. 

Also, 
f(i) = 1/4*f(i-1) + 3/4*f(i+1)

(This second equation means that playing with $i$ coins, you have 1/4 chance of "reducing" your game to the $i-1$ case and 3/4 of "reducing" your game to the $i+1$ case)
The weirdness: These two equations seem to capture all of the problem. However, they have an infinite number of solutions. To see that, notice that the second equation just means $f(i)-f(i-1) = 3(f(i+1) - f(i))$. We can, therefore, choose $f(1)$ freely (as long as it is smaller or equal 1, and sufficiently large that it does not "force" any subsequent $f(i)$ term to be smaller than 0).
The question: What is going on??
 A: The key is to consider a finite version of this question, the Classical Ruin Problem.

Consider the familiar gambler who wins or loses a dollar with probabilities $p$ $[=3/4]$ and $q$ $[=1/4]$, respectively.  Let his initial capital be $z$ and let him play against an adversary with initial capital $a-z$, so that the combined capital is $a$.  The game continues until the gambler's capital either is reduced to zero or has increased to $a$.  We are interested in the probability of the gambler's ruin [that is, $z \le 0$] and the probability distribution of the duration of the game.

[Feller, XIV.2]
Feller's analysis begins with the recursion and initial conditions in the question here, understanding $z$ and $a$ to be integral.  Letting $f(n)$ be the chance the gambler ultimately is ruined when $0\le n\le a$,
$$f(n) = p f(n+1) + q f(n-1)\tag{1}$$
and
$$f(0) = 1;\ f(a)=0.$$
The second boundary condition $f(a)=0$ is new, but is obvious from the rules of this finite game.  With it we obtain a unique solution to this difference equation,
$$f(n) = \frac{(q/p)^n - (q/p)^a}{1 - (q/p)^a};\ n=0, 1, \ldots, a,\tag{2}$$
provided $p\ne q$.
The game against an opponent with arbitrary capital is analyzed by allowing $a$ to be an arbitrarily large whole number.  From $(2)$ it is clear that for any fixed $n \gt 0$, $f(n)$ approaches $(q/p)^n$ as $a$ grows.  Consequently, for all integral $n \ge 0$, the chance of ruin must be $$f(n)=(q/p)^n.$$ With the chances given in the question, this is $((1/4) / (3/4))^n=3^{-n}$.
Reference
William Feller, An Introduction to Probability Theory and Its Applications.  Volume I.  Third Edition, John Wiley & Sons, 1968: Chapter XIV.

Addendum: The Symmetric Random Walk
When $p=q$ then both equal $1/2$: wins and losses are equally likely.  The course of the game is a Symmetric Random Walk.  In this case formula $(2)$ is undefined.  To obtain a solution, return to the recurrence $(1)$, which can be written
$$\Delta(f)(n-1) = f(n) - f(n-1) = f(n+1) - f(n) = \Delta(f)(n).$$
That is, the first differences $\Delta(f)(n)$ are constant for $0\le n \lt a$.  That easily implies $f$ is a linear function of $n$ within this domain.  The unique such function connecting the point $(0,1)$ to $(a,0)$ is
$$f(n) = \frac{a-n}{a} = 1 - \frac{n}{a}.$$
The second expression makes it clear that for any $n\ge 0$, $f(n)$ approaches $1$ as $a$ grows arbitrarily large.  In the Symmetric Random Walk, the chance of ruin is $1$ regardless of how much capital the gambler begins with.
