Techniques for solving a difference recurrence relations

Question

I’m having issues understanding how an answer is derived in a math textbook I have. Just looking for a technique for the derivation as well as some intuition to help with my understanding.

The original recursion is:

$g(k) = pg(k+1) + qg(k-1) + 1 $

Rearranging the equation we can put it in difference form:

$ g(k+1) - g(k) = \frac{q}{p}g(k-1) - \frac{1}{p} \implies \Delta g(k) = \frac{q}{p} \Delta g(k-1) - \frac{1}{p} $

From here you can use the characteristic equation to solve for homogenous and inhomogenous:

$\Delta g(k) = \alpha + (\frac{q}{p})^k \beta $

For some reason my book lists the equations as

$ g(k) = \frac{k}{q - p} + \alpha + \beta (\frac{q}{p})^k $

I don’t really understand where the $\frac{k}{q - p} $ comes from.

Any intuition or techniques to solve this would be very helpful.

Thanks!

Edit: Yes. P and q are probability and p+ q = 1. I didn’t explicitly state it, a mistake on my part.

Answer 1

I'm adding another method of solving this problem based on the fact that the OP introduced the difference form of the equation. In this answer I'll carry out the entire solution from the difference form. Thus, we begin with

$$ \begin{align} &g(k+1) = \frac{1}{p} g(k) - \frac{q}{p}g(k-1) - \frac{1}{p}\\ &g(k+1)-g(k)=\bigg(\frac{1}{p}-1\bigg) g(k) - \frac{q}{p}g(k-1) - \frac{1}{p}\\ &g(k+1)-g(k)=\frac{q}{p}\big(g(k)-g(k-1)\big) - \frac{1}{p}\\ &\Delta g(k) = \frac{q}{p} \Delta g(k-1) - \frac{1}{p} \end{align} $$

What we have done here is to reduce the order of the recurrence by one. Applying the standard methods for non-homogeneous recurrence of the first order we have determined that

$$ \Delta g(k) = \bigg[\Delta g(0)-\frac{1}{q-p}\bigg]\bigg(\frac{q}{p} \bigg)^k +\frac{1}{q-p} $$

So now we can write

$$ \begin{align} &g(1)-g(0) = \bigg[\Delta g(0)-\frac{1}{q-p}\bigg]\bigg(\frac{q}{p} \bigg)^0 +\frac{1}{q-p}\\ &g(2)-g(1) = \bigg[\Delta g(0)-\frac{1}{q-p}\bigg]\bigg(\frac{q}{p} \bigg)^1 +\frac{1}{q-p}\\ &g(3)-g(2) = \bigg[\Delta g(0)-\frac{1}{q-p}\bigg]\bigg(\frac{q}{p} \bigg)^2 +\frac{1}{q-p}\\ &\vdots\\ &g(k)-g(k-1) = \bigg[\Delta g(0)-\frac{1}{q-p}\bigg]\bigg(\frac{q}{p} \bigg)^{k-1} +\frac{1}{q-p}\\ \end{align} $$

We now sum these equations to find that

$$ g(k)-g(0)=\bigg[\Delta g(0)-\frac{1}{q-p}\bigg]\sum_{j=0}^{k-1}\bigg(\frac{q}{p} \bigg)^j+\frac{k}{q-p}\\ $$

And noting that

$$ \sum_{j=0}^{k-1}a^j=\frac{a^k-1}{a-1} $$

we finally have

$$ g(k)=g(0)+\bigg[g(1)-g(0)-\frac{1}{q-p}\bigg]\frac{\big(\frac{q}{r}\big)^k-1}{\big(\frac{q}{r}\big)-1}+\frac{k}{q-p}\\ $$

This is somewhat more complicated than the other solution I presented, but I have verified both solutions numerically compared with the recurrence relation. You may also be surprised to learn that any of the parameters, i.e., $[p,q,g(0),g(1)]$ can be complex, provided that $p+q=1$, of course.

Answer 2

You seem to have taken a shortcut and lost the non-homogeneous solution. Let's take step back and see how that evolves. Let's first write the recurrence to be solved as

$$ g(k)=\frac{1}{p}g(k-1)-\frac{q}{p}g(k-2)-\frac{1}{p} $$

For a problem like this you would usually assume a solution of the form $g(k)=f(k)+A$. However in this case you would find that $A=\frac{1}{1-p-q}$ and so cannot be determined since $p+q=1$. This indicates that you should increase the order of the polynomial by one and try instead $g(k)=f(k)+Ak$. The object here is to separate out the homogeneous equation $f(k)$ by setting all the $A$-terms to zero. Thus we end up with,

$$ f(k)=\frac{1}{p}f(k-1)-\frac{q}{p}f(k-2)\\ A\cdot k=\frac{1}{p}A\cdot(k-1)-\frac{q}{p}A\cdot(k-2)-\frac{1}{p} $$

From here you can readily determine that the $k$-terms cancel each other and that you are left with

$$ A=\frac{1}{q-p} $$

You apparently know how to calculate the characteristic roots of the solution to be $(1,q/p)$ and can thus complete the solution.