Recurrence relation - $f(0) = 0$, $f(n+1) = f(n) + \frac{1}{2^n}$ I wanted to solve the following recurrence relation:
$$f(0) = 0$$
$$f(n+1) = f(n) + \frac{1}{2^n}$$
By looking at a few values I came up with: $$f(n) = 2 - 2^{1-n}$$
which I could prove by mathematical induction.
But is there a way to solve this without guessing and then proving by induction?
 A: You have $f(n)-f(n-1)=\dfrac1{2^{n-1}}$ for $n\ge 1$, so
$$\begin{align*}
\sum_{k=1}^n\big(f(n)-f(n-1)\big)&=\sum_{k=1}^n\frac1{2^{k-1}}\\
&=\sum_{k=0}^{n-1}\frac1{2^k}\\
&=\sum_{k=0}^{n-1}\left(\frac12\right)^k\\
&=\frac{1-\left(\frac12\right)^n}{1-\frac12}\\
&=2-\frac1{2^{n-1}}\;.
\end{align*}$$
But the initial sum telescopes:
$$\begin{align*}
\sum_{k=1}^n\big(f(n)-f(n-1)\big)&=\sum_{k=1}^nf(n)-\sum_{k=1}^nf(n-1)\\
&=\sum_{k=1}^nf(n)-\sum_{k=0}^{n-1}f(n)\\
&=f(n)-f(0)\\
&=f(n)\;.
\end{align*}$$
Thus, $f(n)=2-\dfrac1{2^{n-1}}$.
This is really just a rigorous way to show that $f(n)$ is the sum of the fractions $\frac1{2^k}$ for $0\le k<n$, something that is fairly apparent from the recurrence itself.
A: The recurrence relation
$$
a_{n+1} = a_n + 1/2^n
$$
is inhomogeneous, so we homogenize first: Taking a look at the next element gives
$$
a_{n+2} = a_{n+1} + 1/2^{n+1} \\
$$
While the trailing terms are not constant, we are lucky here, we can make them the same: we have
$$
2 a_{n+2} - a_{n+1} = 2 a_{n+1} + 1/2^n - a_n - 1/2^n =2 a_{n+1} - a_n \iff \\
a_n = (3/2) a_{n-1} - (1/2) a_{n-2}
$$
For this homogeneous recurrence relation with constant coefficients we can perform the usual algorithm. We get the characteristic polynomial
$$
p(t) = t^2 - (3/2) t + (1/2)
$$
with roots 
$$
r_{1,2} \in \{ 1/2, 1\}
$$
and general solution
$$
a_n = k_1 (1/2)^n + k_2 1^n = k_1/2^n + k_2
$$
From $a_0 = 0$ and $a_1 = 1$ we get
$$
0 = k_1 + k_2 \\
1 = k_1/2 + k_2
$$
so we have $-1 = k_1/2 \iff k_1 = -2$ and $k_2 = 2$. This gives
$$
a_n = 2 - 1/2^{n-1}
$$
A: One may write
$$
f(k+1)- f(k) = \frac{1}{2^k},\quad k=0,1,2\cdots,
$$ then recognize a telescoping sum
$$
\sum_{k=1}^n\left(f(k+1)- f(k)\right)=f(n+1)-f(1)
$$ and recognize a geometric sum
$$
\sum_{k=1}^n \frac{1}{2^k}=\frac12\frac{1-\frac1{2^{n}}}{1-\frac1{2}}=1-2^{-n}.
$$
A: $$f(1)=0+\frac{1}{2^0}$$
$$f(2)=f(1)+\frac{1}{2^1}$$
.
.
$$f(n)=f(n-1)+\frac{1}{2^{n-1}}$$
thus, by addition
$$f(n)=\sum_{k=0}^{n-1}\frac{1}{2^k}$$
$=2(1-2^{-n}) \; $ as a geometric sum.
For $n=0$, this formula is true.
Let $n\geq 0$ such that $f(n)=2(1-2^{-n})$.
then
$$f(n+1)=f(n)+\frac{1}{2^n}$$
$$=2-2\frac{1}{2^n}+\frac{1}{2^n}$$
$$=2-\frac{1}{2^n}$$
$$=2(1-2^{-n-1}).$$
qed.
A: Here is an alternative approach, which is not as quick as @Biran M. Scotts answer :).
Multiply the recurrence equation with $x^n$ and sum from $n=0$ to $n=\infty$ (dont care about convergence).
$$\sum_{n=0}^{\infty}f(n+1)x^n=\sum_{n=0}^{\infty}f(n)x^n+\sum_{n=0}^{\infty}1/2^nx^n$$ 
$$\frac{1}{x}\sum_{n=0}^{\infty}f(n+1)x^{n+1}=\sum_{n=0}^{\infty}f(n)x^n+\sum_{n=0}^{\infty}1/2^nx^n$$ 
$$\frac{1}{x}\left(\sum_{n=0}^{\infty}f(n)x^{n}-f(0)x^0\right)=\sum_{n=0}^{\infty}f(n)x^n+\sum_{n=0}^{\infty}1/2^nx^n$$ 
Now, use $f(0)=0$, use the infinite geometric series
$$\sum_{n=0}^{\infty}1/2^nx^n=\sum_{n=0}^{\infty}(x/2)^n=\frac{1}{1-x/2}$$
and bring both sums with $f(n)x^n$ and to the left side:
$$(1/x-1)\sum_{n=0}^{\infty}f(n)x^{n}=\frac{1}{1-x/2}.$$
This is the same as
$$\sum_{n=0}^{\infty}f(n)x^{n}=\frac{1}{(1-x/2)(1/x-1)}=2x\left[ \frac{1}{1-x}-\frac{1}{2}\frac{1}{1-x/2}\right].$$
Now, use the geometric series for the fractions on the right hand side:
$$\sum_{n=0}^{\infty}f(n)x^{n}=\sum_{n=0}^{\infty}(2-1/2^n)x^{n+1}.$$
Note, that the first sum is equal to $\sum_{n=0}f(n+1)x^{n+1}$, because $f(0)=0$. Using this observation and comparing the coefficients of both sums we obtain:
$$f(n+1)=2-1/2^n.$$
After the substitution $n \to n-1$, we obtain:
$$f(n)=2-1/2^{n-1}.$$
A: One can remark that the recurrence relation rewrites as
\begin{equation}
\underbrace{2^{n+1} f(n+1)}_{u_{n+1}} = 2\, \underbrace{2^n f(n)}_{u_{n}} + 2 \, ,
\end{equation}
which has the form of an affine recursion with $n$th term
\begin{equation}
u_n = 2^n (u_0 + 2) - 2 \, .
\end{equation}
Therefore,
\begin{equation}
f(n) = 2 - 2^{1-n} \, .
\end{equation}
