Autor Tema: Ayuda con inducción

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

31 Agosto, 2017, 03:30 pm
Leído 1558 veces

avmath

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 82
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos,

en un problema me piden que:

Dado un vector  \( [v_1,\dots,v_n]\in\mathbb{Z}^n \) tal que \( v_1<\cdots <v_n \), demuestre por inducción sobre \( n \) que:

$$\forall i,j[1,n]\left(i<j\Longrightarrow v_i - i \leq v_j - j\right)$$

He intentado darle vueltas pero, no tengo ni idea de como probar ni siquiera la base de inducción cuando \( n=2 \). Porque claro yo sé que:

$$v_i<v_j$$

Y que:

$$i < j$$

Pero ya no sé como unir las desigualdades para llegar a probar la expresión por inducción.
 
A ver si me podéis echar un cable.

Muchas gracias.

31 Agosto, 2017, 03:57 pm
Respuesta #1

Masacroso

  • Moderador Global
  • Mensajes: 2,243
  • País: es
  • Karma: +0/-0
Observa que si \( v_1=p \) para algún \( p\in\Bbb Z \) entonces \( v_2=p+m \) para algún \( m\in\Bbb N_{>0} \).

Spoiler
En general tienes que demostrar que si \( v_k=p \) entonces \( v_{k+j}=p+j+m \) para algún \( m\in\Bbb N_{\ge 0} \).
[cerrar]

31 Agosto, 2017, 04:13 pm
Respuesta #2

avmath

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 82
  • Karma: +0/-0
  • Sexo: Masculino
Hola Masacroso, gracias por la ayuda, no tengo mucho conocimiento de matemáticas la verdad. Voy a intentar sacar algo con las indicaciones que me das y si no lo consigo vuelvo a preguntar.

¡Gracias!

Editado: Creo que no tengo muy claro como demostrarlo, la verdad  :-[

31 Agosto, 2017, 05:02 pm
Respuesta #3

avmath

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 82
  • Karma: +0/-0
  • Sexo: Masculino
Que va, no lo consigo, gracias por la ayuda pero... no sé como sacar la solución. Básicamente he intentado hacer lo siguiente:

$$\begin{array}{lcl}
v_{1}=p &  & i=x\\
v_{2}=p+m &  & j=x+n
\end{array}$$

Y luego "jugar" con esas igualdades pero me temo me estoy desviando.

EDITO: Creo que lo he conseguido:

$$v_{2}-\overbrace{\left(x+n\right)}^{j}=\overbrace{p}^{v_{1}}+m-\left(x+n\right)$$

$$v_{2}-j=v_{1}+m-x-n$$

$$v_{2}-j=v_{1}-x+\left(m-n\right)$$

$$v_{2}-j=v_{1}-i+\left(m-n\right)$$

Esto es:$$v_{2}-j\leq v_{1}-i$$

La condición de igualdad se cumple a veces ya que:

$$m,n\in\mathbb{N}_{>0}$$

Entonces podría darse el caso en que \( m=n \)

Si alguien pudiera confirmar... , muchas gracias.

31 Agosto, 2017, 06:31 pm
Respuesta #4

Ignacio Larrosa

  • Moderador Global
  • Mensajes: 2,270
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Actividades con GeoGebra
Hola a todos,

en un problema me piden que:

Dado un vector  \( [v_1,\dots,v_n]\in\mathbb{Z}^n \) tal que \( v_1<\cdots <v_n \), demuestre por inducción sobre \( n \) que:

$$\forall i,j[1,n]\left(i<j\Longrightarrow v_i - i \leq v_j - j\right)$$

He intentado darle vueltas pero, no tengo ni idea de como probar ni siquiera la base de inducción cuando \( n=2 \). Porque claro yo sé que:

$$v_i<v_j$$

Y que:

$$i < j$$

Pero ya no sé como unir las desigualdades para llegar a probar la expresión por inducción.
 
A ver si me podéis echar un cable.

Muchas gracias.

Es que o me estoy perdiendo algo, o el enunciado es claramente falso (o incompleto). A menos que \( v_{i+1} - v_i > 1\; \forall{} i = 1\ldots n-1 \) no se puede asegurar tal cosa.

Por ejemplo, considera \( v_1 = 1.1, v_2 = 1.2 \). Evidentemente \( v_1 \leq{} v_2\textrm{ y }1 < 2 \), pero \( 1.1 - 1 \cancel \leq{}1.2 - 2 \)

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

31 Agosto, 2017, 07:46 pm
Respuesta #5

avmath

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 82
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos,

en un problema me piden que:

Dado un vector  \( [v_1,\dots,v_n]\in\mathbb{Z}^n \) tal que \( v_1<\cdots <v_n \), demuestre por inducción sobre \( n \) que:

$$\forall i,j[1,n]\left(i<j\Longrightarrow v_i - i \leq v_j - j\right)$$

He intentado darle vueltas pero, no tengo ni idea de como probar ni siquiera la base de inducción cuando \( n=2 \). Porque claro yo sé que:

$$v_i<v_j$$

Y que:

$$i < j$$

Pero ya no sé como unir las desigualdades para llegar a probar la expresión por inducción.
 
A ver si me podéis echar un cable.

Muchas gracias.

Es que o me estoy perdiendo algo, o el enunciado es claramente falso (o incompleto). A menos que \( v_{i+1} - v_i > 1\; \forall{} i = 1\ldots n-1 \) no se puede asegurar tal cosa.

Por ejemplo, considera \( v_1 = 1.1, v_2 = 1.2 \). Evidentemente \( v_1 \leq{} v_2\textrm{ y }1 < 2 \), pero \( 1.1 - 1 \cancel \leq{}1.2 - 2 \)

Saludos,

Hola, creo que te pierdes en que como puse en el enunciado, \( [v_1,\dots,v_n]\in\mathbb{Z}^n \), es decir, que como bien sabes, es un vector de números enteros.

De todas maneras aprovecho para hacer una pregunta, la "demostración" ,si es que lo que he hecho se le puede catalogar así, para n = 2, ya está hecha, es decir ya tengo la base de inducción.
Ahora supongo que la propiedad se cumple para \( n \)y la pruebo para \( n+1 \) pero la prueba es análoga ¿no? es lo mismo pero con \( v_i,v_j \) en lugar de \( v_1,v_2 \). Además, no tengo por qué partir de la suposición ¿verdad?

¡Saludos y muchas gracias!

31 Agosto, 2017, 08:36 pm
Respuesta #6

Ignacio Larrosa

  • Moderador Global
  • Mensajes: 2,270
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Actividades con GeoGebra
Hola a todos,

en un problema me piden que:

Dado un vector  \( [v_1,\dots,v_n]\in\mathbb{Z}^n \) tal que \( v_1<\cdots <v_n \), demuestre por inducción sobre \( n \) que:

$$\forall i,j[1,n]\left(i<j\Longrightarrow v_i - i \leq v_j - j\right)$$


Es que o me estoy perdiendo algo, o el enunciado es claramente falso (o incompleto). A menos que \( v_{i+1} - v_i > 1\; \forall{} i = 1\ldots n-1 \) no se puede asegurar tal cosa.

Por ejemplo, considera \( v_1 = 1.1, v_2 = 1.2 \). Evidentemente \( v_1 \leq{} v_2\textrm{ y }1 < 2 \), pero \( 1.1 - 1 \cancel \leq{}1.2 - 2 \)

Saludos,

Hola, creo que te pierdes en que como puse en el enunciado, \( [v_1,\dots,v_n]\in\mathbb{Z}^n \), es decir, que como bien sabes, es un vector de números enteros.


Ciertamente, tengo que cambiar las gafas ...  :laugh: :laugh:

Creo que es sencillo, si no es que me he vuelto a perder algo.

Caso base:  \( [v_1,v_2]\in\mathbb{Z}^2 \) tal que \( v_1 < v_2  \)

\( v_2 \geq{}v_1 + 1\;\Rightarrow{}\; v_2 - 2 \geq{} v_1 + 1 - 2 = v_1 - 1 \)

Paso inductivo: Supongamos que es cierto para n y consideremos

\( [v_1,\dots,v_n, v_{n+1}]\in\mathbb{Z}^{n+1} \) tal que \( v_1<\cdots <v_n<v_{n+1} \)

Tenemos que ver que \( \forall{}i \leq{}n, v_{n+1} - (n+1) \geq{} v_i - i \)


\( v_{n+1} - (n+1)\geq{}v_n + 1 - (n+1) = v_n - n \geq{}v_i - i \)

por hipótesis.

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

31 Agosto, 2017, 09:24 pm
Respuesta #7

avmath

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 82
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos,

en un problema me piden que:

Dado un vector  \( [v_1,\dots,v_n]\in\mathbb{Z}^n \) tal que \( v_1<\cdots <v_n \), demuestre por inducción sobre \( n \) que:

$$\forall i,j[1,n]\left(i<j\Longrightarrow v_i - i \leq v_j - j\right)$$


Es que o me estoy perdiendo algo, o el enunciado es claramente falso (o incompleto). A menos que \( v_{i+1} - v_i > 1\; \forall{} i = 1\ldots n-1 \) no se puede asegurar tal cosa.

Por ejemplo, considera \( v_1 = 1.1, v_2 = 1.2 \). Evidentemente \( v_1 \leq{} v_2\textrm{ y }1 < 2 \), pero \( 1.1 - 1 \cancel \leq{}1.2 - 2 \)

Saludos,

Hola, creo que te pierdes en que como puse en el enunciado, \( [v_1,\dots,v_n]\in\mathbb{Z}^n \), es decir, que como bien sabes, es un vector de números enteros.


Ciertamente, tengo que cambiar las gafas ...  :laugh: :laugh:

Creo que es sencillo, si no es que me he vuelto a perder algo.

Caso base:  \( [v_1,v_2]\in\mathbb{Z}^2 \) tal que \( v_1 < v_2  \)

\( v_2 \geq{}v_1 + 1\;\Rightarrow{}\; v_2 - 2 \geq{} v_1 + 1 - 2 = v_1 - 1 \)

Paso inductivo: Supongamos que es cierto para n y consideremos

\( [v_1,\dots,v_n, v_{n+1}]\in\mathbb{Z}^{n+1} \) tal que \( v_1<\cdots <v_n<v_{n+1} \)

Tenemos que ver que \( \forall{}i \leq{}n, v_{n+1} - (n+1) \geq{} v_i - i \)


\( v_{n+1} - (n+1)\geq{}v_n + 1 - (n+1) = v_n - n \geq{}v_i - i \)

por hipótesis.

Saludos,


Gracias a los dos ¡no sabéis lo que me habéis ayudado!

01 Septiembre, 2017, 10:04 am
Respuesta #8

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,121
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Ciertamente, tengo que cambiar las gafas ...  :laugh: :laugh:

Creo que es sencillo, si no es que me he vuelto a perder algo.

Caso base:  \( [v_1,v_2]\in\mathbb{Z}^2 \) tal que \( v_1 < v_2  \)

\( v_2 \geq{}v_1 + 1\;\Rightarrow{}\; v_2 - 2 \geq{} v_1 + 1 - 2 = v_1 - 1 \)

Paso inductivo: Supongamos que es cierto para n y consideremos

\( [v_1,\dots,v_n, v_{n+1}]\in\mathbb{Z}^{n+1} \) tal que \( v_1<\cdots <v_n<v_{n+1} \)

Tenemos que ver que \( \forall{}i \leq{}n, v_{n+1} - (n+1) \geq{} v_i - i \)


\( v_{n+1} - (n+1)\geq{}v_n + 1 - (n+1) = v_n - n \geq{}v_i - i \)

Sólo un mínimo matiz; la demostración está bien, pero quizá sobre todo para alguien que está empezando con esto de la inducción sería bueno poner de manifiesto un detalle. Para probar el caso n+1 habría que demostrar que si \( [v_1,\dots,v_n, v_{n+1}]\in\mathbb{Z}^{n+1} \) tal que \( v_1<\cdots <v_n<v_{n+1} \) entoncs \( \forall 1<i<j\leq n+1 \) se cumple \( v_i-i\leq v_j-j \).

Si \( j\leq n \) el resultado se tiene directamente por hipótesis de inducción (el término \( v_{n+1} \) no influye). Por tanto sólo hay que probar el caso \( j=n+1 \).

Saludos.

03 Septiembre, 2017, 12:37 am
Respuesta #9

avmath

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 82
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Ciertamente, tengo que cambiar las gafas ...  :laugh: :laugh:

Creo que es sencillo, si no es que me he vuelto a perder algo.

Caso base:  \( [v_1,v_2]\in\mathbb{Z}^2 \) tal que \( v_1 < v_2  \)

\( v_2 \geq{}v_1 + 1\;\Rightarrow{}\; v_2 - 2 \geq{} v_1 + 1 - 2 = v_1 - 1 \)

Paso inductivo: Supongamos que es cierto para n y consideremos

\( [v_1,\dots,v_n, v_{n+1}]\in\mathbb{Z}^{n+1} \) tal que \( v_1<\cdots <v_n<v_{n+1} \)

Tenemos que ver que \( \forall{}i \leq{}n, v_{n+1} - (n+1) \geq{} v_i - i \)


\( v_{n+1} - (n+1)\geq{}v_n + 1 - (n+1) = v_n - n \geq{}v_i - i \)

Sólo un mínimo matiz; la demostración está bien, pero quizá sobre todo para alguien que está empezando con esto de la inducción sería bueno poner de manifiesto un detalle. Para probar el caso n+1 habría que demostrar que si \( [v_1,\dots,v_n, v_{n+1}]\in\mathbb{Z}^{n+1} \) tal que \( v_1<\cdots <v_n<v_{n+1} \) entoncs \( \forall 1<i<j\leq n+1 \) se cumple \( v_i-i\leq v_j-j \).

Si \( j\leq n \) el resultado se tiene directamente por hipótesis de inducción (el término \( v_{n+1} \) no influye). Por tanto sólo hay que probar el caso \( j=n+1 \).

Saludos.

Hola el_manco, muchas gracias por la aclaración, sinceramente no entendía por qué había probado solamente uno de los casos que había. Pero claro, luego le di vueltas y vi que por transitividad de \( < \), si demuestro que el caso \( n + 1 \) es mayor al \( n \), y el \( n \) era mayor a todos los anteriores (por hipótesis), por transitividad de \( < \) pues ya están probados los demás casos.

La duda que siempre me suele asaltar es, cuando yo supongo la propiedad \( P \) cierta para \( n \), qué tengo que hacer:
  • ¿A partir de lo que he supuesto para \( n \) probar el caso \( n+1 \) ?
  • ¿A partir del \( n+1 \) llegar a lo que he supuesto mediante operaciones bien razonadas?

Es decir yo tengo que probar que:
$$P_n \Longrightarrow P_{n+1}$$
Pero eso no es ni mucho menos equivalente a probar:
$$P_{n+1} \Longrightarrow P_{n}$$

¿Verdad?

Muchas gracias.