Récurrence triangulaire

Bonjour,

Auriez-vous des exercices faisant intervenir des récurrences triangulaires à me donner pour voir si j'ai bien compris le principe ?

c'est quoi la récurence triangulaire? ça a un rapport avec le raisonnement par récurence?

Oui, c'est une sorte de récurrence où l'on considère la propriété P(n) vraie JUSQU'AU rang n.

Arf, ça me dit rien, ça ressemble à quoi ? En tout cas j'ai jamais entendu le nom...

Oui, c'est une sorte de récurrence où l'on considère la propriété P(n) vraie JUSQU'AU rang n.

ouha! et on retrouve ce genre de méthode dans quel type d'exercice?

Je crois que c'est la même chose qu'une récurrence forte ou qu'une récurrence avec prédécesseurs...

mon prof de math ne connaissait pas la récurence trigulaire mais il dit quela description que tu en fait correspond à la récurence forte.

Dupleganger a écrit:mon prof de math ne connaissait pas la récurence trigulaire mais il dit quela description que tu en fait correspond à la récurence forte.

D'accord, je vois ce que c'est alors... mais si vous avez des exos, n'hésitez pas à les proposer.

Oui la plupart des gens appellent ça récurrence forte, je confirme. Ceci-dit, elle n'a rien de plus fort qu'une récurrence dite faible, les deux sont en fait équivalentes.

Si tu veux un exemple, en voici un simple sur la division euclidienne:
On veut montrer que pour tout entier naturel a et tout entier naturel non nul b, il existe deux entiers naturels q et r tels que a = bq + r et 0 <= r < b (on ne s'occuppe pas ici de l'unicité).
Il y a évidemment plein de manières de le démontrer mais tu peux faire une récurrence forte sur a (en distingant le cas 0<=a<b et a>=b et en utilisant alors a-b). Je te laisse faire.

matthias a écrit:Il y a évidemment plein de manières de le démontrer mais tu peux faire une récurrence forte sur a (en distingant le cas 0<=a<b et a>=b et en utilisant alors a-b). Je te laisse faire.

Oui, merci !

On l'a démontré avec un raisonnement Analyse-Synthèse aussi...

Pour moi, une recurrence forte est différente d'une recurrenece faible.
Quand tu fait une recurrence, tu dois initialiser à un certain rang, ensuite , tu suppose qu'il existe un rang pour lequel ça marche (en général c'est le rang n) et tu regardes si ça marche pour le rang suivant (n+1).

Sur une recurrence faible, le fait que ça marche pour le rang d'avant te servira a montrer que ça marche en n+1; Sur une recurrence forte tu devras utiliser le fait que ça marche pour TOUS les rangs précédents pour y arriver.

J'ai pas d'exemples, là comme ça mais j'en chercherais si tu veux.

Blad a écrit:Pour moi, une recurrence forte est différente d'une recurrenece faible.
Quand tu fait une recurrence, tu dois initialiser à un certain rang, ensuite , tu suppose qu'il existe un rang pour lequel ça marche (en général c'est le rang n) et tu regardes si ça marche pour le rang suivant (n+1).

Sur une recurrence faible, le fait que ça marche pour le rang d'avant te servira a montrer que ça marche en n+1; Sur une recurrence forte tu devras utiliser le fait que ça marche pour TOUS les rangs précédents pour y arriver.

J'ai pas d'exemples, là comme ça mais j'en chercherais si tu veux.

La différence n'est qu'une vue de l'esprit. Même si ça paraît bizarre on peut considérer une récurrence forte comme un cas particulier de récurrence faible (en fait récurrence tout cours, d'ailleurs pas mal de prof n'aiment pas cette distinction).
Une récurrence de base, c'est:
on considère une propriété P(n) qui ne dépend que de n.
On montre P(0) (ou un autre rang), P(n) => P(n+1)
et c'est fini.

Maintenant si je considère la propriété Q(n) = P(k) vrai pour 0<= k <=n, c'est bien une propriété qui ne dépend que de n. Faire une récurrence forte consiste à faire une récurrence normale en utilisant la propriété Q(n) à la place de P(n).

N'oublie pas que dans le cas d'une récurrence forte, il est parfois nécessaire de s'appuyer sur plusieurs cas de base.

ephemere a écrit:N'oublie pas que dans le cas d'une récurrence forte, il est parfois nécessaire de s'appuyer sur plusieurs cas de base.

Il faut toujours au moins deux bases, non ?

Et ça change quoi ?

matthias a écrit:Et ça change quoi ?

Ben je sais pas...