What is Investigating Démonstration par récurrence?

Prouve que pour tous les entiers positifs \(n\N), \N(3^{2n+2} + 8n -9\N) est divisible par 8.

Solution

Définis d'abord \Nf(f(n) = 3^{2n+2} + 8n -9 \).

Étape 1 : Considère maintenant le cas de base. Puisque la question dit pour tous les entiers positifs, le cas de base doit être \(f(1)\N). Tu peux remplacer \N(n=1\N) dans la formule pour obtenir

\N- \N[ \N- \N{align} f(1) = 3^{2+2} + 8 - 9 & = 3^4 - 1 \\ & = 81 - 1 \\ & = 80. \N-{align} \]

80 est clairement divisible par 10, donc la condition est vraie pour le cas de base.

Étape 2 : énonce ensuite l'hypothèse inductive. Cette hypothèse est que \(f(k) = 3^{2k + 2} + 8k - 9 \) est divisible par 8.

Étape 3 : Considère maintenant \(f(k+1)\). La formule sera :

\N-[ \N-{align} f(k+1) & = 3^{2(k+1)+2} + 8(k + 1) - 9 \N- & = 3^{2k + 4} + 8k + 8 -9 \N- & = 3^{2k+4} + 8k -9 + 8. \Nend{align} \]

Il peut sembler bizarre de l'écrire ainsi, sans simplifier le \N(8-9\N) pour le transformer en \N(-1\N). Il y a une bonne raison à cela : tu veux que la formule reste aussi proche que possible de la formule de \(f(k)\) puisque tu dois la transformer d'une manière ou d'une autre.

Pour effectuer cette transformation, remarque que le premier terme de \N(f(k+1) \Nest le même que le premier terme de \N(f(k)\Nmais multiplié par \N(3^2 = 9\N). Tu peux donc le diviser en deux parties distinctes.

\N- [\N- Début{align} f(k+1) & = 9 \Ncdot 3^{2k+2} + 8k -9 + 8 \N- & = 3^{2k+2} + 8 \cdot 3^{2k+2} + 8k -9 + 8 \N = (3^{2k+2} + 8k -9) + 8 \Ncdot 3^{2k+2} + 8 \N- & = f(k) + 8 \N- 3^{2k+2} + 8. \N-END{align} \]

Le premier terme est divisible par 8 en raison de l'hypothèse, et les deuxième et troisième termes sont des multiples de 8, donc ils sont également divisibles par 8. Puisqu'il s'agit de la somme de différents termes qui sont tous divisibles par 8, \(f(k+1)\) doit également être divisible par 8, en supposant que l'hypothèse inductive est vraie. Tu as donc prouvé l'étape inductive.

Étape 4 : Enfin, n'oublie pas d'écrire la conclusion. Elle devrait ressembler à ceci :

S'il est vrai que \Nf(k) est divisible par 8, alors il sera également vrai que \Nf(k+1) est divisible par 8. Puisqu'il est vrai que \Nf(1)est divisible par 8, il est vrai que \Nf(n)est divisible par 8 pour tous les entiers positifs \N(n).

Prouve que pour tout entier non négatif \N(n\N),

\[ |sin{(nx)}| \leq n \sin{x}, \]

pour \( x \N dans (0, \Npi) \N).

Solution

Étape 1 : Le cas de base est clair, puisque la substitution de \(n=1\) permet d'obtenir l'inégalité \( |\sin{x}| \leq{\sin{x}}\), ce qui est vrai pour \( x \N dans (0, \pi) \N).

Étape 2 : Pour l'hypothèse d'induction, suppose que

\[ | \sin{(mx)} | \leq m \sin{x}. \]

Étape 3: Tu dois maintenant prouver que \( |\sin{((m+1)x)}| \leq (m+1) \sin{x}. \) Tout d'abord, tu peux développer la parenthèse du côté gauche :

\[ |sin{((m+1)x)}| = |sin{(mx + x)}| \]

Maintenant, tu peux utiliser la formule de la somme trigonométrique des angles pour la fonction sinus.

\[ |sin{((m+1)x)}| = |sin{(mx)} \cos{(m)} + \cos{(mx)} \sin{(m)}|. \]

À partir de là, tu peux utiliser l'inégalité triangulaire pour les valeurs absolues: \N( | a + b| \leq |a| + |b| \N).

\[ |sin{((m+1)x)}| \leq |sin{(mx)} \cos{(x)}| + |cos{(mx)} \sin{(x)}|. \N- \N- \N- \N- \N- \N- \N- \N- \N- \N]

Rappelle-toi que \( \cos{(mx)} \) et \( \cos{(x)} \) sont inférieurs à un. Tu peux donc créer une nouvelle borne supérieure en estimant que les fonctions cosinus sont égales à 1 :

\[ \begin{align} |\sin{((m+1)x)}| &\leq |\sin{(mx)} \cos{(x)}| + |\cos{(mx)} \sin{(x)}| \\ &\leq |\sin{(mx)}| + |\sin{(x)}|. \Nend{align} \]

A partir de là, remarque qu'il y a \( |\sin{(mx)}| \N dans le côté gauche. C'est ici que tu peux utiliser l'hypothèse inductive. Tu connais \( |\sin{(mx)}| \leq m \sin{x}\), tu peux donc créer une autre borne supérieure :

\[ \begin{align} \sin{((m+1)x)}| &\leq |\sin{(mx)}| + |\sin{(x)}| \\N- &\leq m \sin{(x)} + |\sin{(x)}|. \Nend{align} \]

Enfin, comme nous l'avons indiqué dans le cas de base, \( |\sin{(x)}| \leq \sin{(x)} \N- \N- \N- \N- \N- \N- \N- \N-). S,

\[ |sin{((m+1)x)}| \leq m \sin{(x)} + \sin{(x)} = (m+1)\sin{(x)}, \].

comme il se doit.

Étape 4 : Pour finir, énonce la conclusion. Nous avons prouvé que l'inégalité est valable pour \N( n = m+1) si elle est valable pour \N( n = m.\N) Puisqu'elle est valable pour \N(n=1), par induction, elle sera valable pour tous les entiers positifs.

Prouve que tout entier \(n \geq 2\) peut être écrit comme un produit de nombres premiers.

Solution

Étape 1 : Premièrement, prouve le cas de base, qui dans ce cas requiert \(n=2\). Puisque \(2 \) est déjà un nombre premier, il s'écrit déjà comme un produit de nombres premiers, et donc le cas de base est vrai.

Étape 2 : Ensuite, énonce l'hypothèse inductive. Tu supposeras que pour tout \( 2 \leq n \leq k\), \(n\) peut être écrit comme un produit de nombres premiers.

Étape 3 : Enfin, tu dois utiliser l'hypothèse pour prouver que \(n=k+1 \) peut s'écrire comme un produit de nombres premiers. Il y a deux cas de figure :

• \(k+1\) est un nombre premier, auquel cas il est clairement déjà écrit comme un produit de nombres premiers.
• \(k+1\) n'est pas un nombre premier et il doit y avoir un nombre composite.

Si \(k+1\) n'est pas un nombre premier, cela signifie qu'il doit être divisible par un nombre autre que lui-même ou 1. Cela signifie qu'il existe \N(a_1\N) et \N(a_2\N), avec \N(2 \N- a_1\N) et \N(a_2 \N- k\N), tels que \N(k+1 = a_1 a_2. \N) Par l'hypothèse inductive, \N(a_1\N) et \N(a_2\N) doivent avoir une décomposition première, puisque \N(2 \N- a_1\N) et \N(a_2 \N- k\N). Cela signifie qu'il existe des nombres premiers \Npour p_1,\Npoints ,p_i\Net \Npour q_1,\Npoints ,q_j\Nde telle sorte que

\[ \begin{align} a_1 & = p_1\dots p_i \\ a_2 & = q_1 \dots q_j. \Nend{align} \]

Enfin, puisque \ (k+1 = a_1 a_2, \N) tu as :

\[ k+1 = p_1\dots p_i q_1\dots q_j \]

qui est un produit de nombres premiers. Il s'agit donc d'une décomposition en nombres premiers pour \N(k+1\N).

Étape 4 : \N-(k+1\N) aura une décomposition première si tous les nombres \N(n\N), \N(2 \Nleq n \Nleq k \N) ont également une décomposition première. Puisque 2 a une décomposition première, par induction, tout nombre entier positif supérieur ou égal à 2 doit avoir une décomposition première.

Prouve que pour tout entier positif \(n\N),

\N- 1^2 + \Npoints + n^2 = \Nfrac{n(n+1)(2n+1)}{6}. \N- [1^2 + \Npoints + n^2 = \Nfrac{n(n+1)(2n+1)}{6}].

Solution

Étape 1 : Considérons d'abord le cas de base, lorsque \(n=1\). Le côté gauche n'est clairement que 1, tandis que le côté droit devient

\[ \frac{1 \cdot 2 \cdot 3}{6} = \frac{6}{6} = 1. \]

Le cas de base est donc correct.

Étape 2 : écris ensuite l'hypothèse d'induction. Il s'agit de l'hypothèse suivante

\N- 1^2 + \Npoints + m^2 = \Nfrac{m(m+1)(2m+1)}{6}. \N]

Étape 3 : pour finir, prouve l'étape inductive. Le côté gauche, pour \(n=m+1\), sera :

\N[ 1^2 +\N points + m^2 + (m+1)^2 = (1^2 +\N points + m^2) + (m+1)^2. \N]

Les premiers termes sont dans l'hypothèse inductive. Tu peux donc les remplacer par le côté droit de l'hypothèse inductive :

\[ \begin{align} 1^2 +\dots + m^2 + (m+1)^2 & = \frac{m(m+1)(2m+1)}{6} + (m+1)^2 & = \frac{m(m+1)(2m+1) + 6(m+1)^2}{6} \N- & = \Nfrac{(m+1)\Nà gauche[m(2m+1) + 6(m+1)\Nà droite]}{6}. \N- [Fin{alignement}\N]

Ensuite, développe le bit à l'intérieur des crochets, tu obtiendras ainsi une quadratique. Tu peux ensuite résoudre la quadratique normalement :

\[ \begin{align} 1^2 +\dots + m^2 + (m+1)^2 & = \frac{(m+1)\left[2m^2+1m + 6m+6\right]}{6} \\ & = \frac{(m+1)[2m^2 + 7m + 6}{6} \N- & = \Nfrac{(m+1)(m+2)(2m+3)}{6} \N- & = \Nfrac{(m+1)((m+1)+1)(2(m+1)+1)}{6}, \Nend{align}\N]

comme demandé. Ainsi, tu as prouvé l'étape inductive.

Étape 4 : Pour finir, écris la conclusion. Si la formule de la somme des carrés est vraie pour tout entier positif \(m\N), alors elle sera vraie pour \N(m+1\N). Puisqu'elle est vraie pour \(n=1\), elle est vraie pour tous les entiers positifs.

Prouve la formule de Binet en utilisant l'induction.

Solution

Étape 1 : Premièrement, prouve la base d'induction. Cela se fera pour \N(F_0\N) et \N(F_1\N). Pour \N-(F_0\N) :

\[\frac{\phi^0 - \hat{\phi}^0}{\sqrt{5}} = \frac{1-1}{5} = 0, \]

ce qui correspond à la valeur de \( F_0\) comme prévu.

Pour \(F_1\) :

\[ \begin{align} \frac{\phi - \hat{\phi}}{\sqrt{5}} & = \frac{\frac{1+\sqrt{5}}{2} \frac{1-\sqrt{5}}{2}}{\sqrt{5}} \N- & = \frac{1}{\sqrt{5}}\cdot \frac{1-1 +\sqrt{5} + \sqrt{5}}{2} \N- & = 1, \Nend{align} \]

ce qui est la réponse attendue. Ainsi, la base d'induction est prouvée.

Étape 2 : énonce ensuite l'hypothèse d'induction. Dans ce cas, il faut utiliser l'induction forte. L'hypothèse est que pour tout \( 0 \leq i \leq k+1, \)

\[ F_i = \frac{\phi^i + \hat{\phi}^i}{\sqrt{5}}. \]

Étape 3 : Tu dois maintenant prouver l'étape d'induction, c'est-à-dire que

\[F_{k+2} = \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}}.\]

Commence par le côté droit et essaie de le simplifier jusqu'à ce que tu arrives au côté gauche. Commence par diviser la puissance de \N(k+2\N) en 2 termes distincts, l'un avec la puissance de \N(k\N) et l'autre avec la puissance de \N(2\N).

\[ \frac{\phi^{k+2}]] + \hat{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}} = \frac{\phi^2 \phi^k + \hat{\phi}^2 \hat{\phi}^k}{\sqrt{5}} \]

Maintenant, tu peux utiliser le résultat que \( \phi^2 = 1 + \phi\) et \( \hat{\phi}^2 = 1 + \hat{\phi} \).

\[ \begin{align} \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}} & = \frac{(1+\phi) \phi^{k} + (1+\hat{\phi}) \hat{\phi}^{k}}{\sqrt{5}} \\N- & = \frac{\phi^{k} + \hat{\phi}^{k} + \phi^{k+1} + \hat{\phi}^{k+1}}{\sqrt{5}} \\N- & = \frac{\phi^{k} + \hat{\phi}^{k}}{\sqrt{5}} + \frac{\phi^{k+1} + \hat{\phi}^{k+1}}{\sqrt{5}} \N- & = F_k + F_{k+1} \N- & = F_{k+2}. \Nend{align} \]

Ainsi, l'étape d'induction a été prouvée. L'étape qui permet d'obtenir la réponse à \( F_k + F_{k+1} \N) nécessite l'utilisation de l'hypothèse d'induction pour y parvenir.

Étape 4 : Enfin, la conclusion : Si la formule de Binet est valable pour tous les entiers non négatifs jusqu'à \N(k+1\N), alors la formule sera valable pour \N(k+2\N). Puisque la formule est valable pour \(F_0\) et \(F_1\), la formule sera valable pour tous les entiers non négatifs.