Exemple d'incontournabilité du raisonnement par récurrence ?
Bonjour
Désolé ma question est probablement idiote pour un logicien.
J'ai souvent prouvé avec mes élèves des propositions, disons du type (H_n), n étant un entier, n > 0,
avec des raisonnements par récurrence en 'montrant' souvent à quel point sans ce procédé la preuve aurait été difficile.
Je ne me souviens plus, je suis retraité de l'Educ Nat, si j'avais trouvé un exemple de proposition indémontrable sans ce procédé de récurrence.
Est ce possible ?
Il y a quelques années années, enseignant ISN ou NSI je ne sais plus, j'avais posé sur un forum cette question un peu semblable
'est ce que tout programme récursif, dans un langage correct genre Python, Java etc... (je crois me souvenir qu'on dit 'Turing-complet'), a un équivalent non récursif '? Quelqu'un de l'INRIA m'avait répondu 'Oui. La récursivité n'a pas d'expressivité intrinsèque', théorème d'informatique théorique que j'ai admis bien que ne sachant pas le prouver.
Cordialement
Désolé ma question est probablement idiote pour un logicien.
J'ai souvent prouvé avec mes élèves des propositions, disons du type (H_n), n étant un entier, n > 0,
avec des raisonnements par récurrence en 'montrant' souvent à quel point sans ce procédé la preuve aurait été difficile.
Je ne me souviens plus, je suis retraité de l'Educ Nat, si j'avais trouvé un exemple de proposition indémontrable sans ce procédé de récurrence.
Est ce possible ?
Il y a quelques années années, enseignant ISN ou NSI je ne sais plus, j'avais posé sur un forum cette question un peu semblable
'est ce que tout programme récursif, dans un langage correct genre Python, Java etc... (je crois me souvenir qu'on dit 'Turing-complet'), a un équivalent non récursif '? Quelqu'un de l'INRIA m'avait répondu 'Oui. La récursivité n'a pas d'expressivité intrinsèque', théorème d'informatique théorique que j'ai admis bien que ne sachant pas le prouver.
Cordialement
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Alors une autre question, peut être encore pire : dans le domaine des probas discrètes avez-vous un exemple de question non traitable sans la bête formule du complémentaire, P(A_barre)= 1 -P(A) qui simplifie parfois énormément la tâche ? Bon après je quitte ce forum ! ))
Si on part de $F_n = \frac{1}{\sqrt 5}\left((\frac{1+\sqrt 5}{2})^n - (\frac{1-\sqrt 5}{2})^n\right)$, la nécessité de la récurrence ne saute plus aux yeux, en particulier pour prouver que ce sont des entiers.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
J'affirme péremptoirement que toute affirmation péremptoire est fausse
J'affirme péremptoirement que toute affirmation péremptoire est fausse
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Soit $u$ la suite définie par : $u_0=1$ et pour tout entier naturel $n$, $u_{n+1}=u_{n}$.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
J'affirme péremptoirement que toute affirmation péremptoire est fausse
je trouve chouette votre question.
Je ne comprends pas ce que signifie : 'La récursivité n'a pas d'expressivité intrinsèque'.
Bien à vous.
Bon mais peut-être que tout ça est équivalent à l'utilisation d'une récurrence (ou à ce que math coss et gai requin suggèrent) ou qu'il y en a une autre cachée que je n'ai pas vue. Dans tous les cas ce n'est pas ce que j'appellerais "élémentaire" quand la question de départ est de montrer que $F_n$ est entier
Il y a un demi-siècle, le résultat que tu invoques était enseigné en Math Sup et donc peut être considéré comme élémentaire.
En outre, je pense qu'il y a plus urgent que de se demander si $2^{n-1}$ divise le numérateur sans passer par ce qui précède