Autor Tema: Ecuación de recurrencia

0 Usuarios y 1 Visitante están viendo este tema.

04 Diciembre, 2017, 08:42 pm
Leído 2321 veces

Alcornoque

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 37
  • Karma: +0/-0
  • Sexo: Masculino
Buenas tardes, he tratado de resolver la siguiente ecuación de recurrencia,
pero no sé cómo resolverla.


 T(n) = \( \left \{\begin{matrix} 1 & \mbox{si } n = 0 \\  T(n - 1)  + 1  & \mbox{si } n \mbox{ es impar} \\ T(n - 1)  - 1  & \mbox{si }  n\mbox{ es par} \end{matrix}\right. \)


Dibujé una tabla y obtuve que para los número pares la recurrencia es igual a 1 y para los impares a 2, pero de ahí no sé cómo demostrar mi conjetura por inducción.

Saludos cordiales.

04 Diciembre, 2017, 09:35 pm
Respuesta #1

Ignacio Larrosa

  • Moderador Global
  • Mensajes: 2,399
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Actividades con GeoGebra
Buenas tardes, he tratado de resolver la siguiente ecuación de recurrencia,
pero no sé cómo resolverla.

T(0)=1
T(n)=    T(n - 1) 1 si n es par
             T(n - 1) 1 si n es impar

Dibujé una tabla y obtuve que para los número pares la recurrencia es igual a 1 y para los impares a 2, pero de ahí no sé cómo demostrar mi conjetura por inducción.

Saludos cordiales.

Revisa tu mensaje, no se entiende la deficinición de \( T(n) \). Tal y como está, parece que \( T(n) = 1 \forall{}n\in{}\mathbb{N} \). Y no olvides utilizar \( \LaTeX \) para escribir las fórmulas.

Saludos,
Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por muchísimo menos ...  (yo)

05 Diciembre, 2017, 02:30 am
Respuesta #2

Alcornoque

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 37
  • Karma: +0/-0
  • Sexo: Masculino
Buenas tardes, he tratado de resolver la siguiente ecuación de recurrencia,
pero no sé cómo resolverla.

T(0)=1
T(n)=    T(n - 1) 1 si n es par
             T(n - 1) 1 si n es impar

Dibujé una tabla y obtuve que para los número pares la recurrencia es igual a 1 y para los impares a 2, pero de ahí no sé cómo demostrar mi conjetura por inducción.

Saludos cordiales.

Citar
Revisa tu mensaje, no se entiende la deficinición de \( T(n) \). Tal y como está, parece que \( T(n) = 1 \forall{}n\in{}\mathbb{N} \). Y no olvides utilizar \( \LaTeX \) para escribir las fórmulas.

Saludos,

Aquí dejo la fórmula ya corregida:

 T(n) = \( \left \{\begin{matrix} 1 & \mbox{si } n = 0 \\  T(n - 1)  + 1  & \mbox{si } n \mbox{ es impar} \\ T(n - 1)  - 1  & \mbox{si }  n\mbox{ es par} \end{matrix}\right. \)




05 Diciembre, 2017, 02:30 am
Respuesta #3

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 4,607
  • País: es
  • Karma: +0/-0
La recurrencia se puede escribir también como \( a_{n+1}:=a_n+(-1)^n \) con \( a_0:=1 \). La sucesión que describe es \( 1,2,1,2,1,2,\ldots \)

05 Diciembre, 2017, 04:38 am
Respuesta #4

Alcornoque

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 37
  • Karma: +0/-0
  • Sexo: Masculino
La recurrencia se puede escribir también como \( a_{n+1}:=a_n+(-1)^n \) con \( a_0:=1 \). La sucesión que describe es \( 1,2,1,2,1,2,\ldots \)

Esa recurrencia la intenté resolver como una recurrencia lineal no homogénea, pero llegué a un escollo eligiendo el término n.

Me quedó esto:

(x - 1)(x - 1)

Lo que me arroja una solución múltiple con x = 1

Pero una vez resuelta la ecuación característica no obtengo lo que supuse al principio sobre la sucesión, según sea par o impar el núimero de entrada.

He cometido algún error?
Saludos cordiales.

05 Diciembre, 2017, 10:16 am
Respuesta #5

Ignacio Larrosa

  • Moderador Global
  • Mensajes: 2,399
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Actividades con GeoGebra
La recurrencia se puede escribir también como \( a_{n+1}:=a_n+(-1)^n \) con \( a_0:=1 \). La sucesión que describe es \( 1,2,1,2,1,2,\ldots \)

Esa recurrencia la intenté resolver como una recurrencia lineal no homogénea, pero llegué a un escollo eligiendo el término n.

Me quedó esto:

(x - 1)(x - 1)

Lo que me arroja una solución múltiple con x = 1

Pero una vez resuelta la ecuación característica no obtengo lo que supuse al principio sobre la sucesión, según sea par o impar el núimero de entrada.

He cometido algún error?
Saludos cordiales.

Tenemos que

\( a_0 = 1 \)

\( a_{n+1} = a_n + (-1)^n \)

\( a_{n+2} = a_n + (-1)^{n+1} + (-1)^n = a_n \)

\( a_1 = 1 + (-1)^0 = 2 \)

Aqui tenemos entonces una recurrencia lineal homogénea de segundo orden, cuya ecuación característica es

\( r^2 = 1\;\Longrightarrow{}\;r = \pm{}1 \)

Entonces la solución es de la forma

\( a_n = A\cdot{}1^n + B\cdot{}(-1)^n = A + B\cdot{}(-1)^n \)

Para \( n = 0\textrm{ y }n = 1 \):

\( \left. \begin{array}{l}{a_0 = 1 = A + B}\\{a_1 = 2 = A - B}\end{array}\right\}\;\Longrightarrow{}\;A = \displaystyle\frac{3}{2},\; B  = -\displaystyle \frac{1}{2} \)

\( a_n = \displaystyle\frac{3}{2} - \displaystyle\frac{(-1)^n}{2} \)

\( a_0 = 1, \;a_1 = 2 \)

Es decir,

\( a_n=\begin{cases} 1 & \text{si}&\textrm{ n es par}\\2 & \text{si}&\textrm{ n es impar}\end{cases} \)

Saludos,

Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por muchísimo menos ...  (yo)

05 Diciembre, 2017, 12:55 pm
Respuesta #6

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 56,141
  • País: es
  • Karma: +0/-0
Hola

Buenas tardes, he tratado de resolver la siguiente ecuación de recurrencia,
pero no sé cómo resolverla.


 T(n) = \( \left \{\begin{matrix} 1 & \mbox{si } n = 0 \\  T(n - 1)  + 1  & \mbox{si } n \mbox{ es impar} \\ T(n - 1)  - 1  & \mbox{si }  n\mbox{ es par} \end{matrix}\right. \)


Dibujé una tabla y obtuve que para los número pares la recurrencia es igual a 1 y para los impares a 2, pero de ahí no sé cómo demostrar mi conjetura por inducción.

 Si quieres hacer la prueba por inducción.

 Por inspección \( T(0)=1,\quad T(1)=2 \)

 Supongamos que para \( 0\leq k\leq n \) se cumple que:

\( T(k)=\begin{cases} 1 & \text{si}& n\textsf { par}\\2 & \text{si}&  n\textsf { impar}\end{cases} \)

 Probémoslo para \( n+1 \):

 - Si \( (n+1) \) es par, entonces por definición \( T(n+1)=T(n+1-1)-1=T(n)-1 \). Como \( n+1 \) es par, \( n \) es impar y por hipótesis de inducción \( T(n)=2 \). Así \( T(n+1)=2-1=1 \).

 - Si \( (n+1) \) es impar, entonces por definición \( T(n+1)=T(n+1-1)+1=T(n)+1 \). Como \( n+1 \) esim par, \( n \) es par y por hipótesis de inducción \( T(n)=1 \). Así \( T(n+1)=1+1=2 \).

Saludos.

05 Diciembre, 2017, 07:15 pm
Respuesta #7

shaka_shadow

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 2
  • Karma: +0/-0
La recurrencia se puede escribir también como \( a_{n+1}:=a_n+(-1)^n \) con \( a_0:=1 \). La sucesión que describe es \( 1,2,1,2,1,2,\ldots \)

Esa recurrencia la intenté resolver como una recurrencia lineal no homogénea, pero llegué a un escollo eligiendo el término n.

Me quedó esto:

(x - 1)(x - 1)

Lo que me arroja una solución múltiple con x = 1

Pero una vez resuelta la ecuación característica no obtengo lo que supuse al principio sobre la sucesión, según sea par o impar el núimero de entrada.

He cometido algún error?
Saludos cordiales.

Tenemos que

\( a_0 = 1 \)

\( a_{n+1} = a_n + (-1)^n \)

\( a_{n+2} = a_n + (-1)^{n+1} + (-1)^n = a_n \)

\( a_1 = 1 + (-1)^0 = 2 \)

Aqui tenemos entonces una recurrencia lineal homogénea de segundo orden, cuya ecuación característica es

\( r^2 = 1\;\Longrightarrow{}\;r = \pm{}1 \)

Entonces la solución es de la forma

\( a_n = A\cdot{}1^n + B\cdot{}(-1)^n = A + B\cdot{}(-1)^n \)

Para \( n = 0\textrm{ y }n = 1 \):

\( \left. \begin{array}{l}{a_0 = 1 = A + B}\\{a_1 = 2 = A - B}\end{array}\right\}\;\Longrightarrow{}\;A = \displaystyle\frac{3}{2},\; B  = -\displaystyle \frac{1}{2} \)

\( a_n = \displaystyle\frac{3}{2} - \displaystyle\frac{(-1)^n}{2} \)

\( a_0 = 1, \;a_1 = 2 \)

Es decir,

\( a_n=\begin{cases} 1 & \text{si}&\textrm{ n es par}\\2 & \text{si}&\textrm{ n es impar}\end{cases} \)

Saludos,



Muchas gracias, al final olvidé decir que finalmente lo pude hacer, mi mayor dificultad fue porque en clases de algoritmos mi profesor explicó que la B siempre se tomaba positiva, y en ese ejemplo evidentemente no era así. Muchas gracias una vez más por la ayuda.

05 Diciembre, 2017, 07:27 pm
Respuesta #8

Ignacio Larrosa

  • Moderador Global
  • Mensajes: 2,399
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Actividades con GeoGebra
Muchas gracias, al final olvidé decir que finalmente lo pude hacer, mi mayor dificultad fue porque en clases de algoritmos mi profesor explicó que la B siempre se tomaba positiva, y en ese ejemplo evidentemente no era así. Muchas gracias una vez más por la ayuda.

¿shaka_shadow mexicano es un trasunto de Alcornoque cubano?   ::)

Saludos,
Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por muchísimo menos ...  (yo)

05 Diciembre, 2017, 07:29 pm
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 56,141
  • País: es
  • Karma: +0/-0
Hola

Muchas gracias, al final olvidé decir que finalmente lo pude hacer, mi mayor dificultad fue porque en clases de algoritmos mi profesor explicó que la B siempre se tomaba positiva, y en ese ejemplo evidentemente no era así. Muchas gracias una vez más por la ayuda.

Pregunta Alcornoque y da las gracias shaka_schadow. Teneis la misma IP. ¿Sois la misma persona? Está desaconsejado que una misma persona use dos nicks diferentes en el foro; puede causar confusiones y malentendidos innecesarios.

Saludos.