Le cas de base, \(S(1): [1(1 + 1)(2(1) + 1)]/6 = 1 = 1^2\) est vrai. Supposons que \(S(k): 1^2 + 2^2 + \cdots + k^2 = [k(k + 1)(2k + 1)]/6\) est vraie. Alors
Le cas de base, \(S(4): 4! = 24 \gt 16 =2^4\) est vrai. Supposons que \(S(k): k! \gt 2^k\) est vraie. Alors \((k + 1)! = k! (k + 1) \gt 2^k \cdot 2 = 2^{k + 1}\text{,}\) donc \(S(k + 1)\) est vraie. Ainsi, \(S(n)\) est vraie pour tout entier positif \(n\text{.}\)
Soit \(X\) un ensemble. Définissons l’ensemble des parties de \(X\text{,}\) noté \({\mathcal P}(X)\text{,}\) comme l’ensemble de tous les sous-ensembles de \(X\text{.}\) Par exemple,
Montrez que le principe du bon ordre pour les entiers naturels implique que 1 est le plus petit entier naturel. Utilisez ce résultat pour montrer que le principe du bon ordre implique le principe de récurrence ; c’est-à-dire, montrez que si \(S \subset {\mathbb N}\) est tel que \(1 \in S\) et \(n + 1 \in S\) chaque fois que \(n \in S\text{,}\) alors \(S = {\mathbb N}\text{.}\)
Pour chacune des paires d’entiers \(a\) et \(b\) suivantes, calculez \(\gcd(a,b)\) et trouvez des entiers \(r\) et \(s\) tels que \(\gcd(a,b) = ra + sb\text{.}\)
Soient \(a\) et \(b\) des entiers non nuls. S’il existe des entiers \(r\) et \(s\) tels que \(ar + bs =1\text{,}\) montrez que \(a\) et \(b\) sont premiers entre eux.
Montrez que \(\phi = \lim_{n \rightarrow \infty} f_{n + 1} / f_n = (\sqrt{5} + 1)/2\text{.}\) La constante \(\phi\) est connue sous le nom de nombre d’or.
Pour (a) et (b), utilisez le raisonnement par récurrence. (c) Montrez que \(f_1 = 1\text{,}\)\(f_2 = 1\text{,}\) et \(f_{n + 2} = f_{n + 1} + f_n\text{.}\) (e) Utilisez la partie (b) et l’Exercice 2.4.16.
Soient \(x, y \in {\mathbb N}\) premiers entre eux. Si \(xy\) est un carré parfait, montrez que \(x\) et \(y\) doivent tous deux être des carrés parfaits.
En utilisant l’algorithme de la division, montrez que tout carré parfait est de la forme \(4k\) ou \(4k + 1\) pour un certain entier non négatif \(k\text{.}\)
Soit \(n \in {\mathbb N}\text{.}\) Utilisez l’algorithme de la division pour montrer que tout entier est congru mod \(n\) à exactement l’un des entiers \(0, 1, \ldots, n-1\text{.}\) Concluez que si \(r\) est un entier, il existe exactement un \(s\) dans \({\mathbb Z}\) tel que \(0 \leq s \lt n\) et \([r] = [s]\text{.}\) Ainsi, les entiers sont bien partitionnés par la congruence mod \(n\text{.}\)
Définissons le plus petit commun multiple de deux entiers non nuls \(a\) et \(b\text{,}\) noté \(\lcm(a,b)\text{,}\) comme l’entier non négatif \(m\) tel que \(a\) et \(b\) divisent \(m\text{,}\) et si \(a\) et \(b\) divisent un autre entier \(n\text{,}\) alors \(m\) divise aussi \(n\text{.}\) Montrez qu’il existe un unique plus petit commun multiple pour deux entiers quelconques \(a\) et \(b\text{.}\)
Tout nombre premier est de la forme \(2\text{,}\)\(3\text{,}\)\(6n + 1\text{,}\) ou \(6n + 5\text{.}\) Supposons qu’il n’existe qu’un nombre fini de nombres premiers de la forme \(6k + 5\text{.}\)
En utilisant le fait que \(2\) est premier, montrez qu’il n’existe pas d’entiers \(p\) et \(q\) tels que \(p^2 = 2 q^2\text{.}\) Déduisez-en que \(\sqrt{2}\) ne peut pas être un nombre rationnel.
