Prueba por la inducción de una secuencia recursiva y una fórmula

Question

Así que tengo una tarea que me ha dado una gran presión a lo largo de los últimos 2 días. No hay video, o en línea ejemplo ha sido capaz de ayudarme con este problema y no sé a dónde acudir.

Me dan

$a_0=0$

$a_n=2a_{n-1}+1$

Después de escribir los 6 primeros términos de la serie: 0, 1, 3, 7, 15, 31, 63 se me ocurre una fórmula alternativa de

$a_n=2^n-1$

Tengo que probar estas fórmulas son las mismas mediante la Inducción en 3 partes:

• Demostrando el caso base
• Declarando mi Hipótesis Inductiva
• Mostrando el Paso Inductivo

He hecho Inductivo pruebas antes, pero no sé cómo se muestran los casos o hacer manipulaciones en una fórmula recursiva. No sé cómo se representan cuando n = k, entonces n = k + 1 o mostrando el enfoque mediante el uso de n = k – 1, entonces n = k.

Alguna idea?

Answer 1

Demostrando el caso base debe ser bastante simple.

Para la hipótesis inductiva, que asumiremos para $k\geq1$, $$a_{k-1}=2^{k-1}-1$$ From this you need to prove that $ a_k = 2 ^ $k-1. No debería ser demasiado difícil de conseguir desde aquí, siguiendo a la relación de recurrencia.