Introduction aux mathématiques/Exercices/Récurrences

Exercice 2-1

On considère la suite récurrente $(a_{n})_{n\in \mathbb {N} }$ définie par $a_{0}=0$ et

$\forall n\in \mathbb {N} \quad a_{n+1}=n+1+\sum _{k=0}^{n}a_{k}$.

Démontrer que $a_{n}=2^{n}-1$ pour tout $n\in \mathbb {N}$.

Solution

Notons ${\mathcal {P}}_{n}$ la propriété « $a_{n}=2^{n}-1$ ».

${\mathcal {P}}_{0}$ est vrai puisque $a_{0}=0$.

Soit $n$ un entier naturel tel que $\forall k\leq n\quad {\mathcal {P}}_{k}$, alors

$a_{n+1}=n+1+\sum _{k=0}^{n}(2^{k}-1)=\sum _{k=0}^{n}2^{k}=2^{n+1}-1$

donc ${\mathcal {P}}_{n+1}$ est vrai.

Cela termine la preuve par récurrence forte de : $\forall n\in \mathbb {N} \quad {\mathcal {P}}_{n}$.

 

Exercice 2-2

1. Montrer que modulo 7, un carré parfait ne peut être congru qu'à 0, 1, 2 ou 4.
2. En déduire que si trois entiers $x,y,z$ vérifient $x^{2}+y^{2}=7z^{2}$, alors ils sont tous les trois divisibles par 7.
3. En raisonnant par descente infinie, en déduire qu'il n'existe aucun triplet d'entiers naturels $(x,y,z)\neq (0,0,0)$ tel que $x^{2}+y^{2}=7z^{2}$.

Solution

1. Modulo 7, un carré parfait ne peut être congru qu'à $0^{2}=0$, $(\pm 1)^{2}=1$, $(\pm 2)^{2}=4$ ou $(\pm 3)^{2}=9\equiv 2{\pmod {7}}$.
2. Si le seul couple d'entiers $a,b\in \{0,1,2,4\}$ tel que $7\mid a+b$ est $(0,0)$ donc si $x^{2}+y^{2}=7z^{2}$ alors $x^{2}$ et $y^{2}$ sont divisibles par 7, donc $x$ et $y$ aussi puisque 7 est premier. Mais $7z^{2}=x^{2}+y^{2}$ est alors divisible par $7^{2}$ donc $z^{2}$ est lui aussi divisible par 7 (et donc $z$ aussi).
3. Soit (s'il en existe) $(x,y,z)\in \mathbb {N} ^{3}$ tel que $n:=x+y+z>0$ et $x^{2}+y^{2}=7z^{2}$. Alors, $(x',y',z'):=(x/7,y/7,z/7)\in \mathbb {N} ^{3}$, $x'^{2}+y'^{2}=7z'^{2}$ et $0<x'+y'+z'<n$. Par descente infinie, ceci prouve qu'il n'en existe pas.