Récurence

[invite56460777]

Bonjour,

Voilà , si on a une suite qui est définie par ses deux premiers termes puis U_n est exprimée en fonction de U_(n-2) et de U_(n-1)

On veut montrer que U_n peut aussi être égale à une autre expression exprimée uniquement en fonction de n (par ex. U_n= kn +t)

J'ai vérifié que notre nouvelle expression de U_n donnait le même résultat que la première expression de U_n

Je voudrais savoir si j'ai le droit de prendre comme hypthèses de recurrence que :
la nouvelle expression est vraie pour un n et qu' elle est aussi vraie pour n-1

car je voudrais partir de k(n+1) +t = ...
Pour arriver à k(n+1) +t = rU_(n-1) + vU_(n) = U_(n+1)

Sinon je ne vois pas comment on peut résoudre ce genre de récurrence
-----

[shokin]

La démonstration par récurrence, il me semble que c'est démontrer deux choses :

démontrer que c'est vrai pour U1

démontrer que : si c'est vria pour Un, alors c'est vrai pour Un+1

Shokin

[invite56460777]

Je sais bien, mais regarde dans le cas des nombres de fibonnaci

http://forums.futura-sciences.com/sh...ad.php?t=19715

si je suppose que c'est vrai uniquement pour n

alors je ne peux réussir à affirmer que j'ai fait apparaitre fib (n) mais je ne peux pas affirmer à 100% que l'autre élément est bien fib (n-1) à moins de l'avoir supposé

[shokin]

Pour Fibonnaci, comme un terme dépend des deux précédents, tu dois montrer (aussi par récurrence) que :

ça marche pour n=0
ça marche pour n=1
si ça marche pour n et n+1, alors ça marche pour n+2

Je vais aller voir ça pour le cas Fibonnaci dont je ne connaissais pas ce théorème.

Shokin

[A voir en vidéo sur Futura]

[invitef6a8dd1c]

Salut,

Je dirais que tout dépend de ce que tu prends comme hypothèse de récurrence:
Si tu considères H(n) une proposition (hypothèse de récurrence) qui dépend de n, le raisonnement par récurrence consiste en effet à montrer que H(0) est vraie, puis que si H(n) est vraie, alors H(n+1) est vraie.
Dans le cas des nombres de Fibonacci, rien ne t'empêche d'écrire comme proposition:

H(n): pour tout k <= n, fib (k) = ( P^k - Y^k)/ racine carrée de 5
avec les notations utilisées dans ce fil.

Tu "bénéficies" alors de tout ce dont tu as besoin pour la démonstration par récurrence, en n'utilisant qu'un seul indice n.

Geoffrey

[Evil.Saien]

shokin, quelqu'un de cultivé comme toi ne connaissait pas le théorème !
Pourtant il est bien connu et très utile puisqu'il donne la population des genérations de lapins

Cetres geof, mais comme tu dit qu'il faut le demontrer par recurence, tu vas bien devoir ecrire Un+1 qui est donné en fonction de Un et Un-1... Résultat, pas juste un indice, ni deux mais 3

[invitef6a8dd1c]

Salut,

Ok, si tu comptes n+1 et n, alors 2 indices
Et 3, en effet, si tu considères la suite de Fibonacci uniquement, mais pas si tu considères la proposition H, puisqu'elle intègre tous les indices <= n (bien que n-1 et n suffisent).

Il ne s'agit que d'une astuce de logique, pour se conformer à une définition communément admise de la démonstration par récurrence, et rappelée par Shokin dans son premier message de ce fil.

Geoffrey

[shokin]

shokin, quelqu'un de cultivé comme toi ne connaissait pas le théorème !
Pourtant il est bien connu et très utile puisqu'il donne la population des genérations de lapins ;-

Désormais, je saurai !

et pour la démo ? quelqu'un a trouvé ?

Shokin

[Evil.Saien]

ben moi j'l'ai fait, suffit de calculer
fib(n+1) - fib(n) - fib(n-1) et on trouve 0...
On en déduit alors que fib(n+1) = fib(n) + fib(n-1) = (p^(n+1) - y^(n+1)) / rac5