Une récurrence pas évidente...

[Pluume]

Bonjour à tous et à toutes !


J'arrive à la toute fin de mon DM de math (de sup), et les deux dernières questions portes sur des récurrences, mais je n'arrive vraiment pas à la mener à bien...

on me dis de me servir de la relation suivante: U_2n = 2U_n . ( U_n + U_n-1 )
étant donné qu'on me dis de me servir de cette relation, je ne donne pas toutes les info que j'ai sur la suite U trouvé dans toutes les questions précédentes. Surtout que je vois mal coment elle peuvent servir... Sauf peut être qu'on sait que si n est paire, U_n est paire...

(U est une suite)

je dois montrer par récurrence sur k la chose suivante:

- pour tout n appartenant aux entiers naturels, 2^k / n ===> 2^k / U_n

Attention: je ne savais pas comment faire les notations ici donc: ===> : "implique" et a/b veut dire "a divise b" et non pas "a divisé par b"


Si quelqu'un à une idée... Pour la deuxième récurrence j’essaierais de me débrouiller seul une fois que j'aurais compris la mécanique pour celle ci.

Merci d'avance pour vos réponses !
-----

[Amanuensis]

Si quelqu'un à une idée...

Hmm... Désolé de le présenter comme cela, mais cela paraît très simple, et la difficulté pour vous répondre de manière pédagogique (qui vous aide à apprendre) est alors d'essayer de comprendre ce qui vous bloque exactement.

Si je vous dis "récurrence sur k" plutôt que "récurrence sur n", est-ce que cela aide ?

[Pluume]

et bien même dans ce cas je ne vois pas trop le lien avec la relation qu'on nous demande d'utilisé...

et c'est l'implication dans le récurrence qui me gène... même l'initialisation ! Je ne vois pas en quoi le fait que 2⁰ divise n, implique que 2⁰ divise U_n


désolé c'est serrement évident mais je ne vois vraiment pas...

[Amanuensis]

Reprenons alors l'initialisation. C'est pour k=0, soit :

"Pour tout n appartenant aux entiers naturels, 1 divise n => 1 divise Un"

Ou encore "Si n est un multiple de 1, alors Un est un multiple de 1"

Est-ce clair pour vous que c'est vrai, pourquoi c'est vrai ? (Que veut dire "impliquer" en logique ?)

Voyez-vous de quelle récurrence il s'agit ?

[A voir en vidéo sur Futura]

[Pluume]

Oui effectivement, c'est vrai, mais tous les nombres sont multiple de 1, donc l'implication me gène... Pour moi une implication remplace un "si...., alors....." donc ici l'implication me gène.


Et comment ça quel type de récurrence ? Hmmm peut être qu'il faut utiliser une récurrence forte ?

[Amanuensis]

Oui effectivement, c'est vrai, mais tous les nombres sont multiple de 1, donc l'implication me gène... Pour moi une implication remplace un "si...., alors....." donc ici l'implication me gène.

OK, c'était effectivement une possibilité que j'avais envisagée. En maths il y a des fois où il faut être "bête", la table logique dit que "vrai implique vrai" est vrai, donc l'implication indiquée, aussi peu informative qu'elle soit, est vraie. Et cela permet d'initialiser la récurrence.

Et comment ça quel type de récurrence ? Hmmm peut être qu'il faut utiliser une récurrence forte ?

Ce n'était pas mon propos. Je vous invitais juste à écrire explicitement la relation de récurrence à démontrer.

[Médiat]

Pour moi une implication remplace un "si...., alors....."

Et vous avez raison, cependant, et c'est plutôt là que se trouve la source de votre gêne, vous y voyez, il me semble, à tort, une relation de cause à effet ; ici l'implication ne devrait pas vous gêner.

[Pluume]

et bien si on considère la proposition "2^k divise n implique 2^k divise U_n"

il faut démontrer que 2^k+1 divise n implique 2^k+1 divise U_n, donc l’hérédité. Enfin si je comprend bien le but de cette récurrence...

[Médiat]

Bonjour,

Vous pouvez remarquer que

Et plus simplement que .

^(*) La barre | se lit "divise".