Récurrence double

[puilo]

Bonjour !
Je sollicite votre aide car je suis face à un problème que je ne parviens pas à résoudre :

(An) désigne la suite de Fibonacci c'est à dire que :

..
et de manière générale :

Je dois montrer à l'aide de deux récurrences emboitées que pour tout n de N et pour tout p de N* on a :



J'ai donc commencé par fixer n=0 pour faire une première récurrence sur p :

Initialisation :
or :

Hérédité : On a
Montrons que :

J'ai donc (d'après la définition de la suite de Fibonacci)

Mais à ce niveau je suis bloqué ... Comment continuer ? Et surtout suis-je sur la bonne voie ?

Merci pour votre aide

[infernaleur]

Bonjour,
Déjà tu fais une erreur dans ton initialisation, si tu veux faire une récurrence sur p tu fixe n appartenant à N mais tu ne peux dire que n=0, n peux prendre n'importe quelle valeur !
Dans ton initialisation tu dois montrer que la relation est vraie seulement en prenant p=1 mais en laissant n tel quel.

Sinon tu indique vouloir faire une récurrence double dans ton titre pourquoi ne l'as fais-tu pas ?
Je te rappelle qu'une récurrence double consiste :
-à montrer l'initialisation pour les deux premiers rang (p=0 et p=1)
-et pour l'hérédité, tu suppose ta relation vrai pour un certain rang p et le rang suivant (p+1) et tu la montres au rang p+2

Tu verras qu'avec ses deux relations sa sera plus facile.

[zygomatique]

salut








....

[Ben314]

Salut,
Perso, face à ce type de question (i.e. je fait ma récurrence sur quoi ?), j'aurais tendance à me poser la question "c'est quoi qui est "évident" comme initialisation ?
Et comme le truc "évident" concernant la suite de Fibonacci, c'est que pour tout entier n, ben je me poserais la question de savoir si par hasard cette formule ça serait pas un cas particulier de ce que je doit démontrer.
Et là, si on a deux sous de bon sens, ben on voit que ça correspond au cas p=2 et n quelconque de la formule (vu que lorsque p=2).

Et arrivé à ce point là où j'ai vu que j'ai "gratos" le cas p=2 et n quelconque, ben je me dit que ce que je vais considérer, c'est la proposition (dépendant de p et de p seulement) qui dit :

Et que je vais démontrer par récurrence sur p que est vraie pour tout entier p>=1 (pour p=0 le n'a pas de sens)

[infernaleur]

Oui pardon l'initialisation doit être sur p=1 et p=2 !
(merci Ben314)

[puilo]

Merci beaucoup pour toutes vos réponses que j'ai lues attentivement !
J'ai réussi à faire ma récurrence sur p mais maintenant je dois donc faire de même pour n ?
Une autre petite précision : pourquoi initialiser sur 2 rangs ? Est-ce obligatoire dans ce cas ou juste plus simple pour la suite ?

[infernaleur]

Une récurrence double consiste à supposer ta propriété vrai pour deux rang (n0 et n0+1) et montrer qu'elle est vrai au rang (n0+2). En général ce principe de récurrence marche très bien quand tu as des suites du type a*U(n+2)=b*U(n+1)+c*U(n) car dans la partie hérédité tu auras une formule pour U(n) et U(n+1) tu pourras en déduire une relation pour U(n+2) grâce a la relation de récurrence a*U(n+2)=b*U(n+1)+c*U(n).
Mais pour cela il te faut donc démontrer dans l'initialisation qu'il EXISTE déjà deux rang où cette propriété est vrai sinon la récurrence n'aurais pas de sens.

[Ben314]

Je sais pas quelle sont les "indics" que tu as suivi (méa culpa : j'ai pas lu en détail les autres post...)
Mais si tu procède tel que je l'ai suggéré alors :
1) Tu n'a absolument rien à faire "par récurrence" concernant le vu que ce que tu démontre (par récurrence sur ) c'est la proposition "pour tout entier on a ..."
2) En procédant de la façon dont je te le suggère, tu n'a nulle besoin de faire une récurrence "double" : une récurrence suffit amplement (i.e. il suffit de supposer que c'est vrai pour un certain entier pour montrer facilement que c'est aussi vrai pour l'entier p+1)

[zygomatique]

Ben314 : alors regarde mon post :

pour ce qui concerne n c'est exactement ça : ce que j'ai écrit est valable pour tout n ...

par contre ma démonstration nécessite que ce soit vrai pour deux termes consécutifs et pour le montrer pour le terme ...

... et je ne vois pas vraiment comment on peut faire avec un seul terme ...

merci par avance

[Ben314]

Pour tout entier on considère la proposition :


Initialisation :
est trivialement vrai vu que et

Hérédité :
On suppose que, pour un certain entier on a (H.R) : .
et on doit montrer que : .
Soit donc un entier naturel quelconque. On a

par hypothèse de récurrence (on a bien )

[zygomatique]

ha oui ... tu me l'as fais ""à l'envers"" (pour la relation de Fibonacci)

merci beaucoup

[Ben314]

Sinon, s'il y en a que ça intéresse, toute ces propriétés concernant la suite de Fibonnacci, ça se démontre beaucoup plus aisément une fois constaté que avec .
Par exemple la propriété qu'on demande de démontrer ici, elle provient simplement du fait que

[zygomatique]

re ha oui ... effectivement le point de vu matriciel rend évident le résultat ...

merci