Récurrences

Exercice 824. 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 825. \\ Soit $x \in \R^*$ tel que $x + \Frac{1}{x} \in \Z$. \\ Montrer que pour tout $n \in \N$, $x^n+\Frac{1}{x^n} \in \Z$.
Exercice 826. Soient $a$ un réel et $(u_n)$ la suite définie par \[ u_0 = a \; \; et \; \; \forall n \in \N, \; u_{n+1} = \Frac{1}{n+1}\sum_{k=0}^{n}u_ku_{n-k} \] Déterminer $u_n$ en fonction de $n$.
Exercice 827. Montrer que tout naturel $n \geqslant 1$ peut s'écrire sous la forme $n = 2^p(2q+1)$ avec $(p,q) \in \N$.
Exercice 828. 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 829. 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 830. 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 831. 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 832. \\
  1. Soient $a_1, \hdots, 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 833. Montrer que pour tout entier $n \geqslant 2$, $1 + \dfrac{1}{2^2} + \cdots + \dfrac{1}{n^2} > \dfrac{3n}{2n+1}$.
Exercice 834. 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 835. 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 836. 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 837. 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 838. 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 839. Montrer que tout entier $n \geqslant 1$ peut s'écrire comme somme de puissances de $2$ toutes distinctes.
Exercice 840. 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 841. 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 842. 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 843. 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}$ ?