# How do I solve this difference equation?

For a sequence $\{D_k\}$, if we have: $$D_k=pD_{k+1}+qD_{k-1}+1$$

and we know that $D_0=D_N=0$. Where $p+q=1$, and $N$ is known. How do I solve it?

-
Here is a related problem. – Mhenni Benghorbal Nov 4 '12 at 19:02
I would use a generating function: Let $d(x) = \sum x^k D_k$, apply the recurrence and end conditions, and see what happens. – marty cohen Nov 4 '12 at 20:17

First assume $p \neq q$. Define $E_k = D_k + \frac{k}{p - q}$. Then $E$ satisfies the linear recursion

$$E_k = p E_{k+1} + q E_{k - 1}.$$

A solution of this recursion is of the form $E_k = \alpha \left(\frac{q}{p}\right)^k + \beta$ for constants $\alpha, \beta$. Using that $D_0 = D_N = 0$ this results in

$$D_k = \frac{N}{p - q} \cdot \frac{\left(\frac{q}{p}\right)^k - 1}{\left(\frac{q}{p}\right)^N - 1} - \frac{k}{p-q}.$$

If $p = q = \tfrac{1}{2}$ then define $E_k = D_k + k^2$ which satisfies the recursion

$$E_k = \tfrac{1}{2} E_{k+1} + \tfrac{1}{2} E_{k-1}.$$

Now a solution is of the form $E_k =\alpha \, k + \beta$. In this case we find

$$D_k = k \, (N - k).$$

-