Proof by induction · Demostración por inducción
| English | Español |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | entero positivo |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | inducción matemática |
| base case/beɪs keɪs/ | caso base |
| inductive step/ɪnˈdʌktɪv step/ | paso inductivo |
| conjecture/kənˈdʒektʃə/ | conjetura |
| divisible/dɪˈvɪzɪbl/ | divisible |
The domino proof
- How do you prove something is true for every positive integer 正整数 — infinitely many cases?
- Mathematical induction 数学归纳法 works like dominoes: knock over the first one (base case 基础情形), and show each domino knocks over the next (inductive step 归纳步骤). If both work, they all fall.
La demostración por dominó
- ¿Cómo demuestras que algo es verdadero para todo entero positivo 正整数 — infinitos casos?
- La inducción matemática 数学归纳法 funciona como los dominós: derribar el primero (caso base 基础情形) y demostrar que cada uno derriba al siguiente (paso inductivo 归纳步骤). Si ambos funcionan, todos caen.
Proof by induction route · Ruta de demostración por inducción
See induction as a first domino plus a rule that pushes every next case. · Ver la inducción como una primera ficha de dominó más una regla que empuja cada caso siguiente.
The two steps of induction
- Mathematical induction proves a result for every positive integer $n$ in two steps:
- Base case: show it's true for $n = 1$.
- Inductive step: assume it's true for $n = k$, then prove it for $n = k + 1$.
Worked example. Prove $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$. Base case ($n=1$): LHS $= 1$, RHS $= \dfrac{1(2)}{2} = 1$. ✓ Inductive step: Assume true for $n = k$. For $n = k+1$: $\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$. ✓
Proof by induction works like a chain of falling dominoes
Los dos pasos de la inducción
- La inducción matemática demuestra un resultado para todo entero positivo $n$ en dos pasos:
- Caso base: mostrar que es cierto para $n = 1$.
- Paso inductivo: asumir que es cierto para $n = k$, luego demostrarlo para $n = k + 1$.
Ejemplo resuelto. Demostrar $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$. Caso base ($n=1$): LHS $= 1$, RHS $= \dfrac{1(2)}{2} = 1$. ✓ Paso inductivo: Asumir que es cierto para $n = k$. Para $n = k+1$: $\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$. ✓
La demostración por inducción funciona como una cadena de dominós cayendo
The two steps of proof by induction are the base case and the: · Los dos pasos de la demostración por inducción son el caso base y el:
Induction needs a base case plus an inductive step from k to k+1. · La inducción necesita un caso base más un paso inductivo de k a k+1.
The base case usually shows the result is true for: · El caso base suele mostrar que el resultado es verdadero para:
The base case checks the smallest value, usually n = 1. · El caso base verifica el valor más pequeño, usualmente n = 1.
If both the base case and the inductive step hold, the result is true for all positive integers n. · Si tanto el caso base como el paso inductivo se cumplen, el resultado es verdadero para todos los enteros positivos n.
That is exactly what the principle of induction guarantees. · Eso es exactamente lo que garantiza el principio de inducción.
Why both steps are essential
- The base case starts the chain. Without it, you could "prove" false statements.
- The inductive step extends it. Without it, you've only proved one case.
Both steps are essential. A proof with only the inductive step is like a row of dominoes that nobody pushes — they never start falling. A proof with only the base case is like pushing one domino — only one falls.
Por qué ambos pasos son esenciales
- El caso base inicia la cadena. Sin él, podrías "demostrar" enunciados falsos.
- El paso inductivo lo extiende. Sin él, solo habrás demostrado un caso.
Ambos pasos son esenciales. Una demostración con solo el paso inductivo es como una fila de dominós a la que nadie empuja — nunca empiezan a caer. Una demostración con solo el caso base es como empujar un solo dominó — solo cae uno.
You can prove a result by induction using only the inductive step, without a base case. · Puedes demostrar un resultado por inducción usando solo el paso inductivo, sin caso base.
Both steps are essential. Without the base case, the chain never starts. · Ambos pasos son esenciales. Sin el caso base, la cadena nunca comienza.
Conjecture 猜想 then prove
- Often you make a conjecture (a sensible guess) from a few cases, then confirm it by inductive proof.
- Example: $1 + 3 + 5 + 7 = 16 = 4^2$. Conjecture: the sum of the first $n$ odd numbers is $n^2$.
Conjetura 猜想 y luego demostrar
- A menudo haces una conjetura (un supuesto razonable) a partir de unos pocos casos, y luego la confirmas mediante una demostración inductiva.
- Ejemplo: $1 + 3 + 5 + 7 = 16 = 4^2$. Conjetura: la suma de los primeros $n$ números impares es $n^2$.
Using induction, the sum 1 + 2 + ... + n = n(n+1)/2. For n = 10, find the sum. · Usando inducción, la suma 1 + 2 + ... + n = n(n+1)/2. Para n = 10, encuentra la suma.
10(11)/2 = 55.
Induction for divisibility
- Prove $3^n - 1$ is divisible 整除 by $2$ for all positive integers $n$.
- Base case ($n=1$): $3^1 - 1 = 2$, divisible by $2$. ✓
- Inductive step: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$. Since $3^k - 1$ is divisible by $2$ (by assumption), so is the whole expression. ✓
Inducción para divisibilidad
- Demostrar que $3^n - 1$ es divisible 整除 por $2$ para todos los enteros positivos $n$.
- Caso base ($n=1$): $3^1 - 1 = 2$, divisible por $2$. ✓
- Paso inductivo: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$. Dado que $3^k - 1$ es divisible por $2$ (por suposición), también lo es toda la expresión. ✓
In mathematics, a conjecture is: · En matemáticas, una conjetura es:
A conjecture is an unproven statement based on evidence — you then try to prove it (often by induction). · Una conjetura es una afirmación no demostrada basada en evidencia — luego intentas demostrarla (a menudo por inducción).
You've got it
- induction = base case ($n=1$) + inductive step ($n=k \Rightarrow n=k+1$)
- both steps together prove it for all positive integers
- often conjecture from cases, then prove by induction
Lo has entendido
- inducción = caso base ($n=1$) + paso inductivo ($n=k \Rightarrow n=k+1$)
- ambos pasos juntos prueban que es válido para todos los enteros positivos
- a menudo se conjetura a partir de casos, y luego se demuestra por inducción