[manooooh]

Hola!

Estaba mirando el video de Edu Sáenz de Cabezón:

está viendo que \( a_n=2a_{n-1}+1 \) equivale a la fórmula no recursiva \( a_n=2^n-1 \).

Para probar este resultado, lo que conozco es usar inducción, pero lo que hace él (y lo que siempre pensé pero nunca me animé a emitir una opinión), es que, para probar que la no recursiva es equivalente a la recursiva, reemplaza la expresión en la recursiva y comprueba que los dos miembros son iguales. En efecto,

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

pero en mi curso no lo vimos así, sino con inducción. Así que me pregunta es:

¿Es el método de reemplazar en la recursiva y ver que los miembros son el mismo un método válido?

¿Es equivalente a probarlo por inducción?

Gracias!!
Saludos

[geómetracat]

Sí, está bien, y es esencialmente equivalente a probarlo por inducción. Fíjate que el cálculo que haces es básicamente el mismo que harías en el paso inductivo.

[manooooh]

Hola! Gracias por responder

Lo entiendo... a medias. O sea tiene que ver inducción por el tema de reemplazar y tal.

Pero la diferencia que veo es que en este método NO usa la implicación \( p(h)\to p(h+1) \), o sea no considera una hipótesis inductiva, ¿cierto?

De todas formas puede que me esté enrocscando más de lo necesario, porque soy cabeza dura. Por ejemplo el paso base está verificado unos segundos antes en el video.

Saludos

[geómetracat]

Sí, no hay paso inductivo como tal. Es "comprobar la solución", lo que haces es verificar que \( a_n=2^n-1 \) cumple la ecuación recurrente para un \( n \) arbitrario. Decía que es esencialmente equivalente a la demostración por inducción porque al fin y al cabo el trabajo que haces viene a ser el mismo.

[manooooh]

Hola

Ah, vale. Gracias. Ya entiendo.

Está interpretando la relación de recurrencia como una ecuación, y cuando encuentra la no recursiva, la "mete" en la original para ver si cumple o no.

Pregunto: ¿Es entonces un método que sirve para cualquier tipo de relación de recurrencia, por más que su orden sea superior a \( 83 \)?

Porque por ejemplo no serviría para el caso en que en vez de igualdad sea desigualdad, por ejemplo si queremos comprobar que \( x+1\geq2 \) tiene como solución a \( [1,+\infty) \), no podemos comprobar con todos los valores porque son infinitos incontables. Lo mismo si tuviésemos algo del estilo \( a_n\geq a_{n-1}+3a_{n-2} \) con \( a_0=2 \) y \( a_1=5 \). Si usáramos inducción se podría hacer, ¿no?

¿O es que tales "relaciones de recurrencia con desigualdades" no existen o no se estudian? Porque jamás me topé con una.

Saludos

[geómetracat]

Sí, sirve para cualquier orden. También te sirve para desigualdades, pero en el sentido de que el método te dice que la solución propuesta realmente cumple la desigualdad, no que sea la única que lo cumpla.

De hecho, lo mismo pasa con las igualdades. En principio esto no te asegura que la solución sea única, aunque es fácil demostrar que es única usando inducción.

El método de inducción es mucho más versátil que esto de "comprobar la solución" porque es aplicable a muchas situaciones distintas, lo puedes usar para probar cualquier afirmación sobre los naturales.

Sobre lo de si existen las relaciones de recurrencia con desigualdades, claro que existen, de hecho acabas de poner una. 
Otra cosa es si se usan en la práctica, a mí no me suena haber visto muchas por ahí, pero es probable que aparezcan por ejemplo en el análisis de la complejidad de algoritmos y cosas así.

[manooooh]

Hola

Pero ese método de descomposición en potencias de 2 se puede usar siempre , otra cosa es que sea factible.
Si te ha salido un número menor que  \( 10^6 \), entonces ese es el residuo o resto módulo \( 10^6 \), ya sea residuo parcial, ( de alguna potencia de 7) o el residuo final en ese caso el número coincide con las 6 últimas cifras.

Es que ya al inicio del algoritmo de Ignacio, no lo puedo aplicar, porque si bien \( \varphi(10^6)=400.000 \), ocurre que \( 400.000>9999 \).

Es decir que aunque sepamos que \( 7^{40000}\equiv1\pmod{10^6} \), ¿cómo lo descomponemos para hacer los cálculos con el \( 7^{9999} \)?

Saludos

[Luis Fuentes]

Hola

 Algo más sobre todo esto. Cuando uno define una ecuación por recurrencia, por ejemplo como la del caso que citabas:

\( a_n=2a_{n-1}+1 \) (con la condición inicial \( a_1=1 \))

 está presuponiendo que eso define de manera inequívoca una sucesión. La prueba rigurosa de que eso es así se basa precisamente en el principio de inducción.

Saludos.