récurrence

BJR!
Montrer par récurrence que:
qq soit n dans IN avec n>=24, il existe p et q dans IN tq, n=5p+7q.

Indice, savoir que : -1 = 7x2 - 5x3

oussama1305 a écrit:

Indice, savoir que : -1 = 7x2 - 5x3

BJR !!
Celà s'appelle l'Identité de BEZOUT ... 7 et 5 sont PREMIERS entre EUX !!

Amicalement !! LHASSANE

salam

dans Z aucun problème : 5 et 7 premiers entre eux , 5p+7q=n , admet toujours des solutions.

comme : 5.3 + 7.(-2) = 1 ===> 5.(3n) + 7.(-2n) = n

......................................................................

dans IN c'est autre chose

24 = 5.2+7.2
25 = 5.5+7.0
26 = 5.1+7.3
27 = 5.4+7.1
28 = 5.0+7.4
-------------------
29 = 24 +5 = 5.3+7.2
30 = 25 +5 = 5.6+7.0
etc........
......

donc c'est un phénomène périodique

====> pour tout n >= 24 : 5p+7q = n admet un couple solution dans IN²

.........................................................

BJR Mr houssa !!

C'est VRAI et je n'ai pas attentivement lu l'énoncé .....
Autant pour Moi !! Merci Beaucoup ....

LHASSANE

achraf_djy a écrit:

BJR!
Montrer par récurrence que:
qq soit n dans IN avec n>=24, il existe
p et q dans IN tq, n=5p+7q.

BJR Achraf !!

Je reviens sur cet exercice que tu as posé pour y apporter
une Solution basée sur la RECURRENCE .... celà satisfaira sans doute Melle Betty !!
Bien entendu , la réponse de Mr houssa m'a beaucoup inspiré .

La Propriété est VRAIE pour n=24 puisque 24=10 + 14=5.(2) + 7.(2)

Hypothèse de Récurrence :
Supposons que pour un entier naturel n , n>=25 il existe deux autres entiers p et q tels
que l'on ait n=5.p + 7.q

ALORS considérons n+1=5.p + 7.q + 1
Plusieurs cas peuvent alors se produire :

1) q=0 auquel cas n=5.p + 1 ; de toutes les manières puisque n>=25 alors 5.p>=24 donc
p>=5 . Il suffira d'écrire n+1=5.(p-4) + 7.(3) et le Tour est Joué ....
2) q=1 auquel cas n=5.p + 7 ; 5.p=n-7>=18 donc p>=4 donc n+1=5.p + 8
On écrira alors n+1=5.(p-4) + 7.(4) ......
3) q=2 auquel cas n=5.p + 14 donc n+1=5.p + 15=5.(p+3) + 7.(0)

ENFIN :

4) q>=3 alors n+1=5.p + 7.q + 1
que l'on réécrira sous la forme n+1=5.p + 7.(q-2) + 15=5.(p+3) + 7.(q-2)
et celà marche encore ....

Conclusion : on a bien trouvé dans toutes les éventualités deux entiers naturels r et s tels
que n+1=5.r + 7.s


Ce qui achève la démonstration .

Amicalement . LHASSANE

Bonsoir à vous tous
Si vous le permettez M.Lhassane , j'ai une méthode qui s'appuie sur ce qu'a dit oussama.

on veut prouver que :n+1=7q'+5p'
on sait que 1=5.3+7(-2)
puisqu'on a supposé n=5p+7q
alors n+1=5(3+p)+7(q-2)=5p'+7q'
Sauf erreur
et merci

tarask a écrit:

Bonsoir à vous tous
Si vous le permettez M.Lhassane , j'ai une méthode qui s'appuie sur ce qu'a dit oussama.

on veut prouver que :n+1=7q'+5p'
on sait que 1=5.3+7(-2)
puisqu'on a supposé n=5p+7q
alors n+1=5(3+p)+7(q-2)=5p'+7q'
Sauf erreur
et merci

BSR tarask !!

Je veux bien .... MAIS , il faudra veiller à ce que :
p'=3+p et q'=q-2 soient des ENTIERS natuels !!
Si le problème ne se pose pas pour p'=3+p , il le pourrait pour q'=q-2 !!!

Amicalement . LHASSANE

Bison_Fûté a écrit:

tarask a écrit:

Bonsoir à vous tous
Si vous le permettez M.Lhassane , j'ai une méthode qui s'appuie sur ce qu'a dit oussama.

on veut prouver que :n+1=7q'+5p'
on sait que 1=5.3+7(-2)
puisqu'on a supposé n=5p+7q
alors n+1=5(3+p)+7(q-2)=5p'+7q'
Sauf erreur
et merci

BSR tarask !!

Je veux bien .... MAIS , il faudra veiller à ce que :
p'=3+p et q'=q-2 soient des ENTIERS natuels !!
Si le problème ne se pose pas pour p'=3+p , il le pourrait pour q'=q-2 !!!

Amicalement . LHASSANE

ça c'est une faute impardonnable de ma part !
Merci pour la rectification

Bsr
Merci Mr Lhssane

achraf_djy a écrit:

BJR!
Montrer par récurrence que:
qq soit n dans IN avec n>=24, il existe p et q dans IN tq, n=5p+7q.

BJR à Toutes et Tous !!

De Rien , Melle Betty ...
Maintenant , J'aimerais vous poser une Question .

Pourquoi ce résultat n'est VRAI qu'à partir de 24 ????

Bonne Journée & Bonnes Plages Encore ....

LHASSANE

Salam M LHASSANE!
Merci pour l'intervention.
La relation est vraie pour:
n=5, 7, 12, 17, 19 mais elle ne peut pas être vraie pour n=2,3... mais à partir de 24 la relation reste toujours vraie, donc il faut que n soit >= à 24 pour que la relation reste toujours juste.
B journée à vous!

BJR Achraf !!

OUI , c'est tout à fait celà !!
Pour la récurrence , il y a l'INITIALISATION c'est à dire : pour quelle entier N0 la Propriété est-elle VRAIE au DEPART !!

On ne peut pas l'initialiser avant 24 car par exemple si on choisit de l'initialiser à N0=17 ( elle est VRAIE pour 17=5.(2)+7.(1) ) MAIS elle ne passe pas à 18 donc la Propriété ne serait pas TRANSMISSIBLE à l'entier suivant ....

Amicalement . LHASSANE

Autre idée de démonstration :
On vérifie la propriété pour n=24 jusqu'à n=47.
Ensuite, par récurrence forte, on suppose la propriété vraie jusqu'au rang n (n>=24), et on montre qu'elle l'est aussi au rang n+1.
- Si n+1 est compris entre 24 et 47, alors la propriété est vérifiée d'après nos tests de départ.
- Si n+1 est supérieur ou égal à 48, alors on peut décomposer n+1 en une somme de deux entiers p (n>=p>=24) et q (n>=q>=24), et ces deux entiers p et q s'écrivent sous la forme 5k+7i d'après l'hypothèse de récurrence. Donc n+1, étant somme de deux entiers ayant cette forme, a lui aussi cette forme.