Exercices
20 min
Non commencé
Sujet 0 – Suites et algorithmes
Exercice 8
Pour chacune des affirmations suivantes, indiquer si elle est vraie ou fausse.
Chaque réponse doit être justifiée. Une réponse non justifiée ne rapporte aucun point.
On considère la suite $ (u_n) $ définie par $ u_0 = 0 $ et $ u_{n+1} = 3u_n + 1 $ pour tout entier naturel $ n $. On considère la fonction calcul écrite dans le langage Python qui renvoie la valeur de $ u_n $ :
def calcul(n):
u = 0
for i in range(n):
u = 3 * u + 1
return uOn considère par ailleurs la fonction liste écrite dans le langage Python :
def liste(n):
l = [ ]
for i in range(n):
l.append(calcul(i))
return l- Affirmation 1 : « l’appel liste(6) renvoie la liste [0, 1, 4, 13, 42, 121]. »
- Affirmation 2 : « pour tout entier naturel $ n $, $ u_n = \dfrac{1}{2} \times 3^n - \dfrac{1}{2} $. »
- Affirmation 3 : « pour tout entier naturel $ n $, $ u_{n+1} - u_n $ est une puissance de 3. »
Corrigé
Affirmation 1 : « l’appel liste(6) renvoie la liste [0, 1, 4, 13, 42, 121]. »
Calculons les premiers termes de la suite $ (u_n) $ pour vérifier cette affirmation.
- $ u_0 = 0 $
- $ u_1 = 3u_0 + 1 = 3 \cdot 0 + 1 = 1 $
- $ u_2 = 3u_1 + 1 = 3 \cdot 1 + 1 = 4 $
- $ u_3 = 3u_2 + 1 = 3 \cdot 4 + 1 = 13 $
- $ u_4 = 3u_3 + 1 = 3 \cdot 13 + 1 = 40 $
- $ u_5 = 3u_4 + 1 = 3 \cdot 40 + 1 = 121 $
La liste obtenue pour liste(6) est donc [0, 1, 4, 13, 40, 121].
L'affirmation est donc fausse.
- Affirmation 2 : « pour tout entier naturel $ n $, $ u_n = \dfrac{1}{2} \times 3^n - \dfrac{1}{2} $. »
Nous allons démontrer cette affirmation par récurrence.
Initialisation :
Pour $ n = 0 $ :
$ u_0 = 0 $ et
$ \dfrac{1}{2} \times 3^0 - \dfrac{1}{2} = \dfrac{1}{2} \times 1 - \dfrac{1}{2} = 0 $
La formule est donc vraie pour $ n = 0 $.
Hérédité :
Supposons que pour un entier $ k $, la formule est vraie :
$ u_k = \dfrac{1}{2} \times 3^k - \dfrac{1}{2} $
Montrons qu'elle est vraie pour $ k+1 $ :
$ u_{k+1} = 3u_k + 1 $
En remplaçant $ u_k $ par son expression :
$ u_{k+1} = 3\left( \dfrac{1}{2} \times 3^k - \dfrac{1}{2} \right) + 1 $
$ u_{k+1} = \dfrac{3}{2} \times 3^k - \dfrac{3}{2} + 1 $
$ u_{k+1} = \dfrac{3^{k+1}}{2} - \dfrac{3}{2} + 1 $
$ u_{k+1} = \dfrac{3^{k+1}}{2} - \dfrac{1}{2} $
La formule est donc vraie pour $ k+1 $.
Par récurrence, la formule est vraie pour tout entier naturel $ n $.
L'affirmation est donc vraie. - Affirmation 3 : « pour tout entier naturel $ n $, $ u_{n+1} - u_n $ est une puissance de 3. »
Utilisons le résultat de l'affirmation 2 pour démontrer cette affirmation.
D'après l'affirmation 2 :
$ u_n = \dfrac{1}{2} \times 3^n - \dfrac{1}{2} $
$ u_{n+1} = \dfrac{1}{2} \times 3^{n+1} - \dfrac{1}{2} $
Calculons $ u_{n+1} - u_n $ :
$ u_{n+1} - u_n = \left(\dfrac{1}{2} \times 3^{n+1} - \dfrac{1}{2}\right) - \left(\dfrac{1}{2} \times 3^n - \dfrac{1}{2}\right) $
$ u_{n+1} - u_n = \dfrac{1}{2} \times 3^{n+1} - \dfrac{1}{2} - \dfrac{1}{2} \times 3^n + \dfrac{1}{2} $
$ u_{n+1} - u_n = \dfrac{1}{2} \times 3^{n+1} - \dfrac{1}{2} \times 3^n $
$ u_{n+1} - u_n = \dfrac{1}{2} \times 3^n \times (3 - 1) $
$ u_{n+1} - u_n = \dfrac{1}{2} \times 3^n \times 2 $
$ u_{n+1} - u_n = 3^n $
L'affirmation est donc vraie.