[daniiy]

Hola.

He dado varios ejercicios sobre esto, y los entiendo. Sin embargo, en los siguientes dos problemas no soy capaz de resolver más allá del caso base. De hecho en el segundo no sé ni sacar la fórmula que tengo que tratar de demostrar.

1. Probar que \( 1+2^n = 3^n, \forall{n}\geq{2} \)

2. Dado un grafo G, demostrar que el número de vértices de grado impar es par.

[Juan Pablo Sancho]

Es falsa esa igualdad:

\( \displaystyle 3^n = (1+2)^n = 1 + \sum_{i=1}^n {n \choose i} 2^i > 1+2^n  \)
 


\( \displaystyle 1 + 2^4 = 17 \neq 3^4 = 81  \)

[Luis Fuentes]

Hola

2. Dado un grafo G, demostrar que el número de vértices de grado impar es par.

Ahí no veo la necesidad de usar inducción.

La suma de los grados de todos los vértices es el doble del número de aristas, es decir, un número par.

La suma de los grados de los vértices de grado par es un número par.

Por tanto la suma de los grados de los vértices de grado impar es la diferencia de dos números pares y así un número par. Esto no es posible si hubiese un número impar de vértices de grado impar.

Saludos.

[daniiy]

Es falsa esa igualdad:

\( \displaystyle 3^n = (1+2)^n = 1 + \sum_{i=1}^n {n \choose i} 2^i > 1+2^n  \)
 


\( \displaystyle 1 + 2^4 = 17 \neq 3^4 = 81  \)

Perdón, lo escribí mal. En vez de igual, era menor.
\( 1+2^n < 3^n, \forall{n}\geq{2} \)

[daniiy]

Hola

2. Dado un grafo G, demostrar que el número de vértices de grado impar es par.

Ahí no veo la necesidad de usar inducción.

La suma de los grados de todos los vértices es el doble del número de aristas, es decir, un número par.

La suma de los grados de los vértices de grado par es un número par.

Por tanto la suma de los grados de los vértices de grado impar es la diferencia de dos números pares y así un número par. Esto no es posible si hubiese un número impar de vértices de grado impar.

Saludos.

Piden expresamente demostrarlo por inducción, por eso digo...

Aprovecho para mostrarte otro post que creé, por si no lo viste, y por si puedes echarme un cable también.
http://rinconmatematico.com/foros/index.php?topic=81935.0

Gracias, Saludos.

[Luis Fuentes]

Hola

Perdón, lo escribí mal. En vez de igual, era menor.
\( 1+2^n < 3^n, \forall{n}\geq{2} \)

Para el paso inductivo ten en cuenta que:

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

Si por hipótesis de inducción sabes que \( 1+2^n<3^n \) tu problema se reduce a probar que:

\( 2^{n+1}-2^n<3^{n+1}-3^n \)

Pero:

\( 2^{n+1}-2^n=2^n \)
\( 3^{n+1}-3^n=2\cdot 3^n \)

y es claro que \( 2^n<2\cdot 3^n \).

Saludos.

[daniiy]

Entendido, gracias

Pero respecto al ejercicio de los grafos... No sabrías demostrarlo por inducción? Es que no tengo ni idea..

[Luis Fuentes]

Hola

Entendido, gracias

Pero respecto al ejercicio de los grafos... No sabrías demostrarlo por inducción? Es que no tengo ni idea..

 Pues me parece rizar el rizo.

 Una opción es usar inducción por el número de aristas:

 - Para un grafo de una arista el resultado es claro.

 - Supón que todo grafo de \( n-1 \) aristas tiene un número par de vértices de grado impar. Probémoslo para un grafo de \( n \) aristas:

 Dado un grafo de \( n \) aristas si retiras una tienes un grafo con \( n-1 \) aristas. Por hipótesis de inducción el número de vértices de grado impar del nuevo grafo es par: llamémosle \( 2k \). Sea \( m \) el número de vértices de grado impar del grafo inicial. Entonces.

 - Si la arista unía dos vértices de grado par, entonces el nuevo grafo tiene dos nuevos vértices de grado impar. Es decir: \( m=2k-2 \). Par.

 - Si la arista unía dos vértices de grado impar, entonces el nuevo grafo tiene dos  vértices menos de grado impar. Es decir: \( m=2k+2 \). Par.

 - Si la arista unía un vértice de grado par con uno de grado impar, entonces el nuevo grafo tiene los mismos vértices de grado impar. Es decir: \( m=2k \). Par.

Saludos.

[daniiy]

Hola.

Perdona que te vuelva con el tema, pero al intentar hacer yo el ejercicio me he liado en el primer ejercicio que me resolviste. No entiendo como pasas de aquí

Si por hipótesis de inducción sabes que \( 1+2^n<3^n \) tu problema se reduce a probar que:

a aquí:
\( 2^{n+1}-2^n<3^{n+1}-3^n \)

Respecto al ejercicio de los grafos queda totalmente entendido.

Muchas gracias, saludos.

[Luis Fuentes]

Hola

Perdona que te vuelva con el tema, pero al intentar hacer yo el ejercicio me he liado en el primer ejercicio que me resolviste. No entiendo como pasas de aquí

Si por hipótesis de inducción sabes que \( 1+2^n<3^n \) tu problema se reduce a probar que:

a aquí:
\( 2^{n+1}-2^n<3^{n+1}-3^n \)

Queremos probar que:

\( 1+2^{n+1}<3^{n+1} \)

usando que

\( 1+2^n<3^n \)

Entonces:

\( 1+2^{n+1}=1\color{red}+2^n\color{black}+2^{n+1}\color{red}-2^n\color{black}<3^n+2^{n+1}-2^n \)

(en la desigualdad hemos aplicado la hipótesis de inducción; en rojo marco lo que he sumado y restado para hacer intervenir tal hipóteis)

Es decir que ahora queremos probar que:

\( 3^n+2^{n+1}-2^n<3^{n+1} \)

equivalentemente que:

\( 2^{n+1}-2^n<3^{n+1}-3^n \)

Saludos.