Proof by induction
Introduzido| English | Significado |
|---|---|
| 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 |
| inductive hypothesis/ɪnˈdʌktɪv haɪˈpɒθəsɪs/ | hipótese indutiva |
| divisible/dɪˈvɪzɪbl/ | divisível |
| conjecture/kənˈdʒektʃə/ | conjetura |
| factorial/fækˈtɔːrɪəl/ | fatorial |
Uma regra repetível deve ter um ponto de partida
- Verificar um padrão para os primeiros inteiros positivos não estabelece infinitos casos. A indução matemática conecta uma primeira afirmação verdadeira a uma regra que alcança cada próxima afirmação.
- O caso base inicia a cadeia. O passo indutivo prova uma ligação condicional para um inteiro arbitrário permitido, não apenas o próximo número em uma tabela curta.
A imagem dos dominós representa dois requisitos separados: uma verdade inicial e uma ligação que funciona em toda posição subsequente.
A starting truth and a general forward link
The base case P(n₀) and P(k)⇒P(k+1) for every k≥n₀ together establish P(n) for all integers n≥n₀.
Enuncie exatamente o que está sendo provado
- Escreva a afirmação $P(n)$ e sua faixa de inteiros, começando em $n_0$. Verifique $P(n_0)$ diretamente, usando uma condição inicial dada, se apropriado. Depois, assuma $P(k)$ para um inteiro arbitrário $k\ge n_0$ e use essa suposição para derivar $P(k+1)$.
- A hipótese indutiva é temporária e condicional: ela não assume o resultado para todos os inteiros. Conclua que $P(n)$ vale para todos os inteiros $n\ge n_0$, pois o caso base verificado e a ligação geral juntos os alcançam.
Não assuma o caso $k+1$ enquanto tenta prová-lo. Mostrar apenas $P(k+1)\Rightarrow P(k)$ gera a implicação incorreta. Álgebra retrógrada pode ajudar no planejamento, mas uma demonstração exige um argumento válido de progressão ou uma cadeia justificada de declarações equivalentes.
The two steps of proof by induction are the base case and the:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Induction needs a base case plus an inductive step from k to k+1.
For a claim stated for every positive integer n starting at 1, which base case is needed?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The base case checks the smallest value, usually n = 1.
If P(1) is true and P(k) implies P(k+1) for every integer k≥1, then P(n) is true for all positive integers n.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The base case is explicitly1, and the forward implication applies to every later step. A proof starting at a different base has a different guaranteed range.
You can prove a result by induction using only the inductive step, without a base case.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Both steps are essential. Without the base case, the chain never starts.
Adicione o novo termo em uma soma
- Para uma soma finita, separe o último termo da soma $k+1$. Substitua apenas seus primeiros $k$ termos usando a hipótese, depois simplifique até a fórmula com $n=k+1$.
- Mostre o caso inicial, a hipótese exata e a conclusão final. Uma linha que apenas cita a fórmula da soma para $k+1$ não estabeleceu a ligação.
Prove $\sum_{r=1}^{n}r(r+1)=n(n+1)(n+2)/3$ para inteiros positivos $n$.
Em $n=1$, ambos os lados são iguais a $2$. Assuma que a fórmula é válida para $n=k$. Então
Esta é a fórmula requerida de $k+1$; logo, o resultado segue para todos os inteiros positivos por indução.
Using induction, the sum 1 + 2 + ... + n = n(n+1)/2. For n = 10, find the sum.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
10(11)/2 = 55.
Prove by induction that $\sum_{r=1}^{n}(2r-1)^2=n(4n^2-1)/3$ for every positive integer $n$. Show the algebra in the forward step.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Prove by induction that $\sum_{r=0}^{n}3^r=(3^{n+1}-1)/2$ for every integer $n\ge0$. State the correct base case and explain the term count.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Expor um múltiplo inteiro para divisibilidade
- Para provar que uma expressão é divisível por um inteiro não nulo $m$, escreva-a como $m$ vezes um inteiro. No passo indutivo, isole a expressão assumida divisível e mostre que cada termo restante também é múltiplo de $m$.
- Tanto um múltiplo conveniente da expressão $k$ quanto a diferença entre expressões consecutivas podem ajudar. Nomeie o multiplicador inteiro; "é divisível por inspeção" pode ocultar o uso necessário da hipótese.
Seja $F_n=10^n-4^n$. Em $n=1$, $F_1=6$. Assuma $F_k=6q$ para um inteiro $q$. Então
O colchete é um inteiro. Portanto, $6$ divide $F_{k+1}$, e a indução prova o resultado para todo inteiro positivo $n$.
Prove by induction that $25^n+7^n-2$ is divisible by $6$ for every positive integer $n$. Identify an integer multiple in the step instead of quoting a pattern from small cases.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Prove by induction that $n^3-n$ is divisible by $6$ for every positive integer $n$. Explain why the extra term in the step is divisible by $6$, rather than only by $3$.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Usar a recorrência para avançar
- Uma recorrência oferece um método válido para passar de $u_k$ para $u_{k+1}$. Verifique se uma forma fechada proposta tem o primeiro termo correto, substitua sua versão de $k$ na recorrência e simplifique.
- Não insira a fórmula proposta de $k+1$ na recorrência e chame isso de prova sem estabelecer uma equivalência reversível com a fórmula conhecida de $k$. A rota mais clara começa pela recorrência dada.
Suponha $u_1=2$ e $u_{n+1}=3u_n+2$. A afirmação é $u_n=3^n-1$. É verdadeira em $n=1$. Assumindo $u_k=3^k-1$,
Isso prova a forma fechada afirmada para todos os inteiros positivos, não apenas os primeiros termos calculados $2,8,26$.
A sequence has $u_1=3$ e $u_{n+1}=2u_n+3$. Calculate its first four terms, conjecture a closed formula, and prove it by induction. Separate evidence for the guess from its proof.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Preservar um limite e verificar sinais dos denominadores
- Para uma desigualdade envolvendo uma recorrência, substitua a hipótese em uma expressão cujo sinal possa ser controlado. Explique por que seu denominador é positivo antes de usá-lo para preservar a desigualdade.
- Às vezes, a hipótese necessária contém dois limites. Prove que ambos sobrevivem ao passo. Uma vez estabelecido um limite para cada termo, ele pode justificar um argumento subsequente de monotonidade sem assumir a resposta.
Sejam $u_1=1$ e $u_{n+1}=(4u_n+3)/(u_n+2)$. Prove $0<u_n<3$.
O primeiro termo satisfaz ambas as desigualdades. Se $0<u_k<3$, o numerador e o denominador de $u_{k+1}$ são positivos. Além disso,
Logo, $0<u_{k+1}<3$. Por indução, $0<u_n<3$ para todo inteiro positivo $n$. Os limites estabelecidos fornecem então
portanto, a sequência é crescente. Esta última dedução usa o limite provado; não o substitui.
Suppose $0<u_1<1$ is given and $u_{n+1}=2u_n/(1+u_n)$. Prove by induction that $0<u_n<1$ for all positive integers. Then use your proved bounds to decide whether the sequence is increasing.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Prove a fórmula da potência de matriz por multiplicação
- Para potências de uma matriz, $M^{k+1}=M^kM$. Substitua a expressão proposta para $M^k$, multiplique linha por coluna e mostre que cada entrada tem a forma $k+1$.
- A potência de uma matriz não é obtida elevando-se cada entrada a uma potência. Além disso, uma fórmula verificada em $M$ e $M^2$ é apenas uma evidência até que o passo arbitrário-$k$ tenha sido provado.
Para $M=\begin{pmatrix}2&1\\0&1\end{pmatrix}$, afirma-se
O caso $n=1$ é $M$ em si. Usando a hipótese de $k$,
Portanto, a fórmula vale para todos os inteiros positivos por indução. O caso separado $n=0$ é $M^0=I$, que também se encaixa nesta fórmula.
A favor $M=\begin{pmatrix}2&1\\0&2\end{pmatrix}$, calculate $M^2$, then prove $M^n=\begin{pmatrix}2^n&n2^{n-1}\\0&2^n\end{pmatrix}$ for every positive integer $n$. Show the off-diagonal multiplication explicitly.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Conjeture e prove um padrão de derivadas
- Uma conjetura é uma afirmação sugerida por evidências, não um teorema estabelecido. Calcule algumas derivadas, procure um padrão e expresse-o precisamente com seu valor inicial de $n$.
- Para uma fórmula de derivada de ordem $n$, diferencie uma vez a derivada assumida de ordem $k$. Um padrão correto exige uma diferenciação real e simplificação no passo indutivo.
Para $f(x)=xe^{2x}$, as primeiras derivadas são $e^{2x}(2x+1)$, $e^{2x}(4x+4)$ e $e^{2x}(8x+12)$. Conjeture
A primeira derivada fornece o caso base. Diferenciar a fórmula de $k$ resulta em
que é a derivada de ordem $k+1$ requerida. Logo, a conjetura é verdadeira para todo inteiro positivo $n$.
In mathematics, a conjecture is:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
A conjecture is an unproven statement based on evidence — you then try to prove it (often by induction).
A favor $f(x)=x^2e^x$, compute the first three derivatives and conjecture $f^{(n)}(x)$ for $n\ge1$. Prove the formula by induction for all real $x$.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
The values n²−n+41 at n=1,2,3 are 41,43,47, all prime. A student conjectures that the expression is prime for every positive integer n. Test n=41 and explain what the result says about limited trials and induction.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Combine a ordem da derivada na afirmação
- Se a fórmula afirmada for para a ordem de derivada $2n$, aumentar $n$ em uma unidade aumenta a ordem da derivada em duas. O passo indutivo deve diferenciar duas vezes. Conte a ordem da derivada antes de iniciar os cálculos algébricos.
- Acompanhe o sinal alternante e o coeficiente dependendo de $n$ separadamente. Uma afirmação sobre ordens pares selecionadas não é automaticamente uma afirmação sobre toda ordem de derivada.
Para $f(x)=x\sin x$, afirma-se
Em $n=1$, $f''(x)=2\cos x-x\sin x$, conforme exigido. Diferenciar a fórmula assumida de ordem $2k$ uma vez resulta em $(-1)^k\{x\cos x+(2k+1)\sin x\}$. Uma segunda diferenciação resulta em
completando o passo até a ordem de derivada $2(k+1)$. Portanto, a fórmula vale para todos os inteiros positivos $n$ por indução.
Prove by induction that for $f(x)=x\sin x$, $f^{(2n-1)}(x)=(-1)^{n-1}\{x\cos x+(2n-1)\sin x\}$ for every positive integer $n$. How many differentiations does one induction step require?
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Transforme uma tentativa curta em uma conjetura de fatorial
- Um fatorial é $n!=1\cdot2\cdots n$ para um inteiro positivo $n$, com $0!=1$. Algumas somas parciais podem sugerir um fatorial deslocado, mas o padrão deve então sobreviver a um passo indutivo geral.
- Calcule os primeiros termos cuidadosamente e procure uma expressão simples após adicionar ou subtrair uma constante. Quando uma questão pede indução, apresente essa prova mesmo que um argumento direto telescópico também esteja disponível.
Para $S_n=\sum_{r=1}^{n}r\,r!$, as primeiras somas são $1,5,23,119$. Adicionar $1$ sugere $S_n=(n+1)!-1$.
Em $n=1$, ambos os lados são iguais a $1$. Assumindo a fórmula para $k$,
Assim, a conjectura é válida para todos os inteiros positivos por indução. A identidade $r\,r!=(r+1)!-r!$ também explica por que as somas se telescopiam, mas listar valores iniciais isoladamente não constitui uma prova.
Let $S_n=\sum_{r=1}^{n}(r^2+r+1)r!$. Compute $S_1,S_2,S_3$, compare $S_n+1$ with $(n+1)!$, conjecture a formula for $S_n$, and prove it by induction.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Inicie no primeiro valor que a afirmação realmente abrange
- Uma afirmação pode começar em $n=4$ ou outro inteiro declarado. Prove o caso inicial e assuma que $k$ está na faixa permitida; não substitua silenciosamente o domínio por todos os inteiros positivos.
- Para $2^n\ge n^2$ com $n\ge4$, o caso base é $16=16$. Assumindo $2^k\ge k^2$ para $k\ge4$, temos $2^{k+1}\ge2k^2\ge(k+1)^2$, pois $2k^2-(k+1)^2=(k-1)^2-2>0$ está nessa faixa. Logo, a indução prova a afirmação declarada para todos os inteiros $n\ge4$.
A cadeia prova a faixa declarada começando em 4. Na verdade, n=3 falha, já que 8 é menor que 9; o ponto inicial faz parte da afirmação.
Prove $3^n\ge n^2$ by induction for every integer $n\ge2$. Justify the comparison in your inductive step. Does this proof by itself cover $n=1$?
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Audite a implicação e a conclusão
- Verifique se a hipótese é usada para provar o próximo caso na direção direta, com todas as expressões definidas. Um caso base verificado e uma implicação reversa sozinhos não estabelecem a afirmação para inteiros posteriores.
- Conecte a conclusão ao elo: $P(k)\Rightarrow P(k+1)$ alcança todo inteiro subsequente, enquanto um elo de $k$ para $k+2$ atinge apenas uma paridade a partir de uma única base. Para cobrir ambas as paridades com esse elo, são necessários dois casos iniciais.
As afirmações $P(n): n\le5$ fornecem um aviso. $P(1)$ é verdadeira e $P(k+1)\Rightarrow P(k)$ é verdadeira para inteiros positivos, contudo $P(6)$ é falsa. A implicação reversa não pode substituir o passo direto necessário.
Prove o caso inicial correto, assuma um k arbitrário permitido e estabeleça o passo direto. Conecte a conclusão à faixa alcançada; uma fórmula de derivada de ordem par exige duas derivações por etapa.
Using the formula for the sum of the first n integers, what is the sum when n = 8, and why is the inductive step not enough on its own?
The closed formula gives the sum directly. Induction still has to anchor that formula with a first true case.
What is the sum of the first 8 integers?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
8 times 9 divided by 2 is 36. Other options — 55 (the lesson sum for n = 10); 8 (the value of n).
A proposed proof of n+1<n says: assume k+1<k; adding 1 gives k+2<k+1; therefore the result holds for every positive integer. Identify the error and explain why a valid conditional calculation is insufficient.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Let P(n) be n≤7. A student checks P(1), proves P(k+1) implies P(k), and concludes P(n) for all positive integers. Show why this fails and identify a value of k where the required forward link fails.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
For P(n): n is odd, P(1) is true and P(k) implies P(k+2). What range does this chain cover? Why can it not establish the claim for all positive integers merely by calling the link an inductive step?
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.