Semana 2: Demostración por Inducción Matemática

¿Qué es la inducción matemática?

La inducción matemática es una técnica que se usa para demostrar que una afirmación es cierta para todos los números naturales. Es como una cadena: si sabemos que se cumple para el primer número, y que si se cumple para uno también se cumple para el siguiente, entonces se cumplirá para todos.

Este método es comúnmente usado en programación o matemáticas para probar fórmulas, analizar el comportamiento de algoritmos o verificar patrones.

---

Ejemplo: suma de los primeros n números naturales

Queremos probar que la suma:

1 + 2 + 3 + ... + n

es igual a:

n * (n + 1) / 2

---

Paso 1: Caso base

SSi n es 1, entonces la suma es simplemente:

1

Y usando la fórmula:

1 * (1 + 1) / 2 = 2 / 2 = 1

Por lo tanto, la fórmula funciona para n = 1.

Paso 2: Hipótesis inductiva

Ahora vamos a suponer que la fórmula es válida para algún número k, es decir:

1 + 2 + 3 + ... + k = k * (k + 1) / 2

Esto se llama hipótesis inductiva.

Paso 3: Paso inductivo

Ahora debemos probar que, si la fórmula funciona para k, también funciona para k + 1. Es decir:

1 + 2 + 3 + ... + k + (k + 1)

Según la hipótesis, la parte hasta k ya sabemos que vale:

k * (k + 1) / 2

Entonces sumamos el siguiente número:

k * (k + 1) / 2 + (k + 1)

Sacamos factor común:

(k + 1) * (k / 2 + 1)

Simplificando:

(k + 1) * (k + 2) / 2

Que es justamente la fórmula original, pero reemplazando n por k + 1.

---

Conclusión

La inducción matemática es una forma ordenada y efectiva de demostrar fórmulas. Funciona mostrando que si la regla se cumple al inicio, y también se mantiene paso a paso, entonces se mantendrá siempre.

---

Taller Algoritmo de Fusión (Merge)

public class CodigoMerge {

    public static void merge(int[] A, int p, int q, int r) {
        int nL = q - p + 1;
        int nR = r - q;

        int[] L = new int[nL];
        int[] R = new int[nR];

        // Copiar los datos a los arreglos temporales
        for (int i = 0; i < nL; i++) {
            L[i] = A[p + i];
        }

        for (int j = 0; j < nR; j++) {
            R[j] = A[q + 1 + j];
        }

        int i = 0, j = 0, k = p;

        // Combinar los arreglos temporales en A[p..r]
        while (i < nL && j < nR) {
            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
            k++;
        }

        // Copiar elementos restantes de L[]
        while (i < nL) {
            A[k] = L[i];
            i++;
            k++;
        }

        // Copiar elementos restantes de R[]
        while (j < nR) {
            A[k] = R[j];
            j++;
            k++;
        }
    }

    // Método para imprimir el arreglo (opcional)
    public static void printArray(int[] A) {
        for (int num : A) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // Ejemplo de uso
    public static void main(String[] args) {
        int[] A = {1, 4, 5, 2, 3, 6};
        merge(A, 0, 2, 5); // Combina [1, 4, 5] con [2, 3, 6]
        System.out.print("Arreglo despues de merge: ");
        printArray(A);
    }
}

¿Qué hace este algoritmo?

Este algoritmo llamado "MERGE" se usa para juntar dos partes de un arreglo que ya están ordenadas. Lo que hace es comparar los elementos de cada parte y los va acomodando en orden en el arreglo original. Básicamente, va eligiendo el número más pequeño entre los dos lados y lo coloca en su lugar.

Es una parte clave del método de ordenamiento Merge Sort, que primero divide todo en partes más pequeñas y luego las va uniendo con este algoritmo para que queden bien ordenadas.

Se usa en situaciones como:

• Cuando ya tienes dos listas ordenadas y necesitas unirlas en una sola sin perder el orden.
• Como parte del proceso de Merge Sort, que funciona dividiendo y luego uniendo.
• Cuando quieres ordenar datos de forma eficiente y predecible, sin depender de la suerte.