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?
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?
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). $