démonstration par récurrence

[parousky]

Bonjour, je bloque sur un problème depuis trois jours :
Démontrer par récurrence que : 2n+1<2^n+1
Je n'y arrive vraiment pas, pourriez-vous m'aider svp ?
-----

[invitee0f9a3c2]

Soit n un entier naturel

On note P(n) la propriété " 2n+1<2^n+1"

2*0+1=1
2^0+1=2
Or 1<2 donc P(0) est vraie

On suppose P(n) vraie pour un entier naturel n quelconque (hypothèse de récurrence)

On va démontrer P(n+1):

2(n+1)+1=2n+3

2^(n+1)+1=2^n * 2 + 1= (2^n + 1)*2 -1
Or d'après l'hypothèse de récurrence,
(2^n + 1)>2n+1
=> (2^n + 1)*2>(2n+1)*2
=> (2^n + 1)*2 -1 >(2n+1)*2 -1
(2^n + 1)*2 -1 > 4n +1

4n+1-(2n+3)=2n-2=2(n-1) >> 0 pour n>>1
donc 4n+1 >> 2n+3

soit (2^n + 1)*2 -1 > 4n +1 >> 2n+3
<=> 2^(n+1)+1 >2(n+1)+1

donc
P(0) est vraie (n=0)
et pour n>>1 si P(n) est vraie, alors P(n+1) est vraie
donc d'après le principe de récurrence, P(n) est vraie quelque soit n

[Duke Alchemist]

Bonsoir.

La relation n'est pas très claire mais j'opterais plutôt pour 2n+1 < 2ⁿ⁺¹ pour la proposition P(n).
Les 1 se simplifieraient dès la proposition elle-même...

Quel courage lutecia mais ne fais pas trop les exercices des autres, essaie plutôt de les guider dans un premier temps

Cordialement,
Duke.

[parousky]

Merci beaucoup pour ta réponse lutécia. Et puis, un exercice entièrement fait de temps en temps, c'est bien, ça permet de garder la forme !

[A voir en vidéo sur Futura]

[invitee0f9a3c2]

Oh, oui désolé, je n'aurais peut-être pas du te donner la réponse directement, j'y penserai la prochaine fois. Mais je trouve que quand on bloque sur les démonstrations par récurrence il faut en lire quelques unes en entier et les comprendre pour voir le cheminement... et après normalement on y arrive par soi même...

2^n+1 se lit 2ⁿ + 1 s'il n'y a pas de parenthèses

2ⁿ⁺¹ serait plutôt 2^(n+1)

vérifie ton énoncé...