Proof by induction · Prova por indução
| English | Português |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | inteiro positivo |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | indução matemática |
| base case/beɪs keɪs/ | caso base |
| inductive step/ɪnˈdʌktɪv step/ | passo indutivo |
| conjecture/kənˈdʒektʃə/ | conjectura |
| divisible/dɪˈvɪzɪbl/ | divisível |
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.
A prova dos dominós
- Como provar que algo é verdadeiro para todo inteiro positivo 正整数 — infinitos casos?
- Indução matemática 数学归纳法 funciona como dominós: derrubar o primeiro (caso base 基础情形) e mostrar que cada um derruba o próximo (passo indutivo 归纳步骤). Se ambos funcionarem, todos caem.
Proof by induction route · Rota de prova por indução
See induction as a first domino plus a rule that pushes every next case. · Veja a indução como uma primeira domino mais uma regra que empurra cada próximo caso.
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
Os dois passos da indução
- Indução matemática prova um resultado para todo inteiro positivo $n$ em dois passos:
- Caso base: mostre que é verdadeiro para $n = 1$.
- Passo indutivo: assuma que é verdadeiro para $n = k$, depois prove para $n = k + 1$.
Exemplo resolvido. Prove $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$. Caso base ($n=1$): LHS $= 1$, RHS $= \dfrac{1(2)}{2} = 1$. ✓ Passo indutivo: Assuma verdadeiro 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}$. ✓
A prova por indução funciona como uma corrente de dominós caindo
The two steps of proof by induction are the base case and the: · As duas etapas da prova por indução são o caso base e o:
Induction needs a base case plus an inductive step from k to k+1. · A indução precisa de um caso base mais um passo indutivo de k para k+1.
The base case usually shows the result is true for: · O caso base geralmente mostra que o resultado é verdadeiro para:
The base case checks the smallest value, usually n = 1. · O caso base verifica o menor valor, geralmente n = 1.
If both the base case and the inductive step hold, the result is true for all positive integers n. · Se tanto o caso base quanto o passo indutivo forem válidos, o resultado é verdadeiro para todos os inteiros positivos n.
That is exactly what the principle of induction guarantees. · Isso é exatamente o que o princípio da indução garante.
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 que ambos os passos são essenciais
- O caso base inicia a cadeia. Sem ele, você poderia "provar" afirmações falsas.
- O passo indutivo estende o resultado. Sem ele, você provou apenas um caso.
Ambos os passos são essenciais. Uma prova com apenas o passo indutivo é como uma fileira de dominós que ninguém empurra — eles nunca começam a cair. Uma prova com apenas o caso base é como empurrar um único dominó — apenas um cai.
You can prove a result by induction using only the inductive step, without a base case. · Você pode provar um resultado por indução usando apenas o passo indutivo, sem um caso base.
Both steps are essential. Without the base case, the chain never starts. · Ambas as etapas são essenciais. Sem o caso base, a corrente nunca começa.
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$.
Conjectura 猜想 depois prove
- Muitas vezes você faz uma conjectura (um palpite razoável) a partir de alguns casos, depois confirma por prova indutiva.
- Exemplo: $1 + 3 + 5 + 7 = 16 = 4^2$. Conjectura: a soma dos primeiros $n$ números ímpares é $n^2$.
Using induction, the sum 1 + 2 + ... + n = n(n+1)/2. For n = 10, find the sum. · Usando indução, a soma 1 + 2 + ... + n = n(n+1)/2. Para n = 10, encontre a soma.
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. ✓
Indução para divisibilidade
- Prove $3^n - 1$ é divisível 整除 por $2$ para todos os inteiros positivos $n$.
- Caso base ($n=1$): $3^1 - 1 = 2$, divisível por $2$. ✓
- Passo indutivo: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$. Como $3^k - 1$ é divisível por $2$ (pela suposição), todo o expression também é. ✓
In mathematics, a conjecture is: · Em matemática, uma.wind is:
A conjecture is an unproven statement based on evidence — you then try to prove it (often by induction). · Uma.wind é uma afirmação não provada baseada em evidências — você então tenta prová-la (muitas vezes por indução).
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
Entendeu?
- indução = caso base ($n=1$) + passo indutivo ($n=k \Rightarrow n=k+1$)
- juntos, ambos os passos provam para todos os inteiros positivos
- frequentemente conjeture a partir de casos, depois prove por indução