Exercices – Raisonnement par récurrence

Raisonnement par récurrence

Fiche TS-rec1

Exercice 1

Démontrer que pour tout entier naturel $n$ on a :

$$S_n = \sum_{k=0}^{n} k = 0 + 1 + 2 +\ldots+n = \dfrac{n(n+1)}{2}$$

$\quad$

Correction Exercice 1

Initialisation : Pour $n=0$ $S_n =0$ et $\dfrac{0 \times (0+1)}{2} = 0$.

la propriété est vraie au rang $0$.

Hérédité : Supposons la propriété vraie au rang $n$. On a donc $S_n = \dfrac{n(n+1)}{2}$.

$\begin{align} S_{n+1} &= 0+1+2+\ldots+n+(n+1) \\\\
&= S_n + (n+1) \\\\
&= \dfrac{n(n+1)}{2} + n+1\\\\
&= \dfrac{n(n+1)+2(n+1)}{2}\\\\
&= \dfrac{(n+1)(n+2)}{2}
\end{align}$

La propriété est donc vraie au rang $n+1$.

Conclusion : La propriété est vraie au rang $0$. En la supposant vraie au rang $n$, elle est encore vraie au rang suivant.

Par conséquent, pour tout $n \in \N$ on a $S_n = \dfrac{n(n+1)}{2}$.

[collapse]

$\quad$

Exercice 2

Démontrer par récurrence que pour tout entier $n \ge 1$, on a :

$$ S_n = \sum_{k=1}^{n} k^2 = 1^2+2^2+\ldots+n^2 = \dfrac{n(n+1)(2n+1)}{6}$$

$\quad$

Correction Exercice 2

Initialisation : Si $n=1$ alors $S_1=1^2 = 1$ et $\dfrac{1(1+1)(2\times 1 + 1)}{6} = 1$.

La propriété est vraie au rang $1$.

Hérédité : Supposons la propriété vraie au rang $n$ : $S_n = \dfrac{n(n+1)(2n+1)}{6}$.

$\begin{align} S_{n+1} &= 1^2+2^2+\ldots+n^2+(n+1)^2 \\\\
&= S_n + (n+1)^2 \\\\
&= \dfrac{n(n+1)(2n+1)}{6} + (n+1)^2 \\\\
&= \dfrac{n(n+1)(2n+1)+6(n+1)^2}{6} \\\\
&= \dfrac{(n+1)\left[n(2n+1)+6(n+1)\right]}{6}\\\\
&=\dfrac{(n+1)(2n^2+n+6n+6)}{6}\\\\
&=\dfrac{(n+1)(2n^2+7n+6)}{6} \quad (1)
\end{align}$

On voulait montrer que $S_{n+1} = \dfrac{(n+1)(n+1+1)\left(2(n+1)+1\right)}{6} = \dfrac{(n+1)(n+2)(2n+3)}{6}$.

Développons $(n+2)(2n+3) = 2n^2+3n+4n+6=2n^2+7n+6$.

Par conséquent, en revenant dans $(1)$ on a $S_{n+1} = \dfrac{(n+1)(n+2)(2n+3)}{6}$.

La propriété est vraie au rang $n+1$.

Conclusion : La propriété est vraie au rang $1$. En supposant la propriété vraie au rang $n$ elle est encore vraie au rang suivant.

Par conséquent, pour entier $n \ge 1$ on a $S_n = \dfrac{n(n+1)(2n+1)}{6}$.

[collapse]

$\quad$

Exercice 3

Démontrer par récurrence que pour tout entier $n \ge 1$, on a :

$$S_n = \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} + \dfrac{1}{3 \times 4} + \ldots + \dfrac{1}{n(n+1)} = 1 – \dfrac{1}{n+1}$$

$\quad$

Correction Exercice 3

Initialisation : Si $n=1$ alors $S_1 = \dfrac{1}{1\times (1+1)} = \dfrac{1}{2}$.

Or $1-\dfrac{1}{1+1} = \dfrac{1}{2}$.

La propriété est donc vraie au rang $1$.

Hérédité : Supposons la propriété vraie au rang $n$ :

$S_n = \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} + \dfrac{1}{3 \times 4} + \ldots + \dfrac{1}{n(n+1)} = 1 – \dfrac{1}{n+1}$

Au rang $n+1$ on a donc :

$\begin{align} S_{n+1}&= \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} + \dfrac{1}{3 \times 4} + \ldots + \dfrac{1}{n(n+1)} + \dfrac{1}{(n+1)(n+2)}\\\\
& = 1-\dfrac{1}{n+1} + \dfrac{1}{(n+1)(n+2)} \\\\
&=1-\dfrac{n+2}{(n+1)(n+2)} + \dfrac{1}{(n+1)(n+2)} \\\\
&=1-\dfrac{n+2}{(n+1)(n+2)}-\dfrac{-1}{(n+1)(n+2)} \\\\
&=1-\dfrac{n+2-1}{(n+1)(n+2)}\\\\
&=1-\dfrac{n+1}{(n+1)(n+2)} \\\\
&=1-\dfrac{1}{n+2}
\end{align}$

La propriété est donc vraie au rang $n+1$.

Conclusion : La propriété est vraie au rang $1$. En la supposant vraie au rang $n$, elle est encore vraie au rang suivant.

Par conséquent, pour tout entier naturel $n \ge 1$ on a $S_n = 1 – \dfrac{1}{n+1}$

[collapse]

$\quad$

Exercice 4

Soit $(u_n)$ une suite définie par $u_0 = 1$ et $u_{n+1} = \sqrt{2 + u_n}$ pour tout $n\in \N$.

Démontrer que, pour tout $n \in \N$, $0 < u_n <2$.

$\quad$

Correction Exercice 4

Initialisation : $u_0 = 1$ donc $0<u_0\le 2$.

La propriété est vraie au rang $0$.

Hérédité : Supposons la propriété vraie au rang $n$ : $0<u_n < 2$.

Donc $2<2+u_n < 4$ et $\sqrt{2} < \sqrt{2+u_n}<\sqrt{4}$

Finalement $0 < \sqrt{2} < u_{n+1} < 2$

La propriété est vraie au rang $n+1$

Conclusion : La propriété est vraie au rang $0$. En la supposant vraie au rang $n$, elle est encore vraie au rang suivant.

Par conséquent, pour tout $n \in \N$, $0 < u_n <2$.

[collapse]

$\quad$

 Exercice 5

Soit $(u_n)$ une suite définie par $u_0 = 2$ et $u_{n+1} = \dfrac{u_n}{1+u_n}$.

Démontrer que pour tout $n \in \N$, $u_n = \dfrac{2}{2n+1}$.

$\quad$

Correction Exercice 5

Initialisation : Si $n=0$ alors $u_0 = 2$ et $\dfrac{2}{2\times 0 + 1} = 2$.

La propriété est donc vraie au rang $0$.

Hérédité : Supposons la propriété vraie au rang $n$ : $u_n =  \dfrac{2}{2n+1}$.

Alors :

$\begin{align} u_{n+1} & = \dfrac{u_n}{1+u_n} \\\\
&= \dfrac{\dfrac{2}{2n+1}}{1+\dfrac{2}{2n+1}} \\\\
&= \dfrac{2}{2n+1 + 2}\\\\
&= \dfrac{2}{2n+3}\\\\
&=\dfrac{2}{2(n+1)+1}
\end{align}$

La propriété est donc vraie au rang $n+1$.

Conclusion : La propriété est vraie au rang $0$. En la supposant vraie au rang $n$ elle est encore vraie au rang suivant.

Par conséquent, pour tout $n \in \N$ on a $ u_n = \dfrac{2}{2n+1}$.

[collapse]

$\quad$

Exercice 6

Soit $(u_n)$ une suite définie par $u_0 = 3$ et $u_{n+1} = 2u_n – 1$ pour tout $n \in \N$.

Démontrer que, pour tout $n \in \N$, $u_n = 2^{n+1}+1$.

$\quad$

Correction Exercice 6

Initialisation : Si $n=0$, $u_0=3$ et $2^{0+1}+1 = 2 + 1 =3$.

La propriété est vraie au rang $0$.

Hérédité : Supposons la propriété vraie au rang $n$. $u_n = 2^{n+1}+1$.

$\begin{align} u_{n+1} &= 2u_n – 1 \\\\
&= 2 \times \left( 2^{n+1}+1 \right) – 1 \\\\
&= 2^{n+2} + 2 – 1 \\\\
& = 2^{n+2} + 1
\end{align}$

La propriété est donc vraie au rang $n+1$.

Conclusion : La propriété est vraie au rang $0$. En la supposant vraie au rang $n$, elle est encore vraie au rang suivant.

Par conséquent, pour tout $n\in \N$ on a $u_n = 2^{n+1}+1$.

[collapse]

$\quad$

Exercice 7

Soit $(u_n)$ une suite définie par $u_0=0$ et $u_{n+1} = \dfrac{1+2u_n}{2+u_n}$.

Démontrer que pour tout $n \in \N^*$ on a $ 0 < u_n \le 1$.

$\quad$

Correction Exercice 7

Initialisation : Si $n=1$ alors $u_1 = \dfrac{1+2u_0}{2+u_0} = \dfrac{1}{2}$ . Donc $0<u_1\le 1$.

La propriété est vraie au rang $1$.

Hérédité : Supposons la propriété vraie au rang $n$. Donc $ 0 < u_n \le 1$.

On a donc :

  • $u_n > 0$ donc $1+2u_n > 0$ et $2+u_n > 0$. Par conséquent $u_{n+1} > 0$
  • $u_{n+1} – 1 = \dfrac{1+2u_n}{2+u_n} – 1 = \dfrac{u_n-1}{2+u_n}$
    Or $u_n  \le 1$ cela signifie donc que $u_n-1 \le 0$ et par conséquent $u_{n+1} – 1 \le 0$.

La propriété est donc vraie au rang $n+1$.

Conclusion : La propriété est vraie au rang $1$. En la supposant vraie au rang $n$, elle est vraie au rang suivant.

Par conséquent, pour tout $n \in \N^*$ on a $ 0 < u_n \le 1$.

[collapse]

$\quad$

Exercice 8 (ROC)

Soit $a\in \R^+$. Démontrer que pour tout $n \in \N$ on a $(1+a)^n \ge 1+na$

$\quad$

Correction Exercice 8

Initialisation : si $n=0$ alors $(1+a)^0 = 1$ et $1+ 0 \times a = 1$. $1 \ge 1$.

La propriété est donc vraie au rang $0$.

Hérédité : Supposons la propriété vraie au rang $n$. On a donc $(1+a)^n \ge 1+na$.

$\begin{align} (1+a)^{n+1} &= (1+a) \times (1+a)^n \\\\
& \ge (1+a) \times (1+na) \\\\
& \ge 1 + na + a + na^2 \\\\
& \ge 1 + (n+1)a + na^2
\end{align}$

Or $na^2 \ge 0$ donc $(1+a)^{n+1} \ge 1 + (n+1)a$.

La propriété est donc vraie au rang $n+1$.

Conclusion : La propriété est vraie au rang $0$. En la supposant vraie au rang $n$ elle est encore vraie au rang suivant.

Par conséquent, pour tout $n \in \N$ on a $(1+a)^n \ge 1+na$.

[collapse]

$\quad$

Exercice 9

Soit $f $ la fonction définie par $f(x) = \dfrac{1}{1-x}$ pour tout $x \ne 1$.

Démontrer que, pour tout entier $n \ge 1$,  $f^{(n)}(x) = \dfrac{n!}{(1-x)^{n+1}}$ où $f^{(n)}$ désigne la dérivée $n^{\text{ième}}$ de $f$ et $n! = 1\times 2\times 3\times \ldots \times n$.

$\quad$

Correction Exercice 9

Initialisation :  $f$ est dérivable sur $I=]-\infty;1[ \cup ]1;+\infty[$ comme quotient de fonctions dérivables sur $I$.

Si $n= 1$ alors $f'(x) = \dfrac{-(-1)}{(1-x)^2}$ et $\dfrac{1!}{(1-x)^{1+1}} = \dfrac{1}{(1-x)^{2}}$.

La propriété est donc vraie au rang $1$.

Hérédité : Supposons la propriété vraie au rang $n$. $f^{(n)} = \dfrac{n!}{(1-x)^{n+1}}$.

La fonction $f^{(n)}$ est dérivable sur $I$.

$\begin{align} f^{(n+1)}(x) &= \left( f^{(n)}\right)’ (x)  \\\\
&= \dfrac{-n! \times (n+1) \times (-1) \times (1-x)^n}{(1-x)^{2(n+1)}} \\\\
&= \dfrac{(n+1)! \times (1-x)^n}{(1-x)^{2n+2}} \\\\
&=\dfrac{(n+1)!}{(1-x)^{n+2}} \\\\
&=\dfrac{(n+1)!}{(1-x)^{(n+1)+1}}
\end{align}$

La propriété est donc vraie au rang $n+1$.

Conclusion : La propriété est vraie au rang $1$. En la supposant vraie au rang $n$ elle est encore vraie au rang suivant.

Par conséquent, pour tout entier $n \ge 1$, on a $f^{(n)} = \dfrac{n!}{(1-x)^{n+1}}$.

[collapse]

$\quad$

Exercice 10 (Spécialité)

Démontrer que pour tout $n \in \N$, $10^n -1$ est un multiple de $9$.

$\quad$

Correction Exercice 10

Initialisation : Si $n=0$ alors $10^0-1=1-1 = 0$ est bien un multiple de $9$.

La propriété est donc vraie au rang $0$.

Hérédité : Supposons la propriété vraie au rang $n$.

Il existe alors un entier relatif $k$ tel que $10^n -1=9k$ soit $10^n=9k+1$.

$\begin{align} 10^{n+1} -1 &= 10^n\times 10-1 \\\\
&= (9k+1) \times 10 – 1 \\\\
&= 9 \times 10k + 10 – 1 \\\\
&=9 \times 10k + 9
\end{align}$

Par conséquent $10^{n+1}-1$ est bien un multiple de $9$. La propriété est donc vraie au rang $n+1$.

Conclusion : La propriété est vraie au rang $0$. En la supposant vraie au rang $n$ elle est encore vraie au rang suivant.

Par conséquent, pour tout entier naturel $n$, $10^n -1$ est un multiple de $9$.

[collapse]

$\quad$

Exercice 11 (Spécialité)

On considère les propositions suivantes :

$P(n)$ : “$4^n-1$ est divisible par $3$”

$Q(n)$ : “$4^n+1$ est divisible par $3$”

  1. Montrer que les propositions $P(n)$ et $Q(n)$ sont héréditaires.
  2. Montrer que $P(n)$ est vraie pour tout $n\in \N$.
  3. Que peut-on dire pour $Q(n)$?

$\quad$

Correction Exercice 11

  1. Pour $P(n)$ :
    Supposons la propriété vraie au rang $n$ : “$4^n-1$ est divisible par $3$”.
    Il existe donc un entier relatif $k$ tel que $4^n-1 = 3k$ soit $4^n = 1+3k$.
    Par conséquent :
    $\begin{align} 4^{n+1} -1&= 4^n\times 4 -1\\\\
    &= 4(1+3k) -1\\\\
    &=4 + 3\times 4k – 1\\\\
    &=3+3\times 4k
    \end{align}$
    Donc $4^{n+1}-1$ est bien divisible par $3$.
    $\quad$
    Pour $Q(n)$ :
    Supposons la propriété vraie au rang $n$ : $4^n+1$ est divisible par $3$”.
    Il existe donc un entier relatif $k$ tel que $4^n+1=3k$ soit $4^n=3k-1$.
    Par conséquent :
    $\begin{align} 4^{n+1}+1 &= 4^n\times 4 + 1 \\\\
    &= 4(3k-1)+1 \\\\
    &= 3 \times 4k – 4 + 1\\\\
    &= 3\times 4k – 3
    \end{align}$
    Donc $4^n+1$ est divisible par $3$”.
    $\quad$
    Les  propositions $P(n)$ et $Q(n)$ sont héréditaires.
    $\quad$
  2. Regardons si $P(0)$ est vraie : $4^0-1 = 1 – 1 = 0$ est bien divisible par $3$.
    La propriété est donc vraie au rang $0$. Puisqu’elle est également héréditaire, la propriété est vraie pour tout $n \in \N$.
    $\quad$
  3. Regardons si $Q(0)$ est vraie : $4^0 + 1 = 1 + 1 = 2$. $Q(0)$ est fausse.
    D’une manière générale : $4 \equiv 1~[3]$ donc $4^n \equiv 1^n \equiv 1~[3]$
    Par conséquent $4^n+1 \equiv 2~[3]$.
    La propriété $Q(n)$, bien qu’héréditaire, n’est jamais vraie.

[collapse]

$\quad$

Exercice 12

Démontrer par récurrence que pour tout entier $n \ge 1$, on a :

$$ S_n = \sum_{k=1}^{n} k^3 = 1^3+2^3+\ldots+n^3 = \dfrac{n^2(n+1)^2}{4}$$

$\quad$

Correction Exercice 12

Initialisation : Si $n=1$ alors $S_n=1$ et $\dfrac{1^2\times (1+1)^2}{4}=1$

La propriété est vraie au rang $1$.

$\quad$

Hérédité : On suppose la propriété vraie au rang $n$ : $S_n = \displaystyle \sum_{k=1}^{n} k^3 = 1^3+2^3+\ldots+n^3 = \dfrac{n^2(n+1)^2}{4}$

$\begin{align*}S_{n+1}&=1^3+2^3+\ldots+n^3+(n+1)^3 \\
&=S_n+(n+1)^3 \\
&=\dfrac{n^2(n+1)^2}{4}+(n+1)^3\\
&=(n+1)^2 \times \left(\dfrac{n^2}{4}+n+1\right) \\
&=(n+1)^2\times \dfrac{n^2+4n+4}{4} \\
&=(n+1)^2\times \dfrac{(n+2)^2}{4}
\end{align*}$

La propriété est donc vraie au rang $n+1$.

$\quad$

Conclusion : La propriété est vraie au rang $1$ et est héréditaire.
Par conséquent, pour tout entier $n \ge 1$, on a : $ S_n = \displaystyle \sum_{k=1}^{n} k^3 = 1^3+2^3+\ldots+n^3 = \dfrac{n^2(n+1)^2}{4}$

[collapse]

$\quad$

Exercice 13

On considère une suite $\left(u_n\right)$ définie par $\begin{cases}u_0=1\\u_{n+1}=\sqrt{1+u_n} \quad \forall n\in \N \end{cases}$.

$\quad$

Démontrer que la suite $\left(u_n\right)$ est croissante.

$\quad$

Correction Exercice 13

On veut donc démontrer que, pour tout entier naturel $n$ on a $u_n\pp u_{n+1}$

Initialisation : Si $n=0$ alors $u_0=1$ et $u_1=\sqrt{u_0+1}=\sqrt{2}$
On a bien $u_0<u_1$
La propriété est vraie au rang $0$.

$\quad$

Hérédité : On suppose la propriété vraie au rang $n$ : $u_n\pp u_{n+1}$
$\begin{align*} u_n\pp  u_{n+1} &\ssi u_n+1 \pp u_{n+1}+1 \\
&\ssi \sqrt{u_n+1} \pp \sqrt{u_{n+1}+1} \quad (*)\\
&\ssi u_{n+1} \pp u_{n+2}
\end{align*}$
$(*)$ par croissance de la fonction racine carrée.

La propriété est donc vraie au rang $n+1$

$\quad$

Conclusion : La propriété est vraie au rang $0$ et est héréditaire.
Par conséquent  la suite $\left(u_n\right)$ est croissante.

[collapse]