Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann AnalyseTopics traitant de analyse [tout]Lister tous les topics de mathématiques

1 2 +

Niveau Licence Maths 1e ann
Partager :

Récurrence avec deux entiers

Posté par
gigi-75 26-02-13 à 02:41

Bonsoir

Je dois montrer par recurrence que pour tout n et tout k * ...

Comment faire lorsqu'on a deux entiers ?

Faire l'hypothèse HR en fonction des deux entiers HR(n,k) ?

Pour l'initialisation, montrer que HR(0,1) est vraie ?

Ensuite supposer HR(n,k) vraie, et montrer que HR(n+1,k+1) vraie ?

Je ne me suis jamais trouvé dans un tel cas, c'est le moment de se poser la question
Désolé d'avance si ce sont de gros bétises ;D

Posté par
abou-salmare : Récurrence avec deux entiers 26-02-13 à 04:23

bonjour,

L'important est de couvrir FORMELLEMENT l'ensemble x*.

Avec votre méthode vous commencez par (0,1), puis à chaque récurrence vous incrémentez tant l'abscisse que l'ordonnée. Ce qui fait que vous couvrez uniquement l'ensemble {(0,1), (1,2), (2,3), (3,4),... } = {(n,n+1) | n } .

Par contre, pour couvrir l'ensemble x* vous pouvez par exemple effectuer :
- supposer HR(n,k) vraie et montrer à la fois que : HR(n,k+1) vraie (1), et HR(n+1,k) vraie (2)

Vous pouvez également procéder en 2 étapes :
1. couvrir {0}x*
2. couvrir x{i}, où i > 0
ce qui permets également de couvrir FORMELLEMENT x*

Posté par
LeDinore : Récurrence avec deux entiers 26-02-13 à 04:25

Ca peut dépendre de la question posée.
Parfois, la récurrence ne porte que sur l'une des deux variables (l'autre ne nécessite pas de récurrence dans la démonstration).
Sinon s'il s'agit d'une vraie récurrence à deux variables, tu dois pouvoir t'en sortir par étapes, variable par variable.

Appelons Pn,m la propriété à démontrer aux rangs n,m.
(1) Prouver P1,1
(2) Prouver que si P1,m alors P1,m+1   (ce qui prouve P1,m pour tout m)
(3) Prouver que si Pn,m alors Pn+1,m   (ce qui prouve Pn,m pour tout n et tout m)

Posté par
LeDinore : Récurrence avec deux entiers 26-02-13 à 04:27

Précision :
Partir de n=0 et k=1 si n et k*...

Posté par
LeDinore : Récurrence avec deux entiers 26-02-13 à 04:30

En fait gigi tu n'étais pas loin.
Il te manquait juste une étape...

Avec tes notations :
Pour l'initialisation, montrer que HR(0,1) est vraie.
Ensuite supposer HR(0,k) vraie, et montrer que HR(0,k+1) vraie.
Ensuite supposer HR(n,k) vraie, et montrer que HR(n+1,k) vraie.

Posté par
gigi-75re : Récurrence avec deux entiers 26-02-13 à 12:45

Bonjour.
Merci a vous deux

Je vais essayer la méthode de LeDino et je reviens vers vous si cela ne va pas

Posté par
gigi-75re : Récurrence avec deux entiers 26-02-13 à 13:10

Voilà la récurrence à faire :

n, k*

22n-1 = (22n-1) \prod_{i=0}^{k-1} 2^{2n+i}+1

Posté par
gigi-75re : Récurrence avec deux entiers 26-02-13 à 13:16

Si on part de HR(0,k) vraie, le membre de droit vaut 0 à cause de (22n-1) :-\

Ca pose problème non ?

Posté par
gigi-75re : Récurrence avec deux entiers 26-02-13 à 13:20

On pourrait supposer HR(n,k) vrai, et montrer d'une part HR(n,k+1) vraie, et d'autre part HR(n+1,k) vraie ?

Posté par
GaBuZoMeure : Récurrence avec deux entiers 26-02-13 à 13:54

Ton égalité est mal écrite, zr assez incompréhensible. Ecris-la avec plus de soin. Tu disposes du bouton "Aperçu" pour vérifier si ce que tu as écrit est bien ce que tu voulais écrire.

Posté par
gigi-75re : Récurrence avec deux entiers 26-02-13 à 13:56

Je ne comprends pas
La formule est bien écrite ?!

je vois la formule parfaitement moi

Posté par
gigi-75re : Récurrence avec deux entiers 26-02-13 à 13:57

22n+k-1 = ... (donner plus haut)

Posté par
GaBuZoMeure : Récurrence avec deux entiers 26-02-13 à 14:24

Pas si parfaite que ça, n'est-ce pas ? Tu as corrigé une erreur (est-ce la bonne correction ?). Il en reste pas mal. Si on lit le membre de droite suivant les règles de priorité des opérations, on trouve \left((2^{2n}-1)\times 2^{2nk+k(k-1)/2}\right) +1. Est-ce vraiment ça que tu voulais écrire ?

Posté par
gigi-75re : Récurrence avec deux entiers 26-02-13 à 14:27

Pardon, dans le membre de droite, le +1 est compris dans le produit, le reste est bon

Posté par
GaBuZoMeure : Récurrence avec deux entiers 26-02-13 à 14:31

Prenons n=1 et k=1. On aurait à montrer
2^3-1= (2^2-1)\times (2^2+1)
Tu plaisantes ? Pourrais-tu donner un énoncé correct ?

Posté par
gigi-75re : Récurrence avec deux entiers 26-02-13 à 19:56

L'énoncé est correcte

Posté par
LeDinore : Récurrence avec deux entiers 26-02-13 à 20:53

Tu peux le redonner de manière complète et exacte s'il te plait ?
Parce qu'avec un k qui traine ici et un +1 par là... on n'est sûr de rien.

Enfin si tu veux de l'aide bien sûr ...

Posté par
GaBuZoMeure : Récurrence avec deux entiers 26-02-13 à 21:21

D'accord, l'énoncé est correct, et on a 7=3\times 5.

Posté par
GaBuZoMeure : Récurrence avec deux entiers 26-02-13 à 21:46

Dans la grande série "Devinez l'énoncé correct", je propose
2^{nk}-1 = (2^n-1)\times \sum_{i=0}^{k-1} 2^{ni}
qui présente l'avantage d'être correct, et trivial.

Posté par
LeDinore : Récurrence avec deux entiers 26-02-13 à 23:56

Si c'était ça il n'y aurait pas besoin de récurrence, simple ou double...

Mais à ce niveau de foutage de gueule, on peut effectivement s'attendre à tout ...

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 01:25

Ce n'est absolument pas l'énoncé de mon exercice

Je sais qu'il est interdit de faire une capture du sujet, mais pour éviter toutes éventuelles erreurs de recopiage de ma part le voici

(Les ADMINS, c'est juste pour confirmer mon sujet )

Récurrence avec deux entiers

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 03:12

Apparemment tu sais écrire en LATEX...
C'était pas bien compliqué à donner :

2^{2n+k} - 1 = (2^{2n}-1) \times \prod_{i=0}^{k-1} (2^{2n+i}+1)

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 03:19

H(n=0;k=1) est FAUSSE :  

2^{0+1} - 1 = (2^{0}-1) \times \prod_{i=0}^{0} (2^{i}+1)
\implies 1 = (0) \times (2) = 0

Donc il y a toujours une coquille ...

Posté par
GaBuZoMeure : Récurrence avec deux entiers 27-02-13 à 10:00

J'avais déjà signalé, pour n=k=1, la magnifique conséquence de l'égalité de l'exercice 3 : 7=3\times 5.
Il semble que l'éditeur du bouquin ne savait pas faire les doubles exposants
2^{2^{n+k}}=(2^{2^n}-1)\,\prod_{i=0}^{k-1} (2^{2^{n+i}}+1)

Posté par
GaBuZoMeure : Récurrence avec deux entiers 27-02-13 à 10:33

Si j'ajoute des coquilles moi aussi, ça ne va pas faciliter la compréhension ;
2^{2^{n+k}}-1=(2^{2^n}-1)\,\prod_{i=0}^{k-1} (2^{2^{n+i}}+1)
Une simple récurrence sur k suffit. On peut d'ailleurs commencer à k=0, si on sait qu'un produit indexé par la famille vide vaut 1.

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 11:54

Bonjour
Merci de vos réponses

Donc il me,suffit simplement de faire une récurrence sur k et laisser n tel quel ?

Posté par
GaBuZoMeure : Récurrence avec deux entiers 27-02-13 à 11:55

Ne crois jamais aveuglément ce qu'on te dit : essaie toujours par toi-même.

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 12:01

Si vous me dite qu'on peut, je vais le faire
Mais si je le fais et qu'on peut pas, je vais faire une erreur pour que ça marche

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 13:46

Si je fais l'initialisation à k=1
Il y a un petit problème avec le produit

Vous avez dit qu'il fallait savoir qu'un produit indexé par une famille vide vaut 1 mais si on ne sait pas ce que cela veut dire ?

Posté par
GaBuZoMeure : Récurrence avec deux entiers 27-02-13 à 13:50

Où est le problème si tu fais k=1 ?

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 13:57

Bon sang gigi arrête de faire le zouave et réfléchis un peu.

Partir de k=0 c'est une "fioriture" qui ne sert à rien.

Tu commences à partir de k=1 comme le suggère l'énoncé (k>0).
Avec k=1, ton produit contient un seul terme.
Ecris le et tu verras que tu obtiens une identité remarquable.
Et ensuite...

Mais bosse un peu quand même !

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 14:01

Et une fois démontrée H(n quelconque, k=1), tu n'as plus qu'à faire une récurrence SIMPLE sur k.
Tout simplement parce qu'ici tu es capable de démontrer directement  H(n,k=1) pour tout n.


Et par pitié : RE-FLE-CHIS !

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 14:12

Pour k = 1

Je trouve 22n-1 (22n-1)(22n+1)

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 14:15

22n+1 pardon

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 15:09

(a-b)(a+b) = a² - b²

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 15:11

Et ton résultat est mal écrit... Tu as encore oublié les exposants d'exposants...

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 15:12

Ce qui nous donne 44n -1

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 15:15

H(n,k) :

2^{2^{n+k}}-1=(2^{2^n}-1)\,\prod_{i=0}^{k-1} (2^{2^{n+i}}+1)

H(n,k=1) :

2^{2^{n+1}}-1=(2^{2^n}-1) \times (2^{2^{n}}+1) = ...

Identité remarquable (a-b)(a+b) pour le terme de droite.

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 15:17

Citation :
Ce qui nous donne 44n -1

Ca... on va dire que tu l'as pas écrit .
Ce sera mieux pour tout le monde...

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 15:20

Ah ce sont des doubles exposants ?

Ce n'est pas ce qui est dans le sujet
Mais effectivement cela marche si ce sont des doubles exposants

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 15:23

Citation :
Ah ce sont des doubles exposants ?

Je rêve !  Tu n'as pas lu les messages de GaBuZoMeu   ???

C'est un sketch que tu nous fais là...

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 15:25

Merci de votre aide, il faut mieux qu'on en reste la

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 15:31

D'accord on en reste là.

Pour info, le problème est quasi résolu.
Tu termines de prouver H(n,1) il y en a pour trente secondes avec l'identité remarquable.

Ensuite tu supposes H(n,k) VRAIE et tu regardes si H(n,k+1) est VRAIE également...
... ce qui ce montre de la même manière que H(n,1) par la même identité remarquable ET après avoir coupé le produit en deux : produit de 1 à k-1 fois produit de k à k.

Bon courage.
Et essaie de devenir un peu plus autonome parce que là tu te reposes intégralement sur les autres (ce qui ne t'aidera pas à progresser)... et sans vraiment les écouter de surcroit.

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 15:35

Merci pour votre patience, et vos conseils
À bientôt

Posté par
LeDinore : Récurrence avec deux entiers 27-02-13 à 15:45

Je te souhaite sincèrement bon courage.
Si tu réussis à terminer l'exercice (qui est à ta portée si tu avances pas à pas et que tu soignes ton écriture), viens nous le dire : ça nous fera plaisir .

Posté par
gigi-75re : Récurrence avec deux entiers 27-02-13 à 19:03

Pas de soucis
Je vous tiens au courant des que j'ai fini

Posté par
gigi-75re : Récurrence avec deux entiers 02-03-13 à 02:26

Bonsoir

Depuis mon dernier message, j'essaie de faire l'hérédité, et je n'ai pas avancé d'un poil car je suis bloqué au début de l'hérédité !

J'essaie d'écrire 2^{2^{n+k+1}}-1 = 2^{2^{n+k}} 2^{2^{k}}

Je voudrais écrire sous la forme  (2^{2^{n+k}}-1) * quelque chose ...
et ainsi remplacer  (2^{2^{n+k}}-1) par l'hypothèse de récurrence...

Mais je ne trouve pas ce quelque chose, les puissances me perturbent, et m'empêche de trouver :-\

Posté par
LeDinore : Récurrence avec deux entiers 02-03-13 à 04:36

Il faut commencer par prouver H(n,k=1). L'as-tu fait ?


Rappel sur H(n,k) à prouver :

\boxed { 2^{2^{n+k}}-1=(2^{2^n}-1)\,\prod_{i=0}^{k-1} (2^{2^{n+i}}+1) }

On commence par prouver H(n,k=1), pour tout n de N, donc :

2^{2^{n+1}}-1 = (2^{2^n}-1) \times (2^{2^{n}}+1)

Partons du membre de droite (qui est une identité remarquable) :

(2^{2^n}-1) \times (2^{2^{n}}+1) = (2^{2^n})^2 - 1^2 = 2^{2.2^n} - 1 = 2^{2^{n+1}} - 1

\implies \boxed { (2^{2^n}-1) \times (2^{2^{n}}+1) = 2^{2^{n+1}} - 1 }   CQFD


Donc H(n,k=1) est bien prouvée pour tout n

Posté par
LeDinore : Récurrence avec deux entiers 02-03-13 à 05:01

Donc à ce stade, nous avons "initialisé" la récurrence simple.
En effet H(n,k) est prouvée pour tout n et pour k=1.

Il reste à prouver l'hérédité, c'est à dire :    H(n,k)    H(n,k+1)


H(n,k) :       \boxed{  2^{2^{n+k}}-1 = (2^{2^n}-1)\,\prod_{i=0}^{k-1} (2^{2^{n+i}}+1)  }    Supposée VRAIE

H(n,k+1) :    \boxed{  2^{2^{n+k+1}}-1 = (2^{2^n}-1)\,\prod_{i=0}^{k} (2^{2^{n+i}}+1)  }    A vérifier...


On part du membre de droite :

(2^{2^n}-1) \prod_{i=0}^{k}(2^{2^{n+i}}+1) = (2^{2^n}-1)\prod_{i=0}^{k-1} (2^{2^{n+i}}+1) \times (2^{2^{n+k}}+1)=(2^{2^{n+k}}-1) \times (2^{2^{n+k}}+1)

(2^{2^n}-1)\prod_{i=0}^{k} (2^{2^{n+i}}+1) = (2^{2^{n+k}})^2 - 1^2 = 2^{2.2^{n+k}} - 1 = 2^{2^{n+k+1}} - 1

On a donc bien :    \boxed {  (2^{2^n}-1)\prod_{i=0}^{k} (2^{2^{n+i}}+1) = 2^{2^{n+k+1}} - 1  }    H(n,k+1) est vérifiée, CQFD

Posté par
gigi-75re : Récurrence avec deux entiers 02-03-13 à 10:32

Bonjour

Quand je me suis couché, j'ai en effet pensé à faire celui de droite qui pourrait éventuellement être plus facile

Merci a vous de votre aide
Et bonne journée

1 2 +


Rechercher
Menu
Espace membre
13 visiteurs
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1724 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !