Simple difference equation I have the following difference equation:
$B(n) = \phi (B(n-1) )+ 1$, with a boundary that $B(0) = 0$.
I can see that: $B(1) = 1$, $B(2) = 1+\phi$, $B(3) = \phi (1+\phi) + 1$. So the general solution should be: $B(n) = \frac{1-\phi^n}{1-\phi}$
However, I don't seem to be able to figure out how to analytically get the solution to $B(n)$. The solution above was a guess and verify solution.
 A: The general solution to $B_n = k B_{n−1} + a$ where $k \ne 1$ is $B_n = Ak^n - \dfrac{a}{k-1}$, where $A$ is a constant determined by boundary condition.
In your case, $k = \phi, a=1$ and the general solution is $B_n=A\phi^n - \dfrac{1}{\phi-1}$.
You have $B_0 = A\phi^0-\dfrac{1}{\phi-1} = A-\dfrac{1}{\phi-1} = 0$, so $A=\dfrac{1}{\phi-1}$ and $$B_n = \left(\dfrac{1}{\phi-1}\right)\phi^n-\dfrac{1}{\phi-1} = \dfrac{\phi^n-1}{\phi-1}~~~\text{ or}~~~ \dfrac{1-\phi^n}{1-\phi}$$
So, where did this magic solution $B_n = Ak^n - \dfrac{a}{k-1}$ come from? It's very sneaky: we take our original recurrence $B_n = k B_{n−1} + a$ and add $\dfrac{a}{k-1}$ to each side to get: $$\begin{array}{rcl}B_n +\dfrac{a}{k-1}&=& k B_{n−1} + a + \dfrac{a}{k-1}\\&=&kB_{n-1}+\dfrac{ak-a+a}{k-1}\\&=&kB_{n-1}+\dfrac{ak}{k-1}\\&=&k\left(B_{n-1}+\dfrac{a}{k-1}\right)\end{array}$$
Which is a recurrence $Y_n=kY_{n-1}$ where $Y_n=B_n+\dfrac{a}{k-1}$. We can solve the recurrence in $Y_n$ to get $Y_n=Ak^n$ for some $A$, then substitute back to get $B_n=Y_n-\dfrac{a}{k-1}=Ak^n-\dfrac{a}{k-1}$.
And where does $\dfrac{a}{k-1}$ come from? It's the equilibrium solution to the recurrence. If we imagine getting successive identical values in the sequence, then the sequence would be stuck on $B_{eq}=kB_{eq}+a$, or $B_{eq} = \dfrac{a}{k-1}$. Equilibrium solutions are important in solving mathematical models.
