Multiple de 3

[youkef-sne]

Salut,
Un élève confirme avoir démontrer que 1 + 4^n est un multiple de 3.
1) Montrer que cette propriété est héréditaire
2)Cette propriété est elle vrai ? Conclure.

Le problème est que 1 + 4^n n'est pas un multiple de 3.
Je ne comprends pas: il faut prouver l'hérédité d'une propriété qui est fausse.

[Thomas Joseph]

D'où l'importance de vérifier la condition initiale avant de se lancer dans une récurrence.
Cet exercice est là pour te rappeler cette importance.

[titine]

Salut,
Un élève confirme avoir démontrer que 1 + 4^n est un multiple de 3.
1) Montrer que cette propriété est héréditaire
2)Cette propriété est elle vrai ? Conclure.

Le problème est que 1 + 4^n n'est pas un multiple de 3.
Je ne comprends pas: il faut prouver l'hérédité d'une propriété qui est fausse.

Oui.
Pour qu'une propriété soit vraie pour tout entier n il faut :
1) qu'elle soit héréditaire
2) qu'elle soit vraie pour n=0 (initialisation)
Si l'une des 2 conditions n'est pas remplie, la propriété n'est pas vraie.

Exemple :
U0 = 1 et U(n+1) = 3*U(n)
Propriété : "pour tout n, Un est pair"
Il est évident que cette propriété est fausse car U0=1, U1=3, ...
Pourtant elle est héréditaire, en effet :
Si on suppose que U(n) est pair, alors U(n+1) = 3*U(n) est pair aussi.

Si maintenant on considère la suite :
V0 = 4 et V(n+1) = 3*V(n)
La propriété : "pour tout n, Vin est pair" est vraie car elle est héréditaire et l'initialisation est vérifiée.

As tu compris mes explications ?

[youkef-sne]

Oui.
Pour qu'une propriété soit vraie pour tout entier n il faut :
1) qu'elle soit héréditaire
2) qu'elle soit vraie pour n=0 (initialisation)
Si l'une des 2 conditions n'est pas remplie, la propriété n'est pas vraie.

Exemple :
U0 = 1 et U(n+1) = 3*U(n)
Propriété : "pour tout n, Un est pair"
Il est évident que cette propriété est fausse car U0=1, U1=3, ...
Pourtant elle est héréditaire, en effet :
Si on suppose que U(n) est pair, alors U(n+1) = 3*U(n) est pair aussi.

Si maintenant on considère la suite :
V0 = 4 et V(n+1) = 3*V(n)
La propriété : "pour tout n, Vin est pair" est vraie car elle est héréditaire et l'initialisation est vérifiée.

As tu compris mes explications ?

Je n'est pas compris en quoi Un est héréditaire ?

[youkef-sne]

Je n'est pas compris en quoi Un est héréditaire ?

Ah si j'ai compris, je vais essayer de prouver l'hérédité de ma propriété:

Supposons que la propriété est vrai pour un certain rang p, on a alors:
1 + 4^p. Démontrons que cette propriété est vrai et donc qu'elle est vrai au rang p+1:
On a: On a : U(p) = 1 + 4^p donc U(p+1) = 1 + 4^(p+1) et donc elle est héréditaire.

[Thomas Joseph]

Tu n'as rien prouvé !
U(p+1)=1+4^(p+1)=1+4^p*4=1+4^p+3*4^p
1+4^p divisible par 3 par hypothèse de récurrence
3*4^p divisible par 3 car multiple de 3
D'où U(p+1) divisible par 3

[youkef-sne]

Tu n'as rien prouvé !
U(p+1)=1+4^(p+1)=1+4^p*4=1+4^p+3*4^p
1+4^p divisible par 3 par hypothèse de récurrence
3*4^p divisible par 3 car multiple de 3
D'où U(p+1) divisible par 3

D'accord merci de ton aide

[youkef-sne]

D'accord merci de ton aide

Mais comment on fait pour prouver l'hérédité d'une propriété par exemple que:
5^(n+2) >= 4^(n+2) + 3^(n+2) ?

[paquito]

Tu me semble peu à l'aise avec la récurrence.

Jouons au mauvais élève:

Hypothèse de récurrence: pour un entier n, 1+4^n=3k

cherchons à établir la propriété au rang n+1: 1+4^(n+1)=1

Jouons au mauvais élève et supposons:
hypothèse de récurrence: pour un entier n 1+4^n=3k
tentons de montrer la propriété au rang n+1: 1+4^(n+1)=1+(4^n)(4)
1+4^n(3+1)=1+4^n+3*4^n=3k+3*4^n=3(k+4^n) et donc la propriété est établie au rang n+1! d'où, d'après le principe.....etc
Petit problème, pour n=0 Un =2! Pour n=1, U1=5 et en fait, en terme de congruences, 4^n=1[3] et la propriété ne sera jamais vérifié. c'est pourquoi vous risquer d'être pénalisé si vous oublier d'amorcer la récurrence.

Dans le genre, j'ai l'exemple suivant: tout ensemble de n droites du plan est composé de droites ayant la même direction!
Démonstration:
Si n=1,l'amorce est évidente.
Supposons la propriété établie au rang n et soit En+1 un ensemble de n+1 droites; otons lui la droite D1; reste un ensemble de n droites donc qui ont toutes la même direction; remettons D1 et enlevons D2; toutes les droites ont la direction de D2 donc aussi D1; finalement, l a propriété est établi au rang
n+1! Cherchez l'erreur.

[youkef-sne]

Le raisonnement par récurrence j'peu me débrouiller mais dans l'exemple que j vous ai donné, je ne vois pas comment démontrer l'hérédité

[titine]

Tu veux donc démontrer que la propriété "1 + 4^n est un multiple de 3" et héréditaire.
Supposons qu'elle soit vrai au rang p. C'est à dire que 1 + 4^p est un multiple de 3. C'est à dire que 1 + 4^p = 3*k avec k entier.
On a alors 4^p = 3*k - 1
Donc 4^(p+1) = 4 * 4^p = 4 * (3*k - 1) = 12k - 4
Donc 1 + 4^(p+1) = 1 + 12k - 4 = 12k - 3 = 3 * (4k - 1)
Donc 1 + 4^(p+1) est un multiple de 3.
On a donc montrer que SI "1 + 4^p est un multiple de 3" alors "1 + 4^(p+1) est aussi un multiple de 3"
La propriété est héréditaire.

Paquito, où est l'erreur dans ton raisonnement ?

[Thomas Joseph]

"donc aussi D1" : non prouvé ... et faux pour n=2

[paquito]

L'erreur, c'est que pour n=2, si après avoir enlevé D1 on dit que les droites ont la direction de D2, c'est vrai que pour D2, ensuite on enlève D2 et on rajoute D1 qui est toute seule, donc D1 a la même direction que D1;
On peut faire ça aussi avec des crayons de couleurs; c'est toujours le passage de n=1 à n=2 qui cloche;
sinon on peut aussi "démontrer" que l'humanité est composée uniquement d'hommes!