Relación de recurrencia - $f(0) = 0$ , $f(n+1) = f(n) + \frac{1}{2^n}$

Question

Quería resolver la siguiente relación de recurrencia: $$f(0) = 0$$ $$f(n+1) = f(n) + \frac{1}{2^n}$$

Mirando algunos valores que se me ocurrieron: $$f(n) = 2 - 2^{1-n}$$ que podría demostrar por inducción matemática.

Pero, ¿hay alguna manera de resolver esto sin adivinar y luego demostrar por inducción?

Answer 1

Se puede observar que la relación de recurrencia se reescribe como \begin{equation} \underbrace{2^{n+1} f(n+1)}_{u_{n+1}} = 2\, \underbrace{2^n f(n)}_{u_{n}} + 2 \, , \end{equation} que tiene la forma de una recursión afín con $n$ El término \begin{equation} u_n = 2^n (u_0 + 2) - 2 \, . \end{equation} Por lo tanto, \begin{equation} f(n) = 2 - 2^{1-n} \, . \end{equation}