Raisonnement par réccurence

[bonjourbonsoir]

Bonjour, j'ai un peu de mal avec l'exo suivant, pouvez vous m'aider ?
On considère la suite (Un) définie par U0=1 et U(n+1)= 2Un -n+1
1) Montrer par récurrence que pour tout entier naturel Un > n
2) Montrer que (Un) est croissante

[nodjim]

Pas dur quand même ce truc.
Montre que si Un > n, alors U(n+1) aussi.

[nodjim]

Je voulais dire U(n+1) > n+1 si Un > n

[bonjourbonsoir]

oui mais quand je développe tout ça j'obtiens un résulat bizarre

[titine]

1) Initialisation : pas de problème.
Hérédité :
On suppose U(n) > n
Alors 2U(n) > 2n
Et 2U(n) - n + 1 > 2n - n + 1
Donc U(n+1) > n + 1

2) U(n+1) - U(n) = 2U(n) - n + 1 - U(n) = U(n) - n +1
Or U(n) > n
Donc U(n) - n + 1 > n - n +1
Donc U(n+1) - U(n) > 1 > 0
Ce qui prouve que la suite est croissante.

[bonjourbonsoir]

mais pour l'hérédité on doit partir de U(n+1)>n+1 non ?

[titine]

mais pour l'hérédité on doit partir de U(n+1)>n+1 non ?

Pour montrer qu'une propriété est héréditaire on suppose qu'elle est vraie a un certain rang n et on montre qu'alors elle est aussi vraie au rang suivant (n+1).
Donc ici :
On suppose qu'il existe un n tel que U(n) > n
Et on montre qu'alors, U(n+1) est plus grand que n+1

[bonjourbonsoir]

bah oui mais dans ce cas là on part bien de U(n+1)>n+1 pour arriver à quelque chose et pas l'inverse ?

[titine]

bah oui mais dans ce cas là on part bien de U(n+1)>n+1 pour arriver à quelque chose et pas l'inverse ?

Non , "on part de" U(n) > n (hypothèse de récurrence) et on doit arriver à U(n+1) > n+1

[bonjourbonsoir]

et du coup si je simplifie U(n+1) > n+1 j'obtiens 2Un >2n mais je ne sais pas comment rédiger ça ? parceque évidement c'est vrai mais en faite ce n'est pas un raisonnement comme j'ai l'habitude où on a une équation de base à retrouver,je trouve ce raisonnement assez complexe niveau rédaction

[bonjourbonsoir]

dans mon raisonnement je trouve ça :
U(n+1)>n+1
2Un-n+1> n+1
2un > n+1+n-1
2Un > 2n
don Un>n
mais du coup ce n'est pas ce qu'il faut trouver ?

[bonjourbonsoir]

mais en faite c'est justement ça qui me pose problème on raisonne à l'envers... Du coup on a ça ?? mais j'ai le droit d'enlever le -1 de la parenthèse U(n-1) ???
Un > n
2U(n-1)-n-1 > n
2Un-n-1> n+1
U(n+1) > n+1

[titine]

On sait que U(n+1) = 2U(n) - n + 1

Si l'on suppose U(n) > n
alors 2U(n) > 2n (d'accord ? On a multiplié les 2 membres de l'inégalité par un nombre positif : 2)
et alors 2U(n) - n > 2n - n (d'accord ? On a ajouté -n des 2 côtés)
et alors 2U(n) - n + 1 > 2n - n + 1 (toujours d'accord ? On a ajouté 1 des 2 côtés)
Mais je te rappelle que 2U(n) - n +1 c'est U(n+1)
On a donc prouvé que si on a U(n) > n alors on a aussi U(n+1) > n+1

[bonjourbonsoir]

j'ai compris vos deux astuces, laquelle est préférable pour une bonne rédaction ??
(En tout cas merci beaucoup)

[titine]

P'tipito t'explique le principe du raisonnement par récurrence :
- On démontre que la propriété est héréditaire , c'est à dire que si elle est vraie à un rang n alors elle est vraie au rang suivant. Autrement dit que (P(n) Vraie) entraine (P(n+1) Vraie)
- Puis on démontre qu'elle est vraie pour n=0 (initialisation)
On en déduit qu'elle est vraie pour n=1 (car vraie pour 0 donc vraie pour 1.
Et qu'elle est vraie pour n=2 (car vraie pour 1 donc vraie pour 2.
Et qu'elle est vraie pour n=3 (car vraie pour 2 donc vraie pour 3.
....
Et on peut alors conclure qu'elle est vraie pour tout n.

Ce que je t'ai donné, c'est la démonstration que la propriété est héréditaire :

Si l'on suppose U(n) > n
alors 2U(n) > 2n (d'accord ? On a multiplié les 2 membres de l'inégalité par un nombre positif : 2)
et alors 2U(n) - n > 2n - n (d'accord ? On a ajouté -n des 2 côtés)
et alors 2U(n) - n + 1 > 2n - n + 1 (toujours d'accord ? On a ajouté 1 des 2 côtés)
Mais je te rappelle que 2U(n) - n +1 c'est U(n+1)
On a donc prouvé que si on a U(n) > n alors on a aussi U(n+1) > n+1

[mathelot]

Quand on veut montrer que et que l'on ne trouve pas (!),
on part de Q et on cherche des conditions nécessaires à Q. On dit que c'est la phase d'analyse
si , on peut regarder ensuite (toujours dans la phase d'analyse)
les rapports entre les propriétés P et R. Mais bon, dans la phase de synthèse,
on montre que .

[Shew]

Pour la deux, toujours par récurrence, on suppose que et on développe .

[Shew]

Il y a meme pas besoin d'une recurrence ici. Il suffit d'ecrire u(n+1)-u(n) et d'utiliser la question 1.
Mais si tu as vraiment du mal avec le raisonnement par recurrence bonjourbonsoir, tu peux faire la 2 par recurrence pour t'entrainer

Certes on peut en effet utiliser cette approche mais il faudra alors démontrer que pour tout , .

[Shew]

Il y a meme pas besoin d'une recurrence ici. Il suffit d'ecrire u(n+1)-u(n) et d'utiliser la question 1.
Mais si tu as vraiment du mal avec le raisonnement par recurrence bonjourbonsoir, tu peux faire la 2 par recurrence pour t'entrainer

En effet puisqu'on a