Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

[TS/MPSI] Récurrence

Posté par
StrongDensity
25-07-16 à 02:51

salut,

je bloque sur un exo assez complexe si vous pouviez me donner une indication pour que je puisse le faire merci ^^

La suite (u_n)_{n\in N} est définie par u_0 = 1 et :

      n*, u_n=u_{[n/2]}+u_{[n/3]}+u_{[n/6]}

*Ini : Si n=0 , 0+1=11=u_0
La proposition est initialisée.

*Soit n un entier naturel, on suppose Pn est vérifié est montrons que P(n+1) est vérifiée i.e. montrons que :
                                                 u_{n+1}n+2
j'essaye de placer l'hypothèse de récurrence mais je n'arrive pas vu que je suis complètement bloqué
puisque   u_{n+1}=u_{[(n+1)/2]}+u_{[(n+1)/3]}+u_{[(n+1)/6]}
je ne vois pas comment passer la chose...

d'ailleurs je trouve cette suite un peu spécial comme elle est définie u_0 est inutile vu que u_n est définie par des u_n en fraction.

et dernière question j'ai utilisé "proposition" à la place de "propriété", ce n'est pas grave ? vu qu'on cherche à démontrer une proposition?

merci d'avance

Posté par
mdr_non
re : [TS/MPSI] Récurrence 25-07-16 à 05:17

bonsoir : )

La première chose à faire est de donner la proposition à démontrer.
Bon, on la devine après avoir lu.

Ensuite, il y a une réelle différence entre \left[.\right], \left \lfloor . \right \rfloor et \left \lceil . \right \rceil.
Pour la première, il s'agit de crochets ordinaires. La deuxième est la fonction partie entière et la troisième la fonction partie entière par excès.
Tu aurais pu le deviner car une suite est une fonction au départ de [\![ N , \infty \,[\![ avec N \in \N.
Ainsi par exemple, si u est une suite, tu ne pourras jamais écrire u_{1/2} ou u_{\sqrt{2}}, ça n'a aucune signification.

Tu cherches donc à démontrer la proposition suivante \forall n \in \N, u_n \geq n + 1.

Au niveau de l'hérédité, tu as plusieurs façons de t'en sortir.
D'abord, tu peux noter que la suite est clairement positive et tu peux le démontrer par récurrence si t'en as envie.
Ensuite, tu peux démontrer que \forall n \in \N, u_{n+1} \geq 2u_n. Simplement en revenant à la définition de la fonction partie entière et en considérant tous les cas de congruence modulo 6 de l'indice n.

Tu pourras faire des recherches sur la différence entre une proposition et une propriété.
En pratique on ne fait aucune différence.

Posté par
mdr_non
re : [TS/MPSI] Récurrence 25-07-16 à 05:58

Je rectifie :

Citation :
D'abord, tu peux démontrer que la suite est minorée par 1.
Ensuite, tu peux démontrer que \forall n \in \N, u_{n+1} \geq {\red u_n + 1}. Simplement en revenant à la définition de la fonction partie entière et en considérant tous les cas de congruence modulo 6 de l'indice n.


Sinon plus simplement avec une récurrence forte.
Soit n \in \N, si la propriété est vérifiée pour tout k \in [\![ 0 , n ]\!], alors, en utilisant la propriété suivante de la fonction partie entière \forall x \in \R, \left \lfloor x \right \rfloor > x - 1 on parvient à conclure que la propriété est vérifiée au rang n + 1.

Posté par
Razes
re : [TS/MPSI] Récurrence 25-07-16 à 12:29

mdr_non @ 25-07-2016 à 05:58

Je rectifie :
Citation :
D'abord, tu peux démontrer que la suite est minorée par 1.
Ensuite, tu peux démontrer que \forall n \in \N, u_{n+1} \geq {\red u_n + 1}. Simplement en revenant à la définition de la fonction partie entière et en considérant tous les cas de congruence modulo 6 de l'indice n.


Sinon plus simplement avec une récurrence forte.
Soit n \in \N, si la propriété est vérifiée pour tout k \in [\![ 0 , n ]\!], alors, en utilisant la propriété suivante de la fonction partie entière \forall x \in \R, \left \lfloor x \right \rfloor > x - 1 on parvient à conclure que la propriété est vérifiée au rang n + 1.

Que vaut u_1; u_2?

Posté par
Razes
re : [TS/MPSI] Récurrence 25-07-16 à 12:34

Ce qu'il faut démontrer c'est u_{n}\geqslant n+1  et non pas u_{n+1}\geqslant u_n+1

Posté par
mdr_non
re : [TS/MPSI] Récurrence 25-07-16 à 13:39

Razes, tu fais exprès de ne jamais lire ou quoi ?

Posté par
Recomic35
re : [TS/MPSI] Récurrence 25-07-16 à 13:46

Voir ici :

Posté par
StrongDensity
re : [TS/MPSI] Récurrence 29-07-16 à 00:14

merci pour vos réponses

mdr_non @ 25-07-2016 à 05:58

Je rectifie :
Citation :
D'abord, tu peux démontrer que la suite est minorée par 1.
Ensuite, tu peux démontrer que \forall n \in \N, u_{n+1} \geq {\red u_n + 1}. Simplement en revenant à la définition de la fonction partie entière et en considérant tous les cas de congruence modulo 6 de l'indice n.


Sinon plus simplement avec une récurrence forte.
Soit n \in \N, si la propriété est vérifiée pour tout k \in [\![ 0 , n ]\!], alors, en utilisant la propriété suivante de la fonction partie entière \forall x \in \R, \left \lfloor x \right \rfloor > x - 1 on parvient à conclure que la propriété est vérifiée au rang n + 1.


je ne comprends pas bien ce que c'est que la récurrence forte.  
et même avec le lieu je vous avouerai que c'est la galère penser à la congruence

et d'ailleurs :
je ne comprends pas le dernier post de Robot dans le lien (je n'arrive pas à copier coller) car c'est un peu simple ce qu'il dit là ? il ne l'a pas vraiment démontré ?

merci,

Posté par
StrongDensity
re : [TS/MPSI] Récurrence 29-07-16 à 00:15

d'ailleurs les raisonnements ne sont pas vraiment mon fort en math :/ vous avez pas quelque chose à me conseiller ? à moins que j'attends les premiers cours de math sup ?

Posté par
mdr_non
re : [TS/MPSI] Récurrence 29-07-16 à 03:40

Je te l'ai écrite ce qu'était la récurrence forte. Elle se formule comme une récurrence simple sauf que pour établir l'hérédité, on suppose vraie toute une suite de propositions.



Soit n_0 \in \N.
Le principe de la récurrence simple est le suivant : si \mathcal{P}_{n_0} est vraie, et si, pour tout entier n \geq n_0, la vérité de \mathcal{P}_n implique celle de \mathcal{P}_{n+1} alors la proposition : \forall n \geq n_0, \mathcal{P}_n est vraie.


Exemple : Soit (u_n)_{n\in\N} une suite arithmétique de raison r \in \C. Alors, pour tout n \in \N, u_n = u_0 + nr.

En effet, par définition, pour tout n \in \N, u_{n+1} = u_n + r.

Initialisation : On a u_0 = u_0 + 0\times r.

Hérédité : Soit n \in \N. On suppose que u_n = u_0 + nr et il s'agit de montrer que u_{n+1} = u_0 + (n + 1)r.
Or, il est immédiat que : u_{n+1} = \left(u_0 + nr\right) + r = u_0 + (n + 1)r, ce qui termine la récurrence.



Il arrive parfois des cas où l'hypothèse que \mathcal{P}_n est vraie ne suffit pas pour montrer que \mathcal{P}_{n+1} est vraie. Dans ces cas, on a par exemple besoin de \mathcal{P}_{n-1} et \mathcal{P}_n (on parle alors d'une récurrence double), ..., voire carrément de toute la suite de propositions \mathcal{P}_0, \mathcal{P}_1, ..., \mathcal{P}_n (et on parle alors d'une récurrence forte).


Exemple : Soit (u_n)_{n\in\N} une suite réelle définie par u_0 > 0 et pour tout n \in \N, u_{n+1} = u_0 + u_1 + ... + u_n. Alors u est à termes strictement positifs.

Initialisation : Par hypothèse, u_0 > 0.

Hérédité : Soit n \in \N. On suppose que pour tout k \in [\![ 0 , n ]\!], u_k > 0 et il s'agit de montrer que u_{n+1} > 0.
Or, u_{n+1} est une somme de nombres strictement positifs si bien que u_{n+1} > 0 et la preuve est terminée.

Tu vois qu'ici, on ne pouvait pas se contenter de supposer uniquement que u_n > 0 pour montrer que u_{n+1} > 0.



Maintenant que tu as eu un exemple, tu peux reprendre mon message et rédiger ta solution.

Citation :
Soit n \in \N, si la propriété est vérifiée pour tout k \in [\![ 0 , n ]\!], alors, en utilisant la propriété suivante de la fonction partie entière \forall x \in \R, \left \lfloor x \right \rfloor > x - 1 on parvient à conclure que la propriété est vérifiée au rang n + 1.

Posté par
StrongDensity
re : [TS/MPSI] Récurrence 31-07-16 à 18:23

ok merci j'ai compris

si j'ai bien compris y'a pas besoin d'initialisation vu qu'elle est dans l'hérédité?

-Hérédité:  Soit n \in \N, supposons qu'il existe k tel que  pour tout k \in [\![ 0 , n ]\!], la propriété est vraie c'est à dire que pour tout n \in \N, u_n\ge n+1

en faite non je comprend pas ce que ça apporte la fonction partie entière

Posté par
Recomic35
re : [TS/MPSI] Récurrence 31-07-16 à 18:41

Citation :
je ne comprends pas le dernier post de Robot dans le lien (je n'arrive pas à copier coller) car c'est un peu simple ce qu'il dit là ? il ne l'a pas vraiment démontré ?


C'est pourtant bien simple.

Hérédité : on suppose n>0 et la proposition vérifiée pour tout p<n. Vérifions-la pour n.

Puisque n>0, on a \lfloor n/6\rfloor\leq \lfloor n/3\rfloor\leq \lfloor n/2\rfloor < n et donc par hypothèse de récurrence
u_{\lfloor n/6\rfloor}\geq \lfloor n/6\rfloor +1, u_{\lfloor n/3\rfloor}\geq \lfloor n/3\rfloor +1 et u_{\lfloor n/2\rfloor}\geq \lfloor n/2\rfloor +1.

Je te laisse conclure avec la remarque de Robot sur l'autre forum.

Posté par
mdr_non
re : [TS/MPSI] Récurrence 31-07-16 à 21:14

Non tu n'as pas compris, j'ai explicitement fait une initialisation dans les deux exemples que j'ai donnés. L'initialisation est toujours à faire.

Et ta récurrence ne va pas du tout.

Citation :
supposons qu'il existe k tel que  pour tout k \in [\![ 0 , n ]\!], la propriété est vraie c'est à dire que pour tout \red n \in \N, \red u_n\ge n+1
Comprends-tu ce que tu écris ? Réfléchis quelques secondes à pourquoi j'ai souligné cette partie en rouge.
Tu aurais pu reprendre la rédaction que je t'ai fournie aussi.

Soit n \in \N. On suppose que pour tout k \in [\![ 0 , n ]\!], u_k \geq k + 1 et il s'agit de montrer que u_{n+1} \geq n + 2.

Comme n \geq \lfloor \frac{n + 1}{2} \rfloor \geq \lfloor \frac{n + 1}{3} \rfloor \geq \lfloor \frac{n + 1}{6} \rfloor on a, par hypothèse de récurrence, \left\{\begin{matrix}u_{\lfloor \frac{n + 1}{2} \rfloor} \geq \lfloor \frac{n + 1}{2} \rfloor + 1
 \\ u_{\lfloor \frac{n + 1}{3} \rfloor} \geq \lfloor \frac{n + 1}{3} \rfloor + 1
 \\ u_{\lfloor \frac{n + 1}{6} \rfloor} \geq \lfloor \frac{n + 1}{6} \rfloor + 1\end{matrix}\right..

De plus, \forall x \in \R, \left \lfloor x \right \rfloor > x - 1 d'où \left\{\begin{matrix}u_{\lfloor \frac{n + 1}{2} \rfloor} > \frac{n - 1}{2} + 1
 \\ u_{\lfloor \frac{n + 1}{3} \rfloor} > \frac{n - 2}{3} + 1
 \\ u_{\lfloor \frac{n + 1}{6} \rfloor} > \frac{n - 5}{6} + 1\end{matrix}\right..

D'où, u_{n+1} > \frac{n - 1}{2} + \frac{n - 2}{3} + \frac{n - 5}{6} + 3 = n + 1 puis, comme voulu, u_{n+1} \geq n + 2.

Posté par
Recomic35
re : [TS/MPSI] Récurrence 01-08-16 à 00:33

mdr_non @ 31-07-2016 à 21:14

L'initialisation est toujours à faire.


Affirmation un peu hative. Ici, il convient de la faire. Ce n'est pas toujours le cas avec la récurrence forte.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !