Exemple d'incontournabilité du raisonnement par récurrence ?

jkent · June 2023

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

JLapin · June 2023

J'ai l'impression que le lemme des tiroirs (si $m<n$ alors il n'existe pas d'injection de $\llbracket 1,n\rrbracket$ sur $\llbracket 1,m\rrbracket$) est impossible à démontrer sans récurrence (ou un principe équivalent d'utilisation d'un entier minimal).

Ou encore, un fait aussi simple que "les termes de la suite de Fibonacci sont entiers".

Médiat_Suprème · June 2023

Si on se place dans l'arithmétique Peano, la commutativité de l'addition ne peut pas se démontrer sans récurrence (ainsi que plein d'autres choses)

Martial · June 2023

@Médiat_Suprème : Tu m'as coupé l'herbe sous les pieds, j'allais dire exactement la même chose. Grillé au poteau, GRRR... !

jkent · June 2023

MERCI beaucoup, j'imaginais des (H_n) compliquées mais je vois que ma question était idiote !, le vieillard que je suis en est ravi. L'exemple de Fibo me semble le plus simple, splendide ! ben oui, parler de la preuve de la commutativité de l'addition à des élèves me semble être disons risqué ...
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 !

))

Médiat_Suprème · June 2023

L'exemple de Fibonacci me semble "truqué" : si on part de sa définition usuelle, qui est récurrente, tout ce que l'on pourra en dire, partira de la définition et donc sera récurrente (et c'est vrai pour toutes les suites récurrentes).

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.

Médiat_Suprème · June 2023

@Martial : pour une fois que je suis le premier

JLapin · June 2023

Dans ce cas, l'exemple de la commutativité est truqué puisque les entiers sont fondamentalement définis par récurrence également

Médiat_Suprème · June 2023

Ils ne sont pas définis par récurrence, la théorie arithmétique de Peano inclut les axiomes de récurrence (c'est purement syntaxique), si on veut une démonstration qui exige la récurrence, il suffit de regarder les théorèmes de Peano qui ne sont pas des théorèmes de Robinson (comme la commutativité de l'addition)

john_john · June 2023

Médiat Suprême : avec la définition des $F_n$ comme éléments de $\Q(\sqrt5)$, la preuve par récurrence est tout de même plus pratique que le développement binomial qui fournit un dénominateur $2^{n-1}$.

Médiat_Suprème · June 2023

Je n'ai jamais dit que c'était plus pratique, je répondais à la question "Peut-on se passer de la récurrence ?", et la réponse est oui (dans ce cas)

Math Coss · June 2023

Le dénominateur ne compte pas si on se permet d'utiliser la notion d'entier algébrique (et la stabilité de ladite notion par somme et produit). C'est sans doute un peu trop sophistiqué pour la situation...

john_john · June 2023

Médiat Suprême : je veux bien, mais comment démontres-tu que $2^n$ divise le numérateur, après la simplification des $\sqrt5$ ?

gai requin · June 2023

Pour préciser le message de @Math Coss, Galois dit que, pour tout $n$, $F_n\in\Q$ et une minuscule factorisation montre que $F_n$ est un entier algébrique donc $F_n\in\Z$.

JLapin · June 2023

Alors je propose le théorème d'existence de la décomposition en facteurs premiers.

Dom · June 2023

Exercice trivial :
Soit $u$ la suite définie par : $u_0=1$ et pour tout entier naturel $n$, $u_{n+1}=u_{n}$.

Pour démontrer que c’est la suite constante égale à $1$ (i.e. : pour tout entier naturel $n$, $u_n=1$), peut-on se passer d’un raisonnement par récurrence ?

Médiat_Suprème · June 2023

Comme je le disais plus haut, pour une suite définie par récurrence, il n'y a aucun moyen de se passer de récurrence, ne serait que pour parler de cette suite.

Dom · June 2023

Oui j’aurais dû être plus attentif.

Je pensais aussi au symbole $\Sigma$ ou à la définition des puissances entières.

On est déjà dans la récurrence par définition.

Médiat_Suprème · June 2023

@JLapin : est-ce qu'une régression ne suffit pas ? C'est à vérifier, je n'affirme pas (même si la récurrence est plus simple et plus élégante)

john_john · June 2023

J'avoue ne pas voir comment prouver que $F_n$ est entier sans l'artillerie des entiers algébriques (ce n'est pas de l'artillerie lourde mais cela n'est pas non plus élémentaire).

samok · June 2023

Bonsoir jkent,
je trouve chouette votre question.
Je ne comprends pas ce que signifie : 'La récursivité n'a pas d'expressivité intrinsèque'.

Il y a quelques années (genre 10-15 ans) un intervenant atypique écrivait (du moins dans ma mémoire) qu'un nombre entier était pair passait forcément par une récurrence.

Je trouve votre question chouette parce que je la comprends, ce qui me fait scier, c'est que je ne comprends rien aux réponses. Je me demande si je suis un handicapé mental ou s'ils se fichent de nous avec leurs théories.
Bien à vous.

[Utilisateur supprimé] · June 2023

Une suite de nombres incalculables définie par recurrence ?

Georges Abitbol · June 2023

Je crois que j’ai lu une fois un truc qui disait : on se place dans le formalisme des fonctions calculables, et on considère les programmes définis sans récurrence (i.e. on n’a pas le droit de poser « soit $g(n)$ le plus petit entier $m$ tel que $f(n,m)$ vérifie truc »). Alors le problème de l’arrêt est décidable pour ces programmes (expertes et experts, corrigez-moi si je dis une bêtise). L’auteur concluait que par conséquent, comme le problème de l’arrêt n’est pas décidable, il y a des programmes qu’on ne peut faire qu’avec des récurrences.

Renart · June 2023

@john_john. Une idée comme ça. En utilisant la factorisation de $a^n-b^n$ par $a-b$ on trouve \[F_n = \phi^{n-1}+\phi^{n-2}\phi'+ \dots + \phi \phi' ^{n-2}+\phi'^{n-1} = P(\phi,\phi'),\] où $\phi = (1+\sqrt 5 )/2$ et $\phi'= (1-\sqrt 5)/2$. Comme $P$ est un polynôme symétrique en deux variables à coefficients dans $\Z$ et puisqu'on l'évalue en les racines de $X^2-X-1\in \Z[X]$ on en déduit que $F_n$ est entier. Ceci demande de savoir que tout polynôme symétrique se décompose à l'aide des polynômes symétriques élémentaires. D'après wikipédia on démontre cela par une récurrence sur un ordre lexicographique dans $\N^n$. Mais j'ai l'impression qu'on peut reformuler ça sans récurrence, on a un polynôme symétrique et un algorithme qui diminue l'ordre lexicographique maximal de ses monômes donc une bête majoration montre que l'algorithme aboutit au polynôme nul en au plus $k$ étapes avec $k\in \N$ ne dépendant que du polynôme de départ.
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

john_john · June 2023

Renart : oui, cela me convainc (d'ailleurs, parce que $X^2-X-1$ est unitaire à coefficients entiers -- on rejoint la notion d'entier algébrique) et bien entendu, on ne peut réfuter cela au nom de l'interdiction des récurrences car, à cette aune, il ne resterait plus rien des maths.
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

Foys · June 2023

john_john a dit :

on ne peut réfuter cela au nom de l'interdiction des récurrences car, à cette aune, il ne resterait plus rien des maths.

On peut faire plus de choses que ce que les gens s'imaginent sans récurrence. Voir par exemple ce livre: https://projecteuclid.org/eBooks/perspectives-in-logic/Metamathematics-of-First-Order-Arithmetic/toc/pl/1235421926 et en particulier son chapitre V, ou encore l'ultraprovocateur (mais pour le coup très pédagogique) predicative arithmetic d'Edward Nelson (qui peut servir d'introduction technique au livre précédent; voir ici: https://web.math.princeton.edu/~nelson/books/pa.pdf).

Exemple d'incontournabilité du raisonnement par récurrence ?

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 14