Récurrence

par **capitaine nuggets** » 18 Aoû 2012, 00:05

Bonsoir, j'aurais besoin d'aide sur deux exercices indépendant portant sur le raisonnement par récurrence.

I : On considère la suite définie par , et pour tout entier naturel : .
Montrer que pour tout entier naturel , .

Là ce qui me pose problème, c'est que je ne sais pas s'il faut que je vérifie pour le premier rang (

) ou les deux premiers (

et

).
Pour l'hérédité : je ne sais pas si je dois supposer l'existence de deux rang successif

et

pour montrer

ou si je dois supposer la propriété vraie pour tout

pour montrer

II : On considère deux applications et définies respectivement par :

et .

Conjecturer une expression de et en fonction de et démontrer ces deux conjectures par récurrence.

J'ai conjecturé :

.

Mais je bloque totalement sur l'hérédité :triste:

J'ai pu aussi remarque que

donc si on en connaît un, on connais l'autre.

Merci d'avance pour votre aide

par **Le_chat** » 18 Aoû 2012, 01:32

Salut.

Pour le premier exo, pour montrer que la propriété est vraie au rang k+2, il suffit de la supposer vraie au rang k+1 et k. Donc pour initialiser, tu dois montrer que la propriété est vraie à deux rangs successifs, disons 0 et 1. En effet, si tu as montré que P(k) et P(k+1) impliquent P(k+2) pour tout k, alors comme tu as P(0) et P(1), tu as P(2), puis P(3) car P(2) et P(1) etc... En revanche, si tu n'avais pas prouvé P(1), ben tu aurais du mal à dire que P(2) est vrai car alors tu peux pas utiliser l'implication précédente.

Je pige pas le second exo... tes expressions ont l'air justes, mais je vois à quoi sert la récurrence, ça se montre en une ligne en écrivant n=2p ou n=2p+1...

par **SaintAmand** » 18 Aoû 2012, 01:57

Le_chat a écrit:Pour le premier exo, pour montrer que la propriété est vraie au rang k+2, il suffit de la supposer vraie au rang k+1 et k.

Personnellement, je trouve plus élégant de montrer que la propriété

[CENTER]

[/CENTER]
est vraie pour tout

.

par **capitaine nuggets** » 18 Aoû 2012, 03:36

Le_chat a écrit:Je pige pas le second exo... tes expressions ont l'air justes, mais je vois à quoi sert la récurrence, ça se montre en une ligne en écrivant n=2p ou n=2p+1...

c'est un exo d'application ou il m'est demandé de montrer à l'aide d'une récurrence.
Mais je ne vois pas comment faire l'hérédité.

Sinon, comment le montrerais-tu ?

par **chan79** » 18 Aoû 2012, 07:20

capitaine nuggets a écrit:c'est un exo d'application ou il m'est demandé de montrer à l'aide d'une récurrence.
Mais je ne vois pas comment faire l'hérédité.

Sinon, comment le montrerais-tu ?

salut
tu pourrais utiliser le principe de récurrence forte (équivalent au principe de récurrence habituel):
tu vérifies qu'elle est vraie aux rangs 0 et 1
et que:
si elle est vraie pour tout rang k inférieur ou égal à n+1, elle est vraie au rang n+2
alors tu pourras conclure qu'elle est vraie pour tout n

par **Le_chat** » 18 Aoû 2012, 09:31

Pour l'exo 2:

Si n est pair, on écrit n=2p, alors f(n)=p, et la partie entière supérieure de (n-1)/2 est p donc f(n)=...
Si n est impair, on écrit n=2p+1, et f(n)=p, et et la partie entière supérieure de (n-1)/2 est p, donc f(n)=...

Finalement, pour tout n, f(n) est ce que tu écris, tu fais la même chose avec g.

Concernant l'exo 1, je suis sur qu'il est attendu une récurrence double et pas une récurrence forte, même si les deux marchent. C'est pas trop dans l'esprit de la récurrence forte je crois, car il faut initialiser à deux rangs, et qu'on utilise guère autre chose que P(k) et P(k+1) pour démontrer P(k+2).

par **chan79** » 18 Aoû 2012, 09:46

Le_chat a écrit:
Concernant l'exo 1, je suis sur qu'il est attendu une récurrence double et pas une récurrence forte, même si les deux marchent. C'est pas trop dans l'esprit de la récurrence forte je crois, car il faut initialiser à deux rangs, et qu'on utilise guère autre chose que P(k) et P(k+1) pour démontrer P(k+2).

d'accord, mais ça fonctionne tellement facilement

Récurrence

Récurrence

Qui est en ligne