4 votos

¿CÓMO se refactoriza una función recursiva en una sola ecuación

Tengo una ecuación inicial que es muy simple:

answer1 = 0*2+2

Pero es tan recursivo que:

answer2 = answer1*2+2
answer3 = answer2*2+2
answer4 = answer3*2+2

¿Cómo escribiría eso como una simple ecuación para poder determinar cuál es la respuesta 6 sin pasar primero por las respuestas 1-5?

answer1 = 2
answer2 = 6
answer3 = 14
answer4 = 30
answer5 = 62
answer6 = 126

8voto

Milo Brandt Puntos 23147

Una forma de resolver esto es considerar lo siguiente: Si escribimos answer1 como $a_1$ y answer2 como $a_2$ y así sucesivamente, uno puede volver a expresar su fórmula como: $$a_{n+1}=2a_n+2.$$ Esto sólo nos dice cómo obtener la siguiente respuesta ( $a_{n+1}$ ) en términos de la anterior ( $a_n$ ). El truco estándar para encontrar una forma cerrada para tal relación de recurrencia lineal es escribir algo como $$a_{n+1}=2(a_n+2)-2$$ lo importante aquí es que para obtener el siguiente número, sumamos dos, luego multiplicamos, luego restamos dos. Sin embargo, si encadenamos este proceso en sí mismo unas cuantas veces, por ejemplo para obtener $a_{n+3}$ en términos de $a_n$ entonces el proceso parece:

  • Añade dos a $a_n$ .
  • Dóblalo.
  • Reste dos.
  • Añade dos.
  • Dóblalo.
  • Reste dos.
  • Añade dos.
  • Dóblalo.
  • Reste dos.

pero podemos cancelar los pasos consecutivos de "restar dos" y luego "sumar dos" ya que no hacen nada juntos (y los he tachado arriba). Quitarlos da:

  • Añade dos a $a_n$ .
  • Dóblalo.
  • Dóblalo.
  • Dóblalo.
  • Reste dos.

Aquí, tenemos tres pasos de duplicación, pero si quisiéramos avanzar $k$ pasos, necesitaríamos $k$ pasos de doblar. Lo que significa que, desde la duplicación $k$ veces es lo mismo que multiplicar por $2^k$ podemos escribir: $$a_{n+k}=2^k(a_n+2)-2.$$ En particular, con su secuencia, $$a_n=2^n(a_0+2)-2=2^n \cdot 2 - 2 = 2^{n+1}-2$$


Ahora, mirando hacia atrás a lo que hicimos, podemos generalizar un poco. Noten que esencialmente, nuestro objetivo es escribir la ecuación en la forma: $$a_{n+1}=m(a_n+c)-c$$ ya que queremos que la adición $c$ y restando $c$ para cancelar "alrededor" de la multiplicación. En nuestro caso, esencialmente queríamos encontrar $m$ y $c$ de tal manera que la forma deseada se iguala a la forma dada - es decir: $$m(a_n+c)-c=2a_n+2$$ Claramente, $m=2$ para que esto suceda, ya que necesitamos igualar el coeficiente de $a_n$ . Así que queremos encontrar un $c$ satisfactoria: $$2(a_n+c)-c=2a_n+2$$ distribuyendo la $2$ da $$2a_n+2c-c=2a_n+2$$ y la cancelación de algunos términos da $$c=2$$ que es de donde obtuvimos ese número mágico.

Otra forma de ver esto es que $-2$ es el llamado "punto fijo" de la forma $2a_n+2$ - es decir, si nos conectamos $-2$ a esta fórmula para $a_n$ salimos $-2$ . Como el punto fijo no se mueve, es ventajoso medir todo con respecto al punto fijo - cuando aplicamos la expresión $2a_n+2$ todo se aleja el doble del punto fijo! Así que, básicamente, primero cambiamos $-2$ a $0$ añadiendo $2$ entonces doblamos las distancias desde el punto fijo, y luego volvemos todo atrás restando $2$ . En general, en la forma dada anteriormente, $-c$ será el punto fijo.


Sidenote: Este patrón de encadenar un patrón de:

  • Haz algo.
  • Haz otra cosa.
  • Deshaz lo primero.

es bastante común en las matemáticas ya que, si entendemos "Hacer algo más" bastante bien, ahora entendemos todo este proceso de 3 pasos también.

5voto

lhf Puntos 83572

Tienes $a_0=0$ y $a_{n+1}=2a_n+2$ .

Deje que $b_n=a_n+2$ . Luego $b_{n+1}=2b_n$ y así $b_n=2^n b_0 = 2^{n+1}$ .

Esto da $a_n=2^{n+1}-2=2(2^{n}-1)$ .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X