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)?
 A: Another fun way of doing it is by means of a generating function. Define
$$
A(t) = \sum_{n\geq 0} x_nt^n = x_0 + x_1 t + x_2 t^2 + \dots \quad (1)
$$ 
for real $t<1$. Then multiply your recursion formula by $t$ and sum to get
$$
\sum_{n\geq 0} x_{n+1} t^n = \frac{1}{2} \sum_{n\geq 0} x_n t^n + \frac{1}{2} \sum_{n\geq 0} t^n.
$$
Note that the left-hand side can we written as
$$
\frac{1}{t} (\sum_{n\geq 0}x_nt^n - x_0) = \frac{A(t)}{t},
$$
and the right-hand side as
$$
\frac{1}{2}A(t) + \frac{1}{2} \frac{1}{1-t},
$$
where we used the formula for a geometric series. Solving for $A(t)$ is easy and gives us
$$
A(t) = \frac{t}{(1-t)(2-t)}.
$$
Now Taylor expand $A(t)$ around $t=0$ to find
\begin{equation}
A(t) = 0 + \frac{1}{2}t + \frac{3}{4}t^2 + \frac{7}{8}t^3 + \dots + (1-2^{-k})t^k + \dots \quad (2)
\end{equation}
Comparing (1) and (2) we see that indeed $x_k = (1-2^{-k})$.
A: Hint: It's not too difficult to show (by induction if you want) that if $x_{n+1}=ax_n +b$ for all $n \geq 0$ and $a\not=1$, then $$x_n = a^n\left(x_0-\frac{b}{1-a}\right)+\frac{b}{1-a}.$$
Then, in your case $a=\frac{1}{2}=b$. Therefore $x_n= (\frac{1}{2})^n(x_0-1)+1.$
A: 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.
