The origin of the solution space of a recurrence relation

Question

Let's play a simple game. You start out with 10 missiles, and each turn you flip 2 coins.
The possible outcomes of the coin flips are:
- One head and one tail is a loss and your missile count goes down by one.
- Two tails is a tie and your missile count stays the same.
- Two heads is a win and your missile count goes up by one.
What is the expected number of times you get to flip the coins until you run out of missiles?
The answer can be described by the recurrence relation:
$$ f(n) = \frac{1}4 [1 + f(n+1)] + \frac{1}4[1 + f(n)] + \frac{1}2[1 + f(n-1)]$$ whose general solution is: $$ f(n) = c_{1} + c_{2}2 ^n + 4n $$ But, since I only have one initial condition, $f(0) = 0$, I can't solve for $c_{1}$ and $c_{2}$. Running a simulation of the game revealed that the answer I'm looking for is: $f(n) = 4n$, which happens to be the solution of the recurrence when $c_{1}=c_{2}=0$. In other words, the solution to my question is the origin of the vector space of solutions to $f(n)$. In a sense, we've ignored the homogenous solution and only kept the particular solution. Why is this? What a priori justification could I have had, to know that the origin of the solution space would be the specific point I needed?

Answer 1

First, it is incorrect to refer to $4n$ as "the" particular solution. It may be the one you found and is the simplest because it has fewer terms than the other solutions, but if somebody had claimed that the particular solution was $5+3\cdot 2^n + 4n$ you could not prove them wrong.

We can argue from the problem that $c_2$ must be $0$. If it were not, for large $n$ we would have $f(n)$ doubling at each step, but we know that the expectation is linearly downward $\frac 14$ step per turn. Once you make that argument, you can use $f(n)=0$ to evaluate $c_1$ and you are done. If you were just given the recurrence, you would need two values of $f(n)$ to evaluate the two constants.