Probability is given in the form of recurrence relation. How to solve and what is the form of recurrence relation? A player tosses a coin and is to score one point for every head turned up and two points for every tail. He is to play on until his score reaches or passes $n$. If $p_n$ is the chances for attaining exactly $n$, show that, $p_n=\frac 12 \left(p_{n-1}+p_{n-2}\right)$ and hence find the value of $p_n$.
Now the book I'm reading has given the solution of the problem. The first part of the solution is same as How to find the recurrence relation for probability of getting exactly n score during a play?  this. And I have understood that. But for the 2nd part the book reads as follows:-
Let $p_n$ is of the form $p_n=A+Bx^n$, where $A, B$ are constants. Now using $p_n=\frac 12 \left(p_{n-1}+p_{n-2}\right)$ we get $A+Bx^n=\frac 12 [A+Bx^{n-1}+A+Bx^{n-2}]\implies 2x^2-x-1=0 \implies x=-\frac 12, 1$.
Since $p_n$ depends on $n$ so $x\neq 1$.So $p_n=A+B \left(-\frac 12 \right) ^n$. Then using given conditions they show that $p_n=\frac 13 [2+(-1)^n.2^{-n}]$.
But I can't understand why they assume that "$p_n$ is of the form $p_n=A+Bx^n$". Why they can consider $p_n$ in the form of this polynomial?
 A: This is a difference equation. Admittedly I am no expert in difference equations, but I can relate them to differential equations, which hopefully you are more familiar with.
Let $p(t)$ be some continuous (twice-differentiable) function such that $p_n = p(n)$. We customarily make the following approximations
$$\frac{dp}{dt} \approx \frac{p_n - p_{n-1}}{n-(n-1)} = p_n - p_{n-1}$$
$$\frac{d^2p}{dt^2} = \frac{d}{dt}\frac{dp}{dt}  \approx (p_n - p_{n-1}) - (p_{n-1} - p_{n-2}) = p_n - 2p_{n-1} + p_{n-2}$$
And the given equation is $2p_n - p_{n-1} - p_{n-2} = 0$, solving the linear combination problem $2p_n - p_{n-1} - p_{n-2} = a(p_n - p_{n-1}) + b(p_n - 2p_{n-1} + p_{n-2})$ we obtain $a = 3, b = -1$ and the following related differential equation
$$\frac{d^2p}{dt^2} - 3\frac{dp}{dt} = 0 \implies p = c_1 + c_2e^{3t}$$
Our original difference equation is not quite this but quite similar. They are different because the slope of the secant line from $(t, p(t)$ to $(t+1, p(t+1))$ is a poor approximation of $p'(t)$, but the form $A + Bx^n$ is there.
A side note is that because $n$ is the parameter, $x^n$ is actually an exponential expression. $p$ is a "function" of $n$, not $x$.
