Recurrence equation with upper and lower boundary condition

Question

A very natural set up for recurrence equations is the following: $$ s(0) = 0 $$ $$ s(k) = A \ s(k-1) + B $$ $$ s(M) = A \ s(M-1), $$ where $0 \le A,B \le 1$ and $0 < k < M$. We can omit the third equation to find that for $k = 0, 1, \dots, M-2$ \begin{align*} s(k+1) &= A^{k+1}s(0) + \sum_{i=0}^k A^i B \\ &=B \ \sum_{i=0}^k A^i \\ &= B \frac{1-A^{k+1}}{1-A}. \end{align*} However, how can we impose now the condition $s(M) = A \ s(M-1)$?

Answer 1

The recurrence you have is of the first order, so you can only impose one condition. I.e., either fix $s(0)$, or state the restriction on $s(M)$.