Streak00/3aujourd'hui

Notions de logique · Leçon 5

Raisonnement par récurrence

0score
CalculSérie · Ex 7.1

un=7n−2nu_n = 7^n - 2^n : u1=5u_1 = 5, u2=45u_2 = 45, u3=335u_3 = 335… Quel est le plus grand entier qui semble diviser tous les unu_n (n≥1n \geq 1) ?

Tous les énoncés et corrigés
  1. un=7n−2nu_n = 7^n - 2^n : u1=5u_1 = 5, u2=45u_2 = 45, u3=335u_3 = 335… Quel est le plus grand entier qui semble diviser tous les unu_n (n≥1n \geq 1) ?

    Voir le corrigé

    55

    u1=5u_1 = 5, donc le diviseur commun ne peut pas dépasser 55. Et 55 semble diviser tous les termes : c'est la conjecture à démontrer.

  2. La clé de l'hérédité

    Pour faire apparaître 7n−2n7^n - 2^n, quelle égalité est correcte ?

    Voir le corrigé
    • 7n+1−2n+1=7(7n−2n)+5⋅2n7^{n+1} - 2^{n+1} = 7(7^n - 2^n) + 5 \cdot 2^n
  3. Remets dans l'ordre (attention aux pièges) : 55 divise 7n−2n7^n - 2^n.

    Voir le corrigé
    1. Initialisation : pour n=0n = 0, 70−20=07^0 - 2^0 = 0 et 55 divise 00. Donc P(0)P(0) est vraie.
    2. Hérédité : soit n∈Nn \in \mathbb{N}. Supposons que 55 divise 7n−2n7^n - 2^n : il existe k∈Zk \in \mathbb{Z} tel que 7n−2n=5k7^n - 2^n = 5k.
    3. Alors 7n+1−2n+1=7(7n−2n)+5⋅2n=35k+5⋅2n=5(7k+2n)7^{n+1} - 2^{n+1} = 7(7^n - 2^n) + 5 \cdot 2^n = 35k + 5 \cdot 2^n = 5(7k + 2^n).
    4. Comme 7k+2n∈Z7k + 2^n \in \mathbb{Z}, 55 divise 7n+1−2n+17^{n+1} - 2^{n+1} : P(n+1)P(n+1) est vraie.
    5. Conclusion : d'après le principe de récurrence, pour tout n∈Nn \in \mathbb{N}, 55 divise 7n−2n7^n - 2^n.
  4. Touche la ligne où ce raisonnement devient faux.

    Voir le corrigé

    Ligne 5 : L'initialisation n'a pas été faite, et elle est fausse : 100+1=210^0 + 1 = 2 n'est pas divisible par 99.

    Hérédité sans initialisation = des dominos qui se feraient tomber les uns les autres… mais dont aucun n'est poussé.

  5. Pour montrer que 66 divise 72n+52n+17^{2n} + 5^{2n+1}, lesquelles de ces égalités permettent de conclure l'hérédité ?

    Voir le corrigé
    • 72n+2+52n+3=49 (72n+52n+1)−24⋅52n+17^{2n+2} + 5^{2n+3} = 49\,(7^{2n} + 5^{2n+1}) - 24 \cdot 5^{2n+1}
    • 72n+2+52n+3=25 (72n+52n+1)+24⋅72n7^{2n+2} + 5^{2n+3} = 25\,(7^{2n} + 5^{2n+1}) + 24 \cdot 7^{2n}

    Les deux premières sont correctes et 2424 est un multiple de 66. Il y a souvent plusieurs bonnes façons de faire apparaître l'hypothèse.

  6. Pour P(n)P(n) : « 77 divise 32n+1+2n+23^{2n+1} + 2^{n+2} », calcule 32n+1+2n+23^{2n+1} + 2^{n+2} pour n=0n = 0 (initialisation).

    Voir le corrigé

    77

    31+22=3+4=73^1 + 2^2 = 3 + 4 = 7, divisible par 77 : P(0)P(0) est vraie.

  7. Soit ff définie par f(0)=3f(0) = 3 et f(n+1)=2f(n)+5f(n+1) = 2f(n) + 5. Calcule f(3)f(3).

    Voir le corrigé

    5959

    f(1)=11f(1) = 11, f(2)=27f(2) = 27, f(3)=59f(3) = 59. Et 23+3−5=64−5=592^{3+3} - 5 = 64 - 5 = 59 : la formule f(n)=2n+3−5f(n) = 2^{n+3} - 5 est cohérente.

  8. Hérédité : on suppose f(n)=2n+3−5f(n) = 2^{n+3} - 5. Quel calcul de f(n+1)f(n+1) est correct ?

    Voir le corrigé

    Soit n∈Nn \in \mathbb{N}. Supposons f(n)=2n+3−5f(n) = 2^{n+3} - 5. Alors f(n+1)=2f(n)+5=2(2n+3−5)+5=2n+4−5f(n+1) = 2f(n) + 5 = 2(2^{n+3} - 5) + 5 = 2^{n+4} - 5. Donc la propriété est vraie au rang n+1n + 1.

  9. Teste 2n≥n22^n \geq n^2 pour n=0n = 0 à 44. Pour quelle valeur est-elle fausse ?

    Voir le corrigé

    33

    23=8<9=322^3 = 8 < 9 = 3^2. C'est pour cela que la récurrence est initialisée à n0=4n_0 = 4 (16≥1616 \geq 16).

  10. On suppose ∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n+1)}{2}. Quel calcul est correct ?

    Voir le corrigé
    • ∑k=1n+1k=n(n+1)2+(n+1)=(n+1)(n+2)2\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}
  11. P(n)P(n) : « 33 divise 4n−14^n - 1 ». Initialisation : calcule 40−14^0 - 1.

    Voir le corrigé

    40−1=4^0 - 1 = 00

    0=3×00 = 3 \times 0 : 33 divise 00, donc P(0)P(0) est vraie.

  12. Hérédité : on suppose 4n−1=3k4^n - 1 = 3k. Quelle écriture de 4n+1−14^{n+1} - 1 est correcte ?

    Voir le corrigé
    • 4(4n−1)+3=3(4k+1)4(4^n - 1) + 3 = 3(4k + 1)
  13. Remets dans l'ordre : pour tout n∈Nn \in \mathbb{N}, 33 divise 4n−14^n - 1.

    Voir le corrigé
    1. Initialisation : 40−1=0=3×04^0 - 1 = 0 = 3 \times 0. Vrai.
    2. Hérédité : soit n∈Nn \in \mathbb{N}. Supposons 4n−1=3k4^n - 1 = 3k avec kk entier.
    3. Alors 4n+1−1=4(4n−1)+3=3(4k+1)4^{n+1} - 1 = 4(4^n - 1) + 3 = 3(4k + 1).
    4. Donc 33 divise 4n+1−14^{n+1} - 1.
    5. Conclusion : pour tout n∈Nn \in \mathbb{N}, 33 divise 4n−14^n - 1.
  14. On suppose 1+2+22+⋯+2n=2n+1−11 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1. Alors 1+2+⋯+2n+2n+1=1 + 2 + \cdots + 2^n + 2^{n+1} =

    Voir le corrigé
    • 2n+1−1+2n+1=2n+2−12^{n+1} - 1 + 2^{n+1} = 2^{n+2} - 1
  15. On suppose 4n≥3n+14^n \geq 3n + 1. Alors 4n+1=4×4n≥12n+44^{n+1} = 4 \times 4^n \geq 12n + 4. Pourquoi 12n+4≥3(n+1)+112n + 4 \geq 3(n+1) + 1 ?

    Voir le corrigé
    • Car 12n+4−(3n+4)=9n≥012n + 4 - (3n + 4) = 9n \geq 0.
  16. La somme des carrés

    On veut montrer que pour tout n∈N∗n \in \mathbb{N}^{*} : 12+22+⋯+n2=n(n+1)(2n+1)61^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}

    1. Vérifier la formule pour n=1n = 1 et pour n=3n = 3.

    2. Démontrer la formule par récurrence.

    Voir le corrigé
    1. Pour n=1n = 1 : 12=11^2 = 1 et 1×2×36=1\dfrac{1 \times 2 \times 3}{6} = 1.

      Pour n=3n = 3 : 1+4+9=141 + 4 + 9 = 14 et 3×4×76=846=14\dfrac{3 \times 4 \times 7}{6} = \dfrac{84}{6} = 14.

    2. Initialisation. Pour n=1n = 1, la formule est vraie (question 1).

      Hérédité. Soit n≥1n \geq 1. Supposons 12+⋯+n2=n(n+1)(2n+1)61^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}. Alors :

      12+⋯+n2+(n+1)2=n(n+1)(2n+1)6+(n+1)2=(n+1)[n(2n+1)+6(n+1)]6=(n+1)(2n2+7n+6)61^2 + \cdots + n^2 + (n+1)^2 = \frac{n(n+1)(2n+1)}{6} + (n+1)^2 = \frac{(n+1)\big[n(2n+1) + 6(n+1)\big]}{6} = \frac{(n+1)(2n^2 + 7n + 6)}{6}

      Or (n+2)(2n+3)=2n2+7n+6(n + 2)(2n + 3) = 2n^2 + 7n + 6. Donc la somme vaut (n+1)(n+2)(2n+3)6\dfrac{(n+1)(n+2)(2n+3)}{6} : c'est la formule au rang n+1n + 1.

      Conclusion. Pour tout n∈N∗n \in \mathbb{N}^{*} : 12+22+⋯+n2=n(n+1)(2n+1)61^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}.

  17. Deux divisibilités par récurrence

    Démontrer chaque propriété par récurrence.

    1. Pour tout n∈Nn \in \mathbb{N}, 44 divise 5n−15^n - 1.

    2. Pour tout n∈Nn \in \mathbb{N}, 33 divise n3+2nn^3 + 2n.

    Voir le corrigé
    1. Initialisation. Pour n=0n = 0 : 50−1=0=4×05^0 - 1 = 0 = 4 \times 0. Vrai.

      Hérédité. Soit n∈Nn \in \mathbb{N}. Supposons que 44 divise 5n−15^n - 1 : 5n−1=4k5^n - 1 = 4k avec k∈Nk \in \mathbb{N}. Alors : 5n+1−1=5×5n−1=5(5n−1)+4=20k+4=4(5k+1)5^{n+1} - 1 = 5 \times 5^n - 1 = 5(5^n - 1) + 4 = 20k + 4 = 4(5k + 1) Donc 44 divise 5n+1−15^{n+1} - 1.

      Conclusion. Pour tout n∈Nn \in \mathbb{N}, 44 divise 5n−15^n - 1.

    2. Initialisation. Pour n=0n = 0 : 0=3×00 = 3 \times 0. Vrai.

      Hérédité. Soit n∈Nn \in \mathbb{N}. Supposons n3+2n=3kn^3 + 2n = 3k avec k∈Nk \in \mathbb{N}. Alors : (n+1)3+2(n+1)=n3+3n2+3n+1+2n+2=(n3+2n)+3(n2+n+1)=3(k+n2+n+1)(n+1)^3 + 2(n+1) = n^3 + 3n^2 + 3n + 1 + 2n + 2 = (n^3 + 2n) + 3(n^2 + n + 1) = 3\big(k + n^2 + n + 1\big) Donc 33 divise (n+1)3+2(n+1)(n+1)^3 + 2(n+1).

      Conclusion. Pour tout n∈Nn \in \mathbb{N}, 33 divise n3+2nn^3 + 2n.