Proof by induction
Introduit| English | Sens |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | entier positif |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | induction mathématique |
| base case/beɪs keɪs/ | cas de base |
| inductive step/ɪnˈdʌktɪv step/ | étape d'induction |
| inductive hypothesis/ɪnˈdʌktɪv haɪˈpɒθəsɪs/ | inductive hypothesis : hypothèse de récurrence |
| divisible/dɪˈvɪzɪbl/ | divisible |
| conjecture/kənˈdʒektʃə/ | conjecture |
| factorial/fækˈtɔːrɪəl/ | factorial : factorielle |
Une règle reproductible doit avoir un point de départ
- Vérifier un motif pour les premiers entiers positifs ne peut établir une infinité de cas. L'induction mathématique relie une première affirmation vraie à une règle qui s'étend à chaque assertion suivante.
- Le cas de base initie la chaîne. L'étape inductive démontre un lien conditionnel pour un entier arbitraire autorisé, et non seulement pour le nombre suivant dans un tableau court.
L'image des dominos représente deux exigences distinctes : une vérité initiale et un lien fonctionnant à chaque position ultérieure.
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₀.
Énoncer exactement ce qui est démontré
- Rédiger l'affirmation $P(n)$ et son intervalle d'entiers, en commençant par $n_0$. Vérifier $P(n_0)$ directement, en utilisant une condition de départ donnée si nécessaire. Ensuite, supposer $P(k)$ pour un entier arbitraire $k\ge n_0$ et utiliser cette hypothèse pour déduire $P(k+1)$.
- L'hypothèse inductive est temporaire et conditionnelle : elle ne suppose pas le résultat pour tous les entiers. Conclure que $P(n)$ est valable pour tous les entiers $n\ge n_0$, car le cas de base vérifié et le lien général couvrent ensemble l'ensemble des entiers.
Ne pas supposer le cas $k+1$ tout en cherchant à le prouver. N'établir uniquement $P(k+1)\Rightarrow P(k)$ conduit à une implication erronée. L'algèbre rétroactive peut aider à planifier, mais une démonstration nécessite un argument progressif valide ou une chaîne justifiée d'équivalences.
The two steps of proof by induction are the base case and the:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Both steps are essential. Without the base case, the chain never starts.
Ajouter le nouveau terme à une somme
- Pour une somme finie, isoler le dernier terme de la somme $k+1$. Remplacer uniquement ses $k$ premiers termes grâce à l'hypothèse, puis simplifier jusqu'à la formule contenant $n=k+1$.
- Présenter le cas initial, l'hypothèse exacte et la conclusion finale. Une ligne se contentant de citer la formule de la somme pour $k+1$ n'a pas établi le lien.
Démontrer $\sum_{r=1}^{n}r(r+1)=n(n+1)(n+2)/3$ pour les entiers positifs $n$.
Pour $n=1$, les deux côtés valent $2$. Supposer que la formule est vraie pour $n=k$. Alors
Il s'agit de la formule requise $k+1$, donc le résultat est acquis pour tous les entiers positifs par induction.
Using induction, the sum 1 + 2 + ... + n = n(n+1)/2. For n = 10, find the sum.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Mettre en évidence un multiple entier pour la divisibilité
- Pour prouver qu'une expression est divisible par un entier non nul $m$, l'écrire sous la forme $m$ multiplié par un entier. Dans l'étape inductive, isoler l'expression supposée divisible et montrer que chaque terme restant est également un multiple de $m$.
- Tant un multiple commode de l'expression $k$ que la différence entre deux expressions consécutives peuvent être utiles. Nommer explicitement le multiplicateur entier ; dire « c'est divisible à vue » peut masquer une utilisation manquante de l'hypothèse.
Soit $F_n=10^n-4^n$. À $n=1$, $F_1=6$. Supposons $F_k=6q$ pour un entier $q$. Alors
La parenthèse est un entier. Ainsi $6$ divise $F_{k+1}$, et l'induction prouve le résultat pour tout entier positif $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.
Utiliser la récurrence pour progresser
- Une récurrence fournit une méthode valide pour passer de $u_k$ à $u_{k+1}$. Vérifiez que la forme fermée proposée possède le premier terme correct, substituez sa version $k$ dans la récurrence et simplifiez.
- N'insérez pas la formule proposede $k+1$ directement dans la récurrence en la qualifiant de preuve, sauf si vous établissez une équivalence réversible avec la formule connue $k$. La voie la plus claire commence par la récurrence donnée.
Supposons $u_1=2$ et $u_{n+1}=3u_n+2$. L'affirmation est $u_n=3^n-1$. Elle est vraie à $n=1$. En supposant $u_k=3^k-1$,
Cela prouve la forme fermée réclamée pour tous les entiers positifs, et non seulement pour les premiers termes calculés $2,8,26$.
A sequence has $u_1=3$ et $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.
Préserver une borne et vérifier les signes du dénominateur
- Pour une inégalité impliquant une récurrence, substituez l'hypothèse dans une expression dont le signe peut être contrôlé. Expliquez pourquoi son dénominateur est positif avant de l'utiliser pour préserver l'inégalité.
- Parfois, l'hypothèse requise contient deux bornes. Prouvez que les deux survivent à l'étape. Une fois qu'une borne est établie pour chaque terme, elle peut justifier un argument de monotonie ultérieur sans supposer la réponse.
Soient $u_1=1$ et $u_{n+1}=(4u_n+3)/(u_n+2)$. Prouver $0<u_n<3$.
Le premier terme satisfait les deux inégalités. Si $0<u_k<3$, le numérateur et le dénominateur de $u_{k+1}$ sont positifs. De plus,
Ainsi $0<u_{k+1}<3$. Par induction, $0<u_n<3$ pour tout entier positif $n$. Les bornes établies donnent alors
donc la suite est croissante. Cette dernière déduction utilise la borne démontrée ; elle ne remplace pas cette preuve.
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.
Prouver une formule de puissance de matrice par multiplication
- Pour les puissances d'une même matrice, $M^{k+1}=M^kM$. Substituez l'expression proposée pour $M^k$, multipliez ligne par colonne et montrez que chaque entrée a la forme $k+1$.
- Une puissance de matrice ne s'obtient pas en élevant chaque entrée à une puissance. De plus, une formule vérifiée aux étapes $M$ et $M^2$ n'est qu'une indication jusqu'à ce que l'étape arbitraire-$k$ ait été démontrée.
Pour $M=\begin{pmatrix}2&1\\0&1\end{pmatrix}$, affirmer
Le cas $n=1$ est $M$ lui-même. En utilisant l'hypothèse $k$,
Par conséquent, la formule vaut pour tous les entiers positifs par induction. Le cas séparé $n=0$ est $M^0=I$, ce qui correspond également à cette formule.
Pour $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.
Conjecturer et prouver un motif de dérivée
- Une conjecture est une affirmation suggérée par des preuves, mais non un théorème établi. Calculez quelques dérivées, repérez un motif et exprimez-le précisément avec sa valeur initiale de $n$.
- Pour une formule de dérivée d'ordre $n$, dérivez une fois la dérivée supposée d'ordre $k$. Un motif correct nécessite une véritable dérivation et simplification dans l'étape inductive.
Pour $f(x)=xe^{2x}$, les premières dérivées sont $e^{2x}(2x+1)$, $e^{2x}(4x+4)$ et $e^{2x}(8x+12)$. Conjecturez
La première dérivée donne le cas de base. En dérivant la formule de $k$, on obtient
ce qui correspond à la dérivée souhaitée d'ordre $k+1$. Par conséquent, la conjecture est vraie pour tout entier positif $n$.
In mathematics, a conjecture is:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
A conjecture is an unproven statement based on evidence — you then try to prove it (often by induction).
Pour $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.
Relier l'ordre de dérivée dans l'énoncé
- Si la formule prétendue concerne une dérivée d'ordre $2n$, augmenter $n$ d'une unité augmente l'ordre de dérivée de deux. L'étape inductive doit donc comporter deux dérivations successives. Comptez l'ordre de dérivée avant de commencer le calcul algébrique.
- Suivez séparément le signe alterné et le coefficient en fonction de $n$. Une affirmation portant sur des ordres pairs sélectionnés n'est pas automatiquement valable pour tous les ordres de dérivée.
Pour $f(x)=x\sin x$, affirmer
En $n=1$, on a $f''(x)=2\cos x-x\sin x$, comme requis. En dérivant une fois la formule supposée d'ordre $2k$, on obtient $(-1)^k\{x\cos x+(2k+1)\sin x\}$. Une seconde dérivation donne
ce qui complète l'étape jusqu'à l'ordre de dérivée $2(k+1)$. La formule est donc valide pour tous les entiers positifs $n$ par récurrence.
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.
Transformer un essai court en conjecture factorielle
- Une factorielle est définie par $n!=1\cdot2\cdots n$ pour un entier positif $n$, avec $0!=1$. Quelques sommes partielles peuvent suggérer une factorielle décalée, mais le motif doit alors résister à une étape inductive générale.
- Calculez soigneusement les premiers termes et cherchez une expression simple après ajout ou soustraction d'une constante. Lorsqu'une question demande une démonstration par récurrence, présentez cette preuve même si un argument télescopique direct existe également.
Pour $S_n=\sum_{r=1}^{n}r\,r!$, les premières sommes sont $1,5,23,119$. En ajoutant $1$, on obtient $S_n=(n+1)!-1$.
En $n=1$, les deux côtés valent $1$. En supposant la formule pour $k$,
Ainsi, la conjecture est vraie pour tous les entiers positifs par récurrence. L'identité $r\,r!=(r+1)!-r!$ explique aussi pourquoi les sommes s'annulent en télescope, mais lister seulement les valeurs initiales ne constitue pas une preuve.
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.
Commencer à la première valeur couverte par l'affirmation
- Une affirmation peut commencer à $n=4$ ou à un autre entier spécifié. Prouvez ce cas initial et supposez que $k$ appartient à la plage autorisée ; ne remplacez pas silencieusement le domaine par tous les entiers positifs.
- Pour $2^n\ge n^2$ avec $n\ge4$, le cas de base est $16=16$. En supposant $2^k\ge k^2$ pour $k\ge4$, nous avons $2^{k+1}\ge2k^2\ge(k+1)^2$, car $2k^2-(k+1)^2=(k-1)^2-2>0$ se trouve dans cette plage. La récurrence prouve ainsi l'affirmation énoncée pour tous les entiers $n\ge4$.
La chaîne prouve l'énoncé pour la plage indiquée à partir de 4. En fait, n=3 échoue, car 8 est inférieur à 9 ; le point de départ fait partie de l'affirmation.
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.
Vérifiez l'implication et la conclusion
- Vérifiez que l'hypothèse est utilisée pour prouver le cas suivant dans le sens direct, avec toutes les expressions définies. Une base vérifiée et une implication inverse seule ne suffisent pas à établir l'affirmation pour les entiers ultérieurs.
- Reliez la conclusion au lien : $P(k)\Rightarrow P(k+1)$ atteint tous les entiers suivants, tandis qu'un lien de $k$ à $k+2$ ne couvre qu'une parité à partir d'une base unique. Pour couvrir les deux parités avec ce lien, deux cas de départ sont nécessaires.
Les énoncés $P(n): n\le5$ donnent un avertissement. $P(1)$ est vrai et $P(k+1)\Rightarrow P(k)$ est vrai pour les entiers positifs, mais $P(6)$ est faux. L'implication inversée ne remplace pas l'étape directe requise.
Prouvez le bon cas de départ, supposez un k arbitraire autorisé et établissez l'étape directe. Reliez la conclusion à la plage atteinte ; une formule de dérivée d'ordre pair nécessite deux dérivations par étape.
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?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.