Cómo demostrar que una fórmula recursiva alcanza siempre un umbral por inducción

Question

Tengo una fórmula recursiva: $f(n) = \frac{f(n-1)+1}{2} $ donde $f(0) = h$

Debería demostrar inductivamente que para cualquier h real, f(n) siempre cruzará eventualmente un umbral 1, lo que significa que f(n) siempre llegará eventualmente a un valor inferior a 1 para cualquier altura inicial h.

En general, puedo hacer la inducción, pero en este problema, estoy teniendo problemas porque estoy teniendo problemas para llegar a un caso base y no tengo idea de cómo seguir adelante.

Answer 1

Calculando los primeros valores de $f(n)$ a mano por un número arbitrario de $h$ vemos

$$f(0) = h,$$

$$f(1) = \frac{h}{2} + \frac{1}{2},$$

$$f(2) = \frac{h}{4} + \frac{1}{4}+ \frac{1}{2},$$

$$f(3) = \frac{h}{8} + \frac{1}{8}+ \frac{1}{4} + \frac{1}{2}.$$

Ya me lleva a hacer una conjetura para una forma cerrada para $f(n)$ . ¿Puedes conjeturar lo que podría ser antes de leer lo que se me ocurrió? Conjeturo

$$f(n) = \frac{h}{2^n} + \frac{1}{2^n}+ \frac{1}{2^{n-1}}+ \dots + \frac{1}{2}.$$

Lo siento, no sé cómo hacer eso de ocultar parte de mi respuesta a menos que te desplaces sobre ella. Debería aprenderlo. De todas formas, deberías intentar demostrar esa forma cerrada para todos $n$ , tal vez también por inducción. Cuando se tiene mucha experiencia, no es necesaria una demostración aquí, ya que está claro que la forma cerrada es exacta, pero a tu nivel es una buena práctica. Ahora, una vez que tienes eso, podemos simplificar la forma cerrada usando la fórmula de la serie geométrica finita . Si no estás familiarizado con eso, también puedes buscarlo. Tiene una derivación fácil que un estudiante avanzado de pre-calc podría entender.

Utilizando la fórmula que he mencionado, simplificamos a

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

así que

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

y finalmente,

$$f(n) = \frac{h-1}{2^n} + 1.$$

Quizás ahora quieras volver a intentar por tu cuenta analizar esto, y también cuestionar si lo que intentas demostrar es cierto. Veo tres casos:

1. Si $h > 1$ , $f(n)$ convergerá monótonamente hacia 1, lo que significa que nunca cruzará por debajo de 1.

2. Si $h=1$ , $f(n)$ es la constante 1.

3. Si $h < 1$ , $f(n)$ convergerá monótonamente hasta 1, lo que significa que siempre es menor que 1.