Finding a formula for a kth element in a sequence I've setup a recurrence relation as part of a numerical analysis problem, and found that $$x_{n+1} = \frac{x_n+1}{2}$$
The notes then say that for $x_0=0$, it is easy to show that $$x_k = 1 - 2^{-k}$$
Plugging in a few numbers shows this is clearly correct, and equating $x_{n+1}=x_n$ shows it converges to one - but how might one come up with $x_k$ formula in the first place (rather than just being able to verify it)?

Here's one possible process for discovering the general formula: try applying the recurrence a few times:
$$
\begin{aligned}
x_1&=\frac{x_0+1}{2}=\frac{x_0}{2}+\frac{1}{2}\\
x_2&=\frac{x_1+1}{2}=\frac{x_1}{2}+\frac{1}{2}=\frac{x_0}{4}+\frac{1}{4}+\frac{1}{2}=\frac{x_0}{4}+\frac{3}{4}\\
x_3&=\frac{x_2+1}{2}=\frac{x_2}{2}+\frac{1}{2}=\frac{x_0}{8}+\frac{3}{8}+\frac{1}{2}=\frac{x_0}{8}+\frac{7}{8}\\
x_4&=\frac{x_3+1}{2}=\frac{x_3}{2}+\frac{1}{2}=\frac{x_0}{16}+\frac{7}{16}+\frac{1}{2}=\frac{x_0}{16}+\frac{15}{16}.
\end{aligned}
$$
The pattern is pretty clear—you're getting $x_n=\frac{x_0}{2^n}+\frac{2^n-1}{2^n}$—but you can also see why it's happening: every time you apply the recurrence, $x_0$ gets multiplied by $\frac{1}{2}$ one more time, while the constant becomes $\frac{1}{2}$ plus $\frac{1}{2}$ times the previous constant.  So the constant in $x_2$ is $\frac{1}{2}+\frac{1}{2}\cdot\frac{1}{2}$, the constant in $x_3$ is $\frac{1}{2}+\frac{1}{2}\cdot\frac{1}{2}+\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2}$, and so on.  You may recognize the constant as a geometric series:
$$
\sum_{i=1}^n\left(\frac{1}{2}\right)^i=\frac{\frac{1}{2}-\left(\frac{1}{2}\right)^{n+1}}{1-\frac{1}{2}}=1-\left(\frac{1}{2}\right)^n,
$$
from which the formula we observed follows.
