Sujet A.3.1 Raisonnement par récurrence
Choisir
un exercice, puis le résoudre
:
Signaler une erreur
Signaler une erreur
Exercice a
Pour tout $\,n\app\bb N^{\ast},\,$ montrer que la somme $\,S_n=\smb{2}{\dsum_{k=1}^n} k^2\,$ vaut :
$\displaystyle{}S_n=\dfrac{n(n+1)(2\sp{1.5}n+1)}{6}$
récurrence simple
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big(P(n)\!\Imp\! P(n+1)\big).\,$
récurrence double
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ et $P(n_0+1)$ soient vraies,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n)\txt{et}P(n+1))\!\Imp\! P(n+2)\big).\,$
récurrence forte
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n_0)\!\txt{et}\!\!\dots\!\!\txt{et}\!P(n))\!\Imp\! P(n+1)\big).\,$
indication
Procéder par récurrence sur $\,n\sp{1.5},\,$ à partir de $\,n=1\sp{1.5}.\,$
réponse
On obtient bien la formule :
$\,\ptt n\geq1\sp{1.5},\ \, S_n=\dfrac{n(n+1)(2\sp{1.5}n+1)}{6}\!\cdot\,$
correction
On procède par
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
récurrence
simple sur $\,n\,$ à partir du rang $\,n_0=1\sp{.75}.\,$
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big(P(n)\!\Imp\! P(n+1)\big).\,$
- La formule est bien vérifiée au rang $\,n_0=1\,:\,$ $\,S_1=1=\dfrac{1\sp{1.5}.\sp{-1.5}2\sp{1.5}.\sp{-1.5}3}{6}\!\cdot\,$
- Pour $\,n\geq2\,$ fixé, on suppose la formule vérifiée au rang $\,n-1\geq n_0:\,$
$\displaystyle{}S_{n-1}= \frac{(n-1)\,n\,(2\sp{1.5}n-1)}{6}$On en déduit alors la formule au rang $\,n:\,$$\eqalign{S_n&=S_{n-1}+{n^2}=\frac{(n-1)\,n\,(2\sp{1.5}n-1)}{6}+n^2\\&=\frac{n\sp{.75}(2\sp{1.5}n^2-3\sp{1.5}n+1)+6\sp{1.5}n^2}{6}= \frac{n\sp{1.5}(2\sp{1.5}n^2+3\sp{1.5}n+1)}{6}}$L'expression figurant au numérateur s'annule pour $\,n=-1\sp{1.5},\,$ d'où laUne racine de $\,P\app\bb K[X]\,$ est un $\,\alpha\app\bb K\,$ tel que $\,P(\alpha)=0\,.\,$ $\,\alpha\app\bb K\,$ est racine de $\,P\app\bb K[X]\,$ ssi $\,(X\!-\!\alpha)\,$ divise le polynôme $P.$factorisation :$\displaystyle{}S_n=\frac{n(n+1)(2\sp{1.5}n+1)}{6}$
Un raisonnement par récurrence permet de vérifier la validité d'une formule fournie a priori.
En revanche, en l'absence d'une telle conjecture, ce type de raisonnement n'est d'aucune aide.
Signaler une erreur
Signaler une erreur
Exercice b
On considère la suite $\,(u_n)_{n\in\bb{N}}\,$ définie par $\,u_0=0,\,$ $\,u_1=1\,$ et :
$\displaystyle{}\ptt n\app \bb{N},\ u_{n+2}=(n+4)\,u_{n+1}-(n+1)\,u_n$
Démontrer que pour tout $\,n\app\bb N\sp{1.5},\,$ $\,u_n\,$ est le produit de $\,n\,$ par sa factorielle : $\,u_n=n\sp{1.5}.\sp{-1.5}n\sp{1.5}!\,$
récurrence simple
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big(P(n)\!\Imp\! P(n+1)\big).\,$
récurrence double
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ et $P(n_0+1)$ soient vraies,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n)\txt{et}P(n+1))\!\Imp\! P(n+2)\big).\,$
récurrence forte
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n_0)\!\txt{et}\!\!\dots\!\!\txt{et}\!P(n))\!\Imp\! P(n+1)\big).\,$
indication
Effectuer un raisonnement par récurrence à deux prédécesseurs (récurrence double).
réponse
On montre bien, par récurrence, la relation : $\,\ptt n\app\bb{N},\ u_n=n\sp{1.5}.\sp{-1.5}n!\,$
correction
Pour $\,n\geq2,\,$ chacun des $\,u_n\,$ est défini à partir des deux termes précédents.
On va donc démontrer cette formule par une
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
récurrence
double, à partir du rang : $\,n_0=0:\,$
- $P(n_0)$ et $P(n_0+1)$ soient vraies,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n)\txt{et}P(n+1))\!\Imp\! P(n+2)\big).\,$
- La formule est bien vérifiée aux rangs $\,n_0=0\,$ et $\,n_1=n_0+1=1:\,$
$\displaystyle{}u_0=0=0\sp{1.5}.\sp{-1.5}0\sp{1.5}!\,\txt{et}\,u_1=1=1\sp{1.5}.\sp{-1.5}1\sp{1.5}!$
- Pour $\,n\app \bb{N}\,$, on suppose la formule vérifiée aux rangs $\,n\,$ et
$\,n+1:\,$
$\displaystyle{}u_n=n\sp{1.5}.\sp{-1.5}n\sp{1.5}!\ \txt{et} \ u_{n+1}=(n+1)(n+1)\sp{1.5}!$Par définition de laPour $n\app\bb N\sp{1.5},$ la factorielle de $\,n\,$ est l'entier naturel défini par :factorielle, on a pour tout $\,k\app\bb N:\,$ $\,(k+1)\sp{1.5}k\sp{1.5}!=(k+1)\sp{1.5}!\,$ d'où, au rang $\,n+2:\,$$\displaystyle{}0\sp{1.5}!=1 \ \txt{et} \ n\sp{1.5}!=\dprod_{k=1}^{n}k \txt{si} n\neq0$$\eqalign{u_{n+2}&=(n+4)\,u_{n+1}-(n+1)\,u_n\\ &= (n+4)(n+1)(n+1)!-(n+1)\sp{1.5}n\sp{1.5}.\sp{-1.5}n\sp{1.5}!\\ &=\big((n+4)(n+1)-n\big)(n+1)\sp{1.5}!\\ &=(n^2+4\sp{1.5}n+4)\sp{1.5}(n+1)\sp{1.5}!}$ParPour $\,a,b\app\bb C\sp{1.5},\,$ on a les identités remarquables :identité remarquable, on peut conclure au caractère héréditaire de la formule, avec :$\eqalign{\sth{.75}(a+b)^2&=a^2+2\sp{1.5}a\sp{1.5}b+b^2\\[-.5ex](a+b)^3&=a^3+3\sp{1.5}a^2b+3\sp{1.5}a\sp{1.5}b^2+b^3}$$\displaystyle{}u_{n+2}=(n+2)^2\sp{1.5}(n+1)\sp{1.5}!=(n+2)(n+2)\sp{1.5}!$
Un raisonnement par récurrence permet de vérifier la validité d'une formule fournie a priori.
En revanche, en l'absence d'une telle conjecture, ce type de raisonnement n'est d'aucune aide.
Signaler une erreur
Signaler une erreur
Exercice c
Démontrer qu'il existe un certain entier naturel $\,n_0\,$ à préciser, à partir duquel on a : $\,2^{\sp{1.5}n}\sp{-1.5} > n^2.\,$
récurrence simple
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big(P(n)\!\Imp\! P(n+1)\big).\,$
récurrence double
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ et $P(n_0+1)$ soient vraies,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n)\txt{et}P(n+1))\!\Imp\! P(n+2)\big).\,$
récurrence forte
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n_0)\!\txt{et}\!\!\dots\!\!\txt{et}\!P(n))\!\Imp\! P(n+1)\big).\,$
indication
1
Examiner les premières valeurs de $\,n\app\bb N\,$ pour conjecturer une valeur de $\,n_0\,.\,$
indication
2
Prouver par récurrence que $\,n_0=5\sp{1.5},\,$ c'est-à-dire que : $\,\ptt n\geq 5\sp{1.5},\ 2^{\sp{1.5}n}\sp{-1.5}>n^2.\,$
réponse
L'inégalité $\,2^{\sp{1.5}n}\sp{-1.5} > n^2\,$ est fausse pour $\,2\leq n\leq4\sp{1.5},\,$ mais elle est vraie à partir de $\,n_0=5\sp{1.5}.\,$
correction
Il s'agit d'abord de tester cette relation pour les premières valeurs de $\,n\app \bb N:\,$
$\eqalign{\txt{On a d'abord :} \ \smh1{2^0=1}& > &0=0^2\\ 2^1=2&>&1=1^2\\ \txt{mais ensuite :}\ \ 2^2=4&=&4=2^2\\2^3=8&<&9=3^2\\ 2^4=16&=&16=4^2\\ \txt{et enfin :}\ \ 2^5=32&>&25=5^2\stb{1}}$
On conjecture alors que $\,n_0=5\,$ et on va le vérifier par une
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
récurrence
simple à partir de ce rang $\,n_0\,.\,$
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big(P(n)\!\Imp\! P(n+1)\big).\,$
- On a déjà établi l'inégalité au rang $\,n_0=5:\,$ $\,\smb{1}{2^{\sp{1.5}5}\sp{-1.5}>5^2}\sp{1.5}.\,$
- Pour un entier $\,n\geq5\,$ fixé, on suppose que l'inégalité $\,2^n\sp{-1.5}>n^2\,$ soit vérifiée.
En la
L'ordre sur $\bb R$ est compatible avec le produit par un réel positif :multipliant par $\,2\sp{1.5},\,$ on en déduit que : $\,2^{n+1}=2\sp{1.5}.\sp{-1.5} 2^{\sp{1.5}n} > 2\sp{1.5}n^2.\,$ Il suffirait alors que : $\,2\sp{1.5}n^2\geq(n+1)^2\sp{1.5},\,$ pour pouvoir conclure au caractère héréditaire de l'inégalité : $\,2^{\sp{1.5}n}\sp{-1.5}> n^2.\,$
- $\,(\sp{1.5}a\leq b\ \txt{et}\ c\geq 0\sp{1.5})\Imp a\sp{1.5}c\leq b\sp{1.5}c \,;\,$
- $\, (\sp{1.5}a < b\ \txt{et}\ c > 0\sp{1.5})\Imp a\sp{1.5}c < b\sp{1.5}c\,.\,$
- Cela pourrait s'établir par une autre récurrence, mais il y a plus simple en écrivant :
$\eqalign{2\sp{1.5}n^2-(n+1)^2&= n^2-2\sp{1.5}n-1\\ &=(n-1)^2-2\\&=\big(n-1-\sqrt2\big)\big(n-1+\sqrt2\big)}$
- Avec : $\,n\geq5>1+\sqrt2 > 1-\sqrt2\sp{1.5},\,$ on obtient bien : $\,2\sp{1.5}n^2\geq(n+1)^2\,$ pour tout $\,n\geq5\,.\,$
Les factorisations déduites d'Pour $\,a,b\app\bb C\sp{1.5},\,$ on a les identités remarquables :identités remarquables sont d'usage très courant, comme ici pour $\,n^2-2\sp{1.5}n-1\sp{1.5}.\,$ Dans les cas simples, elles sont préférables à l'usage de$\eqalign{\sth{.75}a^2-b^2&=(a-b)(a+b)\\[-.5ex]a^3-b^3&=(a-b)(a^2+a\sp{1.5}b+b^2)}$Soit, pour $(a,b,c)\app\bb R^{\ast}\!\times\sp{-1.5}\bb R^2\sp{1.5},$ l'équation : $\,a\sp{1.5}x^2+b\sp{1.5}x+c=0\sp{1.5}.\,$ Avec pour discriminant $\,\Delta=b^2-4\sp{1.5}a\sp{1.5}c\sp{1.5},\,$ cette équation a dans $\bb R\sp{1.5}:$formules comme : $\,\Delta = b^2-4\sp{.75}a\sp{.75}c\sp{1.5},\,$ $\,x_i=\big(-b\pm\sqrt{\Delta}\big)/2\sp{.75}a\sp{1.5},\,$ etc.- aucune racine si $\,\smh{.5}\Delta < 0\,;\,$
- une seule racine si $\,\Delta = 0\sp{1.5}:\,$ $\,x=\smh{.7}{-\dfrac{b}{2\sp{1.5}a}}\,;\,$
- deux racines distinctes si $\,\Delta > 0\sp{1.5}:\,$ $\,x=\smh{0.2}{\dfrac{-b\pm\sqrt{\Delta}}{2\sp{1.5}a}}\!\cdot\,$
Par
Pour tous réels $\,\alpha\sp{1.5},\ \beta\,$ et $\,\gamma\,$ strictement positifs, on a :
croissances
comparées, on peut dire que : $\,\smb{1}{n^2\!\!\dl n{+\I}\!\!o(2^n)}\sp{1.5},\,$ c'est-à-dire : $\,\smb{1}{\lim n{+\I}{n^2}\!\big/{2^n}=0}\sp{1.5}.\,$
Ce quotient est donc strictement inférieur à $\,1\,$ à partir d'un certain rang $\,n_0\sp{1.5}.\,$
Cependant, ces considérations ne permettent pas de déterminer la valeur du rang $\,n_0\sp{1.5}.\,$$\displaystyle{}(\ln n)^\beta\!\!\dl n{+\I}\sp{1.5}o\sp{1.5}(n^\alpha)\sp{1.5},\ \,n^\alpha\!\!\dl n{+\I}\sp{1.5}o\sp{1.5}(\e{\gamma\,n})\,\txt{et}\,\e{\gamma\,n}\dl n{+\I}o\big(n\sp{1.5}!\big) $
Signaler une erreur
Signaler une erreur
Exercice d
On considère la suite $(u_n)_{n\in\bb{N}}$ définie par $\,u_0=0\sp{1.5},\,$ $\,u_1=1\sp{1.5},\,$ et pour tout $\,p\geq 1:\,$
$\displaystyle{}u_{2\sp{.75}p}=\frac{u_p+u_{p-1}}{2}\ \txt{et}\ u_{2\sp{.75}p+1}=u_{2\sp{.75}p-1}+\frac{1}{2\sp{.75}p+1}$
Démontrer que pour tout $\,n\geq1\sp{1.5},\,$ $\,u_n\,$ est la somme des $\,\smh1{\dfrac{1}{n-2\sp{.75}k}}\,$ pour tous les $\,k\app \bb{N}\,$ tels que $\,2\sp{.75}k\leq n-1\sp{1.5}.\,$
récurrence simple
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big(P(n)\!\Imp\! P(n+1)\big).\,$
récurrence double
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ et $P(n_0+1)$ soient vraies,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n)\txt{et}P(n+1))\!\Imp\! P(n+2)\big).\,$
récurrence forte
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n_0)\!\txt{et}\!\!\dots\!\!\txt{et}\!P(n))\!\Imp\! P(n+1)\big).\,$
indication
1
Dissocier les cas où $n$ est pair des cas où $n$ est impair.
indication
2
Effectuer une récurrence forte, en commençant par le cas où $n$ est impair.
réponse
On obtient : $\,\ptt n\geq1\sp{1.5},\ u_n=\smh{2.8}{\dsum\limits_{k=0}^{\Big\lfloor \tfrac{n-1}2\Big\rfloor}\dfrac{1}{n-2\sp{1.5}k}},\,$ soit encore :
$\displaystyle{}\Syst{u_{2\sp{1.5}p}\ &=\smh0{\smb{1.5}{\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{2\sp{1.5}p}}} \\ \ u_{2\sp{1.5}p+1}&=\smb1{1+\frac{1}{3}+\cdots+\frac{1}{2\sp{1.5}p+1}}}$
correction
La somme envisagée porte sur des $k\app\bb N$ tels que $\,0\leq2\sp{1.5}k\leq n-1\sp{1.5},\,$ c'est-à-dire de $\,0\,$ à la partie
Pour tout $x\app\bb R\sp{1.5},$ il existe un plus grand $\,k\app\bb Z\,$ tel que $\,k\leq x\,.\,$
Cet entier unique noté $\lfloor x\rfloor$ est caractérisé par l'encadrement :
entière
de $\,\dfrac{n-1}2:\,$
$\displaystyle{}\lfloor x\rfloor\leq x < \lfloor x\rfloor +1$
$\eqalign{u_n=&\dsum_{2\sp{.75}k\,\leq\, n-1}\frac{1}{n-2\sp{.75}k}=\smh{4}{\dsum\limits_{k=0}^{\Big\lfloor \tfrac{n-1}2\Big\rfloor}\dfrac{1}{n-2\sp{1.5}k}}\\[1ex]
\txt{soit :}&\Syst{u_{2\sp{1.5}p}\ &=\smh0{\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{2\sp{1.5}p}} \\[-.5ex]
\ u_{2\sp{1.5}p+1}&=\smb1{1+\frac{1}{3}+\cdots+\frac{1}{2\sp{1.5}p+1}}}}$
Lorsque $\,n=2\sp{1.5}p\sp{1.5},\,$ le terme $\,u_{2\sp{1.5}p}\,$ est défini par des termes d'indices qui ne précèdent pas immédiatement $\,n\sp{1.5}.\,$
On va donc utiliser une
Soit $P(n)$ une propriété dépendant d'un entier $\,n\geq n_0\,$ telle que :
récurrence
forte pour démontrer cette formule à partir de $\,n=1:\,$
- $P(n_0)$ soit vraie,
- et $\,\ptt n\geq n_0\sp{1.5},\ \big((P(n_0)\!\txt{et}\!\!\dots\!\!\txt{et}\!P(n))\!\Imp\! P(n+1)\big).\,$
- On a d'abord : $\,u_1=1=\tst{\sum}_{k=0}^0\dfrac1{1-2\sp{1.5}k}\!\cdot\,$
- On suppose maintenant que pour $\,n\geq2\,$ fixé, la formule est vérifiée à tous les rangs de $\,1\,$ à $\,n-1\sp{1.5}.\,$
- Si $\,n=2\sp{1.5},\,$ on a bien : $\,u_2=\dfrac{1}{2}=\tst{\sum}_{k=0}^0\dfrac1{2-2\sp{1.5}k}\!\cdot\,$
- Si $\,n=2\sp{1.5}p+1\geq3\sp{1.5},\,$ on
Dans une somme indexée par $\,k\app\,[\![m,n]\!]\sp{1.5},\,$ on peut translater les indices avec $\,h=k+p\,$ et $\,p\app \bb Z:\,$translate les indices en posant $\,h=k+1:\,$$\displaystyle{}\smh{2}{\sum_{k=m}^{n}x_k=\sum_{h=m+p}^{n+p}\!\!x_{h-p}}$$\eqalign{u_{2\sp{1.5}p+1}&=\ \smh{1.5}{\sum_{k=0}^{p-1}\frac{1}{2\sp{1.5}p-1-2\sp{.75}k}+\frac{1}{2\sp{1.5}p+1}}\sp{110}\\[-.5ex] &= \ {\sum_{h=0}^{p}\frac{1}{(2\sp{1.5}p+1)-2\sp{.75}h}}}$
- Si $\,n=2\sp{1.5}p\geq4\sp{1.5},\,$ on
Soit $S$ une somme de $x_k$ pour un entier $k$ variant de $m$ à $\,n\geq m\sp{1.5}.\,$ Alors on peut y dissocier les termes d'indices pairs de ceux d'indices impairs :réunit les indices $\,h=2\sp{1.5}k\,$ et $\,h=2\sp{1.5}k+1:\,$$\displaystyle{}\dsum_{k=m}^{n}x_k=\!\!\dsum_{m\leq 2\sp{.75}h\leq n}\!\!x_{2\sp{.75}h}\ +\!\!\!\dsum_{m\leq 2\sp{.75}h+1\leq n}\!\!\!x_{2\sp{.75}h+1}$$\eqalign{2\sp{1.5}u_{2\sp{1.5}p}&=\!\!\sum_{2\sp{1.5}k\,\leq \,p-1}\dfrac{1}{p-2\sp{1.5}k}+\!\!\sum_{2\sp{1.5}k\,\leq\, p-2}\dfrac{1}{(p-1)-2\sp{1.5}k}\\[-.75ex] &=\!\!{\sum_{2\sp{1.5}k\,\leq\, p-1}\dfrac{1}{p-2\sp{1.5}k}+\!\!\!\sum_{2\sp{1.5}k+1\,\leq\, p-1}\dfrac{1}{p-(2\sp{1.5}k+1)}}\\[-.5ex] &=\ \sum_{h=0}^{p-1}\dfrac{1}{p-h}\,,\txt{d'où :}\ u_{2\sp{1.5}p}={\sum_{h=0}^{p-1}\dfrac{1}{2\sp{1.5}p-2\sp{1.5}h}}}$
$\displaystyle{}\ptt n\geq1\sp{1.5},\ u_n=\sum_{k=0}^{\Big\lfloor \tfrac{n-1}2\Big\rfloor}\dfrac{1}{n-2\sp{1.5}k}$