Proof by induction · Démonstration par récurrence
| English | Français |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | entier positif |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | raisonnement par récurrence |
| base case/beɪs keɪs/ | cas de base |
| inductive step/ɪnˈdʌktɪv step/ | pas inductif |
| conjecture/kənˈdʒektʃə/ | conjecture |
| 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 preuve en dominos
- Comment prouver que quelque chose est vrai pour tout entier positif 正整数 — cas infinis ?
- L'induction mathématique 数学归纳法 fonctionne comme des dominos : renverser le premier (cas de base 基础情形), et montrer que chaque domino en renverse le suivant (étape inductive 归纳步骤). Si les deux fonctionnent, tous tombent.
Proof by induction route · Chemin de la démonstration par récurrence
See induction as a first domino plus a rule that pushes every next case. · Considérer la récurrence comme un premier domino plus une règle qui pousse chaque cas suivant.
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
Les deux étapes de l'induction
- L'induction mathématique prouve un résultat pour tout entier positif $n$ en deux étapes :
- Cas de base : montrer qu'il est vrai pour $n = 1$.
- Étape inductive : supposer qu'il est vrai pour $n = k$, puis prouver qu'il est vrai pour $n = k + 1$.
Exemple résolu. Prouver $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$. Cas de base ($n=1$) : MGD $= 1$, AMD $= \dfrac{1(2)}{2} = 1$. ✓ Étape inductive : Supposons vrai pour $n = k$. Pour $n = k+1$ : $\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$. ✓
La preuve par induction fonctionne comme une chaîne de dominos qui tombent
The two steps of proof by induction are the base case and the: · Les deux étapes de la démonstration par récurrence sont le cas de base et le :
Induction needs a base case plus an inductive step from k to k+1. · La récurrence nécessite un cas de base plus un pas inductif de k à k+1.
The base case usually shows the result is true for: · Le cas de base montre généralement que le résultat est vrai pour :
The base case checks the smallest value, usually n = 1. · Le cas de base vérifie la plus petite valeur, généralement n = 1.
If both the base case and the inductive step hold, the result is true for all positive integers n. · Si le cas de base et le pas inductif tiennent tous deux, le résultat est vrai pour tous les entiers positifs n.
That is exactly what the principle of induction guarantees. · C'est exactement ce que garantit le principe de récurrence.
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.
Pourquoi les deux étapes sont essentielles
- Le cas de base lance la chaîne. Sans lui, on pourrait "prouver" des énoncés faux.
- L'étape inductive l'étend. Sans elle, on n'a prouvé qu'un seul cas.
Les deux étapes sont essentielles. Une preuve avec seulement l'étape inductive ressemble à une rangée de dominos que personne ne pousse — ils ne tombent jamais. Une preuve avec seulement le cas de base ressemble à pousser un seul domino — un seul tombe.
You can prove a result by induction using only the inductive step, without a base case. · On peut prouver un résultat par récurrence en utilisant uniquement le pas inductif, sans cas de base.
Both steps are essential. Without the base case, the chain never starts. · Les deux étapes sont essentielles. Sans le cas de base, la chaîne ne commence jamais.
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$.
Conjecture 猜想 puis prouver
- On fait souvent une conjecture (une hypothèse raisonnable) à partir de quelques cas, puis on la confirme par preuve par induction.
- Exemple : $1 + 3 + 5 + 7 = 16 = 4^2$. Conjecture : la somme des $n$ premiers nombres impairs est $n^2$.
Using induction, the sum 1 + 2 + ... + n = n(n+1)/2. For n = 10, find the sum. · En utilisant la récurrence, la somme 1 + 2 + ... + n = n(n+1)/2. Pour n = 10, trouver la somme.
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. ✓
Induction pour la divisibilité
- Prouver que $3^n - 1$ est divisible 整除 par $2$ pour tout entier positif $n$.
- Cas de base ($n=1$) : $3^1 - 1 = 2$, divisible par $2$. ✓
- Étape inductive : $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$. Puisque $3^k - 1$ est divisible par $2$ (par hypothèse), toute l'expression l'est aussi. ✓
In mathematics, a conjecture is: · En mathématiques, une conjecture est :
A conjecture is an unproven statement based on evidence — you then try to prove it (often by induction). · Une conjecture est une affirmation non prouvée basée sur des preuves — vous essayez ensuite de la prouver (souvent par récurrence).
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
Vous avez compris
- induction = cas de base ($n=1$) + étape inductive ($n=k \Rightarrow n=k+1$)
- les deux étapes ensemble prouvent pour tout entier positif
- souvent conjecturer à partir de cas, puis prouver par induction