Recurrence relation - $f(0) = 0$, $f(n+1) = f(n) + \frac{1}{2^n}$

Question

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?

Answer 1

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.

Answer 2

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}. $$

Answer 3

$$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.

Answer 4

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} $$

Answer 5

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}.$$

Answer 6

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}