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

Usted tiene $f(n)-f(n-1)=\dfrac1{2^{n-1}}$ para $n\ge 1$ Así que

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

Pero la suma inicial es telescópica:

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

Así, $f(n)=2-\dfrac1{2^{n-1}}$ .

Esto es realmente una forma rigurosa de mostrar que $f(n)$ es la suma de las fracciones $\frac1{2^k}$ para $0\le k<n$ algo que es bastante evidente por la propia recurrencia.

Answer 2

La relación de recurrencia $$ a_{n+1} = a_n + 1/2^n $$ es inhomogénea, por lo que primero homogeneizamos: Si miramos el siguiente elemento obtenemos $$ a_{n+2} = a_{n+1} + 1/2^{n+1} \\ $$ Aunque los términos finales no son constantes, aquí tenemos suerte, podemos hacerlos iguales: tenemos $$ 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} $$ Para esta relación de recurrencia homogénea con coeficientes constantes podemos realizar el algoritmo habitual . Obtenemos el polinomio característico $$ p(t) = t^2 - (3/2) t + (1/2) $$ con raíces $$ r_{1,2} \in \{ 1/2, 1\} $$ y solución general $$ a_n = k_1 (1/2)^n + k_2 1^n = k_1/2^n + k_2 $$ Desde $a_0 = 0$ y $a_1 = 1$ obtenemos $$ 0 = k_1 + k_2 \\ 1 = k_1/2 + k_2 $$ por lo que tenemos $-1 = k_1/2 \iff k_1 = -2$ y $k_2 = 2$ . Esto da $$ a_n = 2 - 1/2^{n-1} $$

Answer 3

Se puede escribir $$ f(k+1)- f(k) = \frac{1}{2^k},\quad k=0,1,2\cdots, $$ entonces reconoce un suma telescópica $$ \sum_{k=1}^n\left(f(k+1)- f(k)\right)=f(n+1)-f(1) $$ y reconocer un suma geométrica $$ \sum_{k=1}^n \frac{1}{2^k}=\frac12\frac{1-\frac1{2^{n}}}{1-\frac1{2}}=1-2^{-n}. $$

Answer 4

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

así, por adición

$$f(n)=\sum_{k=0}^{n-1}\frac{1}{2^k}$$

$=2(1-2^{-n}) \; $ como una suma geométrica.

Para $n=0$ Esta fórmula es verdadera.

Dejemos que $n\geq 0$ tal que $f(n)=2(1-2^{-n})$ .

entonces

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

He aquí un enfoque alternativo, que no es tan rápido como la respuesta de @Biran M. Scotts :).

Multiplica la ecuación de recurrencia por $x^n$ y la suma de $n=0$ a $n=\infty$ (no me importa la convergencia).

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

Ahora, usa $f(0)=0$ , utilice la serie geométrica infinita

$$\sum_{n=0}^{\infty}1/2^nx^n=\sum_{n=0}^{\infty}(x/2)^n=\frac{1}{1-x/2}$$

y llevar ambas sumas con $f(n)x^n$ y hacia el lado izquierdo:

$$(1/x-1)\sum_{n=0}^{\infty}f(n)x^{n}=\frac{1}{1-x/2}.$$

Esto es lo mismo que $$\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].$$

Ahora, utiliza la serie geométrica para las fracciones del lado derecho:

$$\sum_{n=0}^{\infty}f(n)x^{n}=\sum_{n=0}^{\infty}(2-1/2^n)x^{n+1}.$$

Obsérvese que la primera suma es igual a $\sum_{n=0}f(n+1)x^{n+1}$ porque $f(0)=0$ . Utilizando esta observación y comparando los coeficientes de ambas sumas obtenemos:

$$f(n+1)=2-1/2^n.$$

Después de la sustitución $n \to n-1$ obtenemos:

$$f(n)=2-1/2^{n-1}.$$