[proofplan] We solve the second-order linear recurrence $r_a = p\,r_{a+1} + q\,r_{a-1}$ with boundary conditions $r_0 = 1$, $r_N = 0$. The recurrence is rewritten as a homogeneous linear equation whose characteristic equation has roots $1$ and $q/p$. When $p \ne q$ these roots are distinct, giving the general solution as a linear combination $r_a = A + B(q/p)^a$. When $p = q = 1/2$ there is a repeated root and the general solution is $r_a = A + Ba$. In both cases, the boundary conditions determine $A$ and $B$. [/proofplan] [step:Rewrite the recurrence as a homogeneous linear equation and find the characteristic roots] The recurrence $r_a = p\,r_{a+1} + q\,r_{a-1}$ can be rearranged using $p + q = 1$: \begin{align*} p\,r_{a+1} - (p + q)\,r_a + q\,r_{a-1} &= 0 \\ p(r_{a+1} - r_a) - q(r_a - r_{a-1}) &= 0. \end{align*} This is a second-order linear recurrence with constant coefficients. Substituting the trial solution $r_a = \lambda^a$ gives the characteristic equation \begin{align*} p\lambda^2 - (p + q)\lambda + q = 0 \implies p\lambda^2 - \lambda + q = 0. \end{align*} Factoring: $p\lambda^2 - \lambda + q = p(\lambda - 1)(\lambda - q/p)$ (verified by expanding and using $p + q = 1$). The characteristic roots are $\lambda_1 = 1$ and $\lambda_2 = q/p$. [guided] Why rewrite $r_a = p\,r_{a+1} + q\,r_{a-1}$ in the form $p(r_{a+1} - r_a) = q(r_a - r_{a-1})$? This reveals the structure: the recurrence says that the "forward difference" $r_{a+1} - r_a$, weighted by $p$, equals the "backward difference" $r_a - r_{a-1}$, weighted by $q$. If we define $d_a = r_{a+1} - r_a$, then the recurrence becomes $p\,d_a = q\,d_{a-1}$, or $d_a = (q/p)\,d_{a-1}$. This is a first-order recurrence for the differences, with solution $d_a = (q/p)^a \cdot d_0$. To find the characteristic roots more systematically, substitute $r_a = \lambda^a$: $p\lambda^{a+1} - \lambda^a + q\lambda^{a-1} = 0$. Dividing by $\lambda^{a-1}$ (assuming $\lambda \ne 0$): $p\lambda^2 - \lambda + q = 0$. The discriminant is $1 - 4pq = (p + q)^2 - 4pq = (p - q)^2 \ge 0$, so both roots are real. The roots are \begin{align*} \lambda = \frac{1 \pm \sqrt{(p-q)^2}}{2p} = \frac{1 \pm |p - q|}{2p}. \end{align*} When $p \ne q$, the two roots are $\lambda_1 = \frac{1 + (p-q)}{2p} = 1$ and $\lambda_2 = \frac{1 - (p-q)}{2p} = \frac{2q}{2p} = q/p$ (assuming $p > q$; the case $p < q$ is symmetric). When $p = q = 1/2$, both roots equal $1$ (a repeated root). [/guided] [/step] [step:Solve the biased case $p \ne q$ using the boundary conditions] When $p \ne q$, the roots $1$ and $q/p$ are distinct, so the general solution is \begin{align*} r_a = A \cdot 1^a + B \cdot (q/p)^a = A + B(q/p)^a. \end{align*} Applying the boundary conditions: \begin{align*} r_0 &= A + B = 1, \\ r_N &= A + B(q/p)^N = 0. \end{align*} Subtracting: $B(q/p)^N - B = -(A + B(q/p)^N) + (A + B) = 0 - 1 = -1$. That is, $B((q/p)^N - 1) = -1$, so $B = \frac{-1}{(q/p)^N - 1} = \frac{1}{1 - (q/p)^N}$. From $A = 1 - B$: \begin{align*} A = 1 - \frac{1}{1 - (q/p)^N} = \frac{1 - (q/p)^N - 1}{1 - (q/p)^N} = \frac{-(q/p)^N}{1 - (q/p)^N}. \end{align*} Therefore \begin{align*} r_a &= \frac{-(q/p)^N}{1 - (q/p)^N} + \frac{(q/p)^a}{1 - (q/p)^N} = \frac{(q/p)^a - (q/p)^N}{1 - (q/p)^N}. \end{align*} [/step] [step:Solve the fair case $p = q = 1/2$ using the repeated-root solution] When $p = q = 1/2$, the characteristic equation has a repeated root $\lambda = 1$. The general solution for a second-order recurrence with a repeated root $\lambda = 1$ is $r_a = A + Ba$ (the two linearly independent solutions are $1^a = 1$ and $a \cdot 1^a = a$). Applying the boundary conditions: \begin{align*} r_0 &= A = 1, \\ r_N &= A + BN = 1 + BN = 0, \end{align*} so $B = -1/N$. Therefore $r_a = 1 - a/N$. [/step]