¿Alguien puede explicar la inducción matemática (para probar un método recursivo)

Question

¿Puede alguien explicar la inducción matemática para probar un método recursivo? Soy estudiante de informática de primer año y todavía no he tomado Cálculo (lo he tenido hasta Trig). Lo entiendo, pero tengo problemas cuando me piden que escriba una prueba de inducción para un método recursivo.

Answer 1

He aquí una explicación de por ejemplo:

Digamos que tiene la siguiente fórmula que desea probar:

sum(i | i <- [1, n]) = n * (n + 1)/2 

Esta fórmula proporciona una formulario cerrado para la suma de todos los enteros entre 1 y n.

Comenzaremos por probar la fórmula para el caso base simple de n = 1. En este caso, ambos lados de la fórmula se reducen a 1. Esto a su vez significa que la fórmula es válida para n = 1.

A continuación, vamos a demostrar que si la fórmula es válida para un valor n, entonces se cumple para el siguiente valor de n (o n + 1). En otras palabras, si se cumple lo siguiente:

sum(i | i <- [1, n]) = n * (n + 1)/2 

A continuación, el siguiente también es cierto:

sum(i | i <- [1, n + 1]) = (n + 1) * (n + 2)/2 

Para ello, vamos a empezar con la primera parte de la última fórmula:

s1 = sum(i | i <- [1, n + 1]) = sum(i | i <- [1, n]) + (n + 1) 

Es decir, la suma de todos los enteros entre 1 y n + 1 es igual a la suma de enteros entre 1 y n, más el último término n + 1.

Como nos estamos basando esta prueba con la condición de que la fórmula es válida para n, podemos escribir:

s1 = n * (n + 1)/2 + (n + 1) = (n + 1) * (n + 2)/2 = s2 

Como se puede ver, hemos llegado a la segunda parte de la fórmula que estamos tratando de probar, lo que significa que la fórmula realmente se mantiene.

Esto completa la prueba inductiva, pero ¿qué significa realmente?

1. La fórmula es correcta para n = 0.
2. Si la fórmula es correcta para n, entonces es correcto para n + 1.

De 1 y 2, podemos decir: si la fórmula es correcta para n = 0, entonces es correcta para 0 + 1 = 1. Como probamos el caso de n = 0, entonces el caso de n = 1 es correcto.

Podemos repetir este proceso anterior de nuevo. El caso de n = 1 es correcto, entonces el caso de n = 2 es correcto. Este razonamiento puede ir ad infinitum; la fórmula es correcta para todos los valores enteros de n> = 1.

Answer 2

Primero, necesitas una funda de base. Entonces necesitas un paso inductivo que sea cierto para algunos pasos n. En su paso inductivo, necesitará una hipótesis inductiva. Esa hipótesis es la suposición que necesita haber hecho. Por último, utilice esa suposición para demostrar el paso n + 1

Answer 3

inducción! = Calc !!!

Puedo obtener N chicos borrachos con 10 * N cervezas.

Caso Base: 1 chico

puedo conseguir uno borracho con 10 cervezas

paso inductivo, dado p (n) demostrar p (n + 1)

puedo conseguir i chicos Borracho con 10 * cervezas, si agrego a otro chico, puedo emborracharlo con 10 cervezas más. Por lo tanto, puedo obtener i + 1 chicos ebrios con 10 * (i + 1) cervezas.

p (1) -> p (i + 1) -> p (i + 2) ... p (inf)

Matemática Discreta es fácil!