Récurrences

Exercice 571. Inégalité de Bernoulli

\\ Montrer que pour tout $n \in \N$, $\forall x \in \R^{+}$, $(1+x)^n \geqslant 1+nx$.
Exercice 572. Soit $\theta \in \R$. \\ Montrer que pour tout $n \in \N$, on a $\left| \sin(n\theta) \right| \leqslant n \left| \sin(\theta) \right|$.

Exercice 573. Nombres de Pierre de Fermat

\\ On définit la suite $(F_n)$ par $F_n = 2^{2^n}+1$ pour tout entier naturel $n$. \\
  1. Montrer que pour tout entier naturel $n$, $F_{n+1} = (F_n-1)^2+1$. \\
  2. Montrer que pour tout entier naturel $n$ non nul, $F_n-2 = \displaystyle \prod_{k=0}^{n-1} F_k$.
Exercice 574. Montrer que pour tout $n \in \N$, $6$ divise $7^n-1$.
Exercice 575. Montrer que $\forall n \in \N^*$, $2^{n-1} \leqslant n! \leqslant n^n$.

Exercice 576. Suite de Fibonacci

\\ On considère la suite de fibonacci notée $(F_n)$ définie par $F_0=F_1=1$ et pour tout $n \geqslant 0$, \[ F_{n+2} = F_{n+1} + F_{n} \] Montrer que la suite $(F_n)$ vérifie pour tout $n \in \N$, $F_nF_{n+2} -F_{n+1}^2 = (-1)^n$.
Exercice 577. Soit $\un$ définie par $u_0 = 1$ et pour tout $n \geqslant 0$, \[ u_{n+1} = u_0 +u_1 +\hdots+u_n \] Montrer que pour tout $n\geqslant 1$, $u_n = 2^{n-1}$.
Exercice 578. Montrer que pour tout entier $n \geqslant 2$, $1 + \dfrac{1}{2^2} + \cdots + \dfrac{1}{n^2} > \dfrac{3n}{2n+1}$.
Exercice 579. \\ Soit $x \in \R^*$ tel que $x + \Frac{1}{x}$ soit un entier. \\ Montrer que pour tout $n \in \N$, $x^n+\Frac{1}{x^n}$ est un entier.
Exercice 580. On s'intéresse à la forme développée de $(2+\sqrt{3})^n$. \\ Montrer qu'il existe deux suites d'entiers naturels $a_n$ et $b_n$ telles que pour tout $n \in \N$, $(2+\sqrt{3})^n = a_n + b_n \sqrt{3}$.
Exercice 581. Soient $c$ un réel et $u$ la suite définie par \[ u_0 = c \; \; et \; \; \forall n \in \N, \; u_{n+1} = \Frac{1}{n+1}\sum_{k=0}^{n}u_ku_{n-k} \] Calculer $u_1$ et $u_2$. Quelle conjecture simple en déduit-on sur la valeur de $u_n$ ? La prouver.
Exercice 582. Montrer que pour tout $x \in \R_{+}$, pour tout $n \in \N$, on a \[ e^x \geqslant 1+x+\hdots+\Frac{x^n}{n!} \]
Exercice 583. Soit $\un$ une suite à valeur dans $\N$ telle que pour tout $n \in \N$, \[ u_{n+1} = \Frac{u_0+u_1+\hdots+u_n}{n+1} \] Montrer que $\un$ est constante.
Exercice 584. On considère $n$ réels $x_1,\hdots,x_n$ et $f$ l'application définie sur $\R$ par \[ \forall k \in \llbracket 2, n \rrbracket, \;\; f(x_k) = x_{k-1} \quad et \;\; f(x_1) = x_n \] On note $f^{(k)} = f \circ f \circ \hdots \circ f$, $k$-fois. \\ Exprimer pour tout naturel $k \in \llbracket 1,n \rrbracket$, $f^{(k)}(x_k)$ en fonction de $x_n$.
Exercice 585. Montrer que pour tout entier $n \geqslant 2$, pour tout $a \in ]0,1[$, $(1-a)^n < \Frac{1}{1+na}$.
Exercice 586. \\
  1. Soient $a_1, \hots, a_n$ des réels positifs. Montrer que $\displaystyle \prod_{i=1}^{n}(1+a_i) \geqslant 1+ \displaystyle \sum_{i=1}^{n}a_i$. \\
  2. Soient $a_1, \hdots, a_n$ des réels supérieurs à $1$. Montrer que $\displaystyle \prod_{i=1}^{n}a_i \geqslant 1-n+\sum_{i=1}^{n}a_i$.
Exercice 587. Soit $n \in \N^*$ et $u_0, u_1, \hdots, u_{n}$ des réels tels que $u_n = 1$ et pour tout $p \in \{1,\hdots,n\}$, $u_{p-1} = \Frac{u_p}{p}$. \\ Exprimer pour tout $p \in \{0,\hdots,n\}$, $u_p$ en fonction de $n$ et $p$.

Exercice 588. Suite de Wallis

\\ On définit la suite $(W_n)$ par les conditions $W_0 = 0$, $W_1 = 1$ et pour tout $n \in \N$, $W_{n+2} = \Frac{n+1}{n+2}W_n$. \\
  1. Donner la valeur de $W_{2p}$ pour tout $p \in \N$. \\
  2. A l'aide d'un raisonnement par récurrence, justifier que pour tout $p \in \N$, $W_{2p+1} = \Frac{4^p(p!)^2}{(2p+1)!}$.
Exercice 589. Montrer que tout naturel $n \geqslant 1$ peut s'écrire sous la forme $n = 2^p(2q+1)$ avec $(p,q) \in \N$.
Exercice 590. Montrer que pour tout $n \in \N^*$, $\Sum_{k=1}^{2n} \Frac{(-1)^{k-1}}{k} = \Sum_{k=1}^{n} \Frac{1}{n+k}$.
Exercice 591. Soit $(I_{p,q})$ la suite définie pour tout $p \in \N$ et $q \in \N$ par \[ \forall (p,q) \in \N^* \times \N, \;\; I_{p,q} = \Frac{p}{q+1}I_{p-1,q+1} \] et $I_{0,q} = \Frac{1}{q+1}$. \\ Déterminer l'expression de $I_{p,q}$ en fonction de $p$ et $q$ pour tout $p,q \in \N$.

Exercice 592. Nombres de Catalan

\\ On pose $C_0=1$ et, pour tout $n \in \N$ :\\ \[ C_{n+1} = C_0 C_n + C_1 C_{n-1} + C_2 C_{n-2} + \dots + C_{n-2} C_2 + C_{n-1} C_1 + C_n C_0 = \Sum_{k=0}^{n} C_k C_{n-k}. \]
  1. Calculer $C_n$ pour $n \in \llbracket 1,6 \rrbracket$.\\
  2. Montrer, par récurrence forte, que pour tout $n \in \N$, $C_n \in \N^*$.\\
  3. Montrer, par récurrence simple, que pour tout $n \in \N$, $C_n \geqslant 2^{\,n-1}$.\\
  4. Montrer, par récurrence forte, que pour tout $n \in \N$, $C_n \geqslant 3^{\,n-2}$.\\
  5. A-t-on pour tout $n \in \N$, $C_n \geqslant 4^{\,n-2}$ ?
Exercice 593. Soit $(a_n)_{n \in \N^*} \in \R^{\N^*}$ vérifiant $\forall (n,p) \in (\N^*)^2,\; a_{n+p} \leqslant a_n + a_p$.\\
  1. Montrer que pour tout $n \in \N^*$, $n a_{n+1} \leqslant 2 \Sum_{p=1}^{n} a_p$.\\
  2. En déduire que pour tout $n \in \N^*$, $a_n \leqslant \Sum_{p=1}^{n} \Frac{a_p}{p}$.
Exercice 594. On note $(u_{n})_{n \in \N}$ la suite définie par $u_{0}=1$ et pour tout $n \in \N^{*}$ \\ \[ u_{n}=u_{\left\lfloor \frac{n}{2} \right\rfloor}+u_{\left\lfloor \frac{n}{3} \right\rfloor}+u_{\left\lfloor \frac{n}{6} \right\rfloor}. \] \\ 1) Montrer que pour tout $n \in \N$ on a $u_{n} \geqslant n+1$. \\ 2) Trouver $C > 0$ tel que pour tout $n \in \N$ on ait $u_{n} \leqslant C(n+1)$.
Exercice 595. Montrer que pour tout entier $n \geqslant 3$, on peut trouver $n$ entiers $x_1,\hdots,x_n$ strictement positifs, deux à deux distincts, tels que $\Frac{1}{x_1}+\hdots+\Frac{1}{x_n} = 1$.
Exercice 596. Montrer que tout entier $n \geqslant 1$ peut s'écrire comme somme de puissances de $2$ toutes distinctes.
Exercice 597. Soit $A$ une partie de $\N^*$ telle que : \\
  • $1 \in A$; \\
  • $\forall n \in \N^*$, $n \in A \implies 2n \in A$; \\
  • $\forall n \in \N^*$, $n+1 \in A \implies n \in A$. \\
Démontrer que $A = \N^*$.

Exercice 598. Fonction d'Ackermann

\\ La fonction d’Ackermann est définie récursivement par \\ \[ \begin{cases} \forall n \in \N,\; A(0,n)=n+1 \\ \forall m \in \N^{*},\; A(m,0)=A(m-1,1) \\ \forall m \in \N^{*},\; \forall n \in \N^{*},\; A(m,n)=A(m-1,A(m,n-1)) \end{cases} \] \\ Montrer que la fonction d’Ackermann est bien définie.
Exercice 599. Soit $E=\{x_{1},\dots,x_{n}\}$ un ensemble fini. Montrer qu’on peut lister les éléments de $\mathcal{P}(E)$ de sorte que la liste commence par $\varnothing$, se termine par $\{x_{n}\}$ et que chaque nouveau terme de la liste est obtenu depuis le précédent par ajout ou retrait d’un unique élément de $E$.
Exercice 600. Soit $f$ une application de $\N^{*}$ dans $\N^{*}$ telle que pour tout $n \in \N^{*}$ on ait \\ \[ f(n+1) > f(f(n)). \] \\ Montrer que pour tout $n \in \N^{*}$ on a $f(n)=n$.