Chapitre 2Raisonnement par récurrence

On note $P(n)$ la proposition : $\displaystyle{S_n=\frac{n(n+1)}{2}}$.

1. On vérifie que $P(0)$ est vraie.
2. Soit $k$ un entier naturel. On suppose $P(k)$ vraie, c’est à dire :\[\sum\limits_{i=0}^{k}{i}=0+1+2+3+\ldots+k=\frac{k(k+1)}{2}\quad\text{(Hypothèse de récurrence)}\]On va montrer que cette propriété est encore vraie au rang $(k+1)$.\[\begin{align*}\sum\limits_{i=0}^{k+1}{i}&=0+1+2+3+\ldots+k+(k+1)=\frac{k(k+1)}{2}+(k+1) \\&=\frac{(k+1)(k+2)}{2}\end{align*}\]Donc $P(k+1)$ est vraie.
3. $P(n)$ est donc vraie pour tout entier naturel, c’est-à-dire :
   \[\text{Pour tout entier naturel, }0+1+2+3+\ldots+n=\sum\limits_{i=0}^{n}{i}=\frac{n(n+1)}{2}.\]

• 1. On vérifie que $R(0)$ est vraie : $3^0-1=0$ et $3$ divise $0$.
  2. Soit $k$ un entier naturel. On suppose $R(k)$ vraie, c’est à dire :\[3\text{ divise }4^k-1\quad\text{(Hypothèse de récurrence)}\]Donc, il existe un entier $p$ tel que $4^k-1=3p$.
     On va montrer que cette propriété est encore vraie au rang $(k+1)$.\[\begin{align*}4^{k+1}-1&=4(4^k)-1=4(3p+1)-1=12p+4-1=12p+3 \\&=3(4p+1).\end{align*}\]Comme $4p+1$ est un entier, nous en déduisons que $3$ divise $4{k+1}-1$ et donc $R(k+1)$ est vraie.
  3. $R(n)$ est donc vraie pour tout entier naturel, c’est-à-dire :
     \[\text{Pour tout entier naturel, }3\text{ divise }4^n-1.\]
• Montrons que $Q(n)$ est héréditaire.
  Soit $k$ un entier naturel. On suppose $Q(k)$ vraie, c’est à dire :\[3\text{ divise }4^k+1\quad\text{(Hypothèse de récurrence)}\]Donc, il existe un entier $p$ tel que $4^k+1=3p$
  On va montrer que cette propriété est encore vraie au rang $(k+1)$.\[\begin{align*}4^{k+1}+1&=4(4^k)+1=4(3p-1)+1=12p-4+1=12p-3 \\&=3(4p-1).\end{align*}\]Comme $4p-1$ est un entier, nous en déduisons que $3$ divise $4^{k+1}+1$ et donc $Q(k+1)$ est vraie.
  Nous avons montré que $Q(n)$ est une propriété héréditaire.
• $Q(0)$ est la propriété : $3\text{ divise }4^0+1$, c’est-à-dire $3$ divise $2$. Propriété fausse…
  Nous remarquons ici l’importance de vérifier la fondation de la propriété.

On note $P(n)$ la proposition :\[\sum\limits_{i=0}^{n}{i^3}=\frac{n^2{(n+1)}^2}{4}.\]

1. On vérifie que $P(0)$ est vraie.
   Ici, $\displaystyle{\sum\limits_{i=0}^{0}{i^3}=0}$ et $\displaystyle{\frac{0^2{(0+1)}^2}{4}=0}$. Nous avons bien, $\displaystyle{\sum\limits_{i=0}^{0}{i^3}=\frac{0^2(0+1)^2}{4}}$.
2. Soit $k$ un entier naturel. On suppose $P(k)$ vraie, c’est à dire :\[\sum\limits_{i=0}^{k}{i^3}=\frac{k^2{(k+1)}^2}{4}\quad\text{(Hypothèse de récurrence)}\]On va montrer que cette propriété est encore vraie au rang $(k+1)$.\[\sum\limits_{i=0}^{k+1}{i^3}=\sum\limits_{i=0}^{k}{i^3}+k^3=\frac{k^2{(k+1)}^2}{4}+k^3=\frac{{(k+1)}^2{(k+2)}^2}{4}\]Donc $P(k+1)$ est vraie.
3. $P(n)$ est donc vraie pour tout entier naturel, c’est-à-dire :
   \[\text{Pour tout entier naturel, }\sum\limits_{i=0}^{n}{i^3}=\frac{n^2{(n+1)}^2}{4}.\]

On note $P(n)$ la proposition : $2^n\ge n^2$.

1. On vérifie que $P(4)$ est vraie : $24\ge 42$.
2. Soit $k$ un entier naturel. On suppose $P(k)$ vraie, c’est à dire :\[2^k\ge k^2\quad\text{(Hypothèse de récurrence)}\]On va montrer que cette propriété est encore vraie au rang $(k+1)$.
   \[2^{k+1}=2\times 2^k\ge 2k^2.\]Or, $2k^2\ge (k+1)^2$. Donc, $2{k+1}\ge (k+1)^2$ et $P(k+1)$ est vraie.
3. $P(n)$ est donc vraie pour tout entier naturel supérieur (ou égal) à $4$, c’est-à-dire :\[\text{Pour tout entier naturel supérieur (ou égal) à $4$, }2^n\ge n^2.\]

On note $P(n)$ la proposition : $f^{(2n)}(x)=(-4)^n\sin(2x)$.

1. On vérifie que $P(0)$ est vraie.\[f^{(0)}(x)=\sin(2x)\text{ et }(-4)^0\sin(2x)=\sin(2x).\]Donc, nous avons : $f^{(0)}(x)=(-4)^0\sin(2x)$.
2. Soit $k$ un entier naturel. On suppose $P(k)$ vraie, c’est à dire :\[f^{(2k)}(x)=(-4)^k\sin(2x)\quad\text{(Hypothèse de récurrence)}\]On va montrer que cette propriété est encore vraie au rang $(k+1)$.\[\eqalign{(f)^{\bigl(2(k+1)\bigr)}(x)&=\left((f)^{(2k)}\right)^{\prime\prime}(x)=\left((-4)^k\sin(2x) \right)^{\prime\prime}\cr&=(-4)^k 2\bigl(\cos(2x)\bigr)’=(-4)^{k+1}\sin(2x).}\]Donc $P(k+1)$ est vraie.
3. $P(n)$ est donc vraie pour tout entier naturel, c’est-à-dire :
   \[\text{Pour tout entier naturel, }f^{(2n)}(x)=(-4)^n\sin(2x).\]

On note $P(n)$ la proposition : $n^2+n+2$ est un nombre pair, c’est-à-dire :\[\exists i\in \N,\ n^2+n+2=2i\]

1. On vérifie que $P(0)$ est vraie : $0^2+0+2=2\times 1$.
2. Soit $k$ un entier naturel. On suppose $P(k)$ vraie, c’est à dire :\[\exists i\in \N,\ k^2+k+2=2i\quad\text{(Hypothèse de récurrence)}\]On va montrer que cette propriété est encore vraie au rang $(k+1)$.\[\begin{align*}(k+1)^2+(k+1)+2&=k^2+2k+1+k+1+2 \\&=(k^2+k+2)+2k+2 \\&=2i+2(k+1) \\&=2(i+k+1).\end{align*}\]Donc $P(k+1)$ est vraie.
3. $P(n)$ est donc vraie pour tout entier naturel, c’est-à-dire :
   \[\text{Pour tout entier naturel, }n^2+n+2\text{ est un nombre pair}.\]