petit problem de math

comment calculer en 5mn chrono sans calculatrice

la somme des 1000 premier entier

1000 +999+...+3+2+1

la légende veut que le mathématicien qui a trouvé le moyen avait une douzaine d'année

le plus souvent on ait sa en seconde

Lequel était Gauss bien entendu. Et son 'truc" est un grand classique. Il ne faut pas 5 mn, mais 5 secondes et de tête.

Pour élargir un peu plus on a pour tout n appartenant à N, n>0

1 + 2 + 3 + ... + n

= n (n + 1) / 2

1² + 2² + 3² + ... + n²

= n (n + 1)(2n + 1) / 6

1³ + 2³ + 3³ + ... + n³

= n² (n + 1)² / 4

Qui me fait les démonstrations par récurrence ?

Pour [le chiffre ou le nombre impair de l'énonce] il faut le multiplier par sa moitié en arrondissant au dessus la moitié pour qu'elle reste entiere et cela donne le résultat.

Pour "[le chiffre ou le nombre pair de l'énoncé]" il faut non seulement le multiplier par sa moitié mais "additionner à ce résultat la moitié du chiffre ou du nombre de l'ennoncé" et cela donne le résultat.

Donc multiplier le nombre 1000 par sa moitié donne un résultat auquel il faut lui "additionner la moitié de 1000"car 1000 est "un nombre pair" et cela donne le résultat .

On remarque le même énoncé pour;

"[2]" 2+1=3 [2] fois 1=2"+1"=3

[3] 3+2+1=6 [3] fois 2=6

"[4]" 4+3+2+1=10 [4] fois 2=8"+2"=10

[5] 5+4+3+2+1=15 [5] fois 3=15

"[6]" 6+5+4+3+2+1=21 [6] fois 3=18"+3"=21

[7] 7+6+5+4+3+2+1=28 [7] fois 4=28

"[8]" 8+7+6+5+4+3+2+1=36 [8] fois 4=32"+4"=36

...

donc pour"[1000]" ....c'est [1000] fois 500=500000"+500"=500500

Oh vi, la récurrence ! ^^

J'avais oublié ce mode de raisonnement, tiens. C'est mal, de laisser son cerveau rouiller... :blush:

* Je vois ce que ça donne pour n=1 : 1(1+1)/2 = 1*2/2 = 1

* soit n tel que la somme des entiers de 1 à n (ie 1 + ... + n ) = n(n+1)/2

Alors S = 1 + ... + n + (n + 1) = n(n+1)/2 + (n+1)

S =[ n(n+1) + 2(n+1)]/2

S = [(n+1) * (n+2) ]/ 2 (en factorisant par (n + 1) )

On a bien 1 + ... + (n+1) = (n + 1) ( (n + 1) + 1) / 2

C'est vrai pour n = 1. Donc cela va être vrai pour n = 2, et de proche en proche pour tout entier.

En revanche, j'ai la flemme de dérouler la démonstration pour les carrés et les cubes. La semaine prochaine, peut-être, si je m'ennuie..

comment calculer en 5mn chrono sans calculatrice

la somme des 1000 premier entier

1000+999+...+3+2+1

= (1000+1) + (999+2) + (998+3) + ... + (501+500)

= 500 é 1001

= 500500

Oh vi, la récurrence ! ^^

J'avais oublié ce mode de raisonnement, tiens. C'est mal, de laisser son cerveau rouiller... :blush:

* Je vois ce que ça donne pour n=1 : 1(1+1)/2 = 1*2/2 = 1

* soit n tel que la somme des entiers de 1 à n (ie 1 + ... + n ) = n(n+1)/2

Alors S = 1 + ... + n + (n + 1) = n(n+1)/2 + (n+1)

S =[ n(n+1) + 2(n+1)]/2

S = [(n+1) * (n+2) ]/ 2 (en factorisant par (n + 1) )

On a bien 1 + ... + (n+1) = (n + 1) ( (n + 1) + 1) / 2

C'est vrai pour n = 1. Donc cela va être vrai pour n = 2, et de proche en proche pour tout entier.

En revanche, j'ai la flemme de dérouler la démonstration pour les carrés et les cubes. La semaine prochaine, peut-être, si je m'ennuie..

Tu as perdu la belle rédaction mathématique. Eh oui, les maths ça se pratique, sinon ça s'oublie vite.

Le modèle que je te propose, et le plus utilisé, c'est :

a - Initialisation

Vérifions si cette propriété P(n) est vraie au rang initial. Pour n=0, on a [....]

Donc P(0) est vrai

b - Hérédité

Admettons cette propriété vraie à un certain rang n, et vérifions si elle est également vraie au rang n+1. Montrons P(n+1) vraie.

P(n) est donc l'hypothèse de récurrence

[...]

La récurrence peut aussi être présentée sous cette forme :

Hérédité :

Supposons la propriété vraie pour tout rang <n, et vérifions qu'elle est aussi vraie au rang n.

Dans ces conditions, on n'a plus besoin de l'initialisation, et en plus, pour montrer P(n), on a le droit d'utiliser le fait que la propriété est vraie pour tous les entiers strictement plus petits, et pas seueemnt le précédent.

Je ne comprends pas trop, Grenouille... une initialisation, il me semble qu'on en aura toujours besoin, non ?Au rang 1, ou à un autre... J'ai du mal à comprendre comment ta démonstration peut fonctionner (mais je suis peut-être un peu rouillée).

Gallium : désolée. :blush: Finalement, les mathématiques, c'est comme une langue vivante...

La récurrence peut aussi être présentée sous cette forme :

Hérédité :

Supposons la propriété vraie pour tout rang <n, et vérifions qu'elle est aussi vraie au rang n.

Dans ces conditions, on n'a plus besoin de l'initialisation, et en plus, pour montrer P(n), on a le droit d'utiliser le fait que la propriété est vraie pour tous les entiers strictement plus petits, et pas seueemnt le précédent.

Si je ne m'abuse il s'agit d'une récurence forte ?

Mais même dans ce cas, je suis assez étonné de la non existence de l'initialisation Oo

Oui, c'est la récurrence forte, et elle a aussi besoin d'une initialisation.

Dans ces conditions, on n'a plus besoin de l'initialisation

La récurrence forte doit, afin de démontrer P(n) vraie pour tout entier n ∈ N.

- Vérifier P(0) (La propriété est vraie à partir d'un certain rang n(0))

- Vérifier [∀k≤n P(k)] ⇒ P(n+1) (pour tout n ∈ N) (Pour tout rang n plus grand que n(0), les propriétés des rangs compris entre n(0) et n entraînent la propriété au rang n+1)

La récurrence forte doit, afin de démontrer P(n) vraie pour tout entier n ∈ N.

- Vérifier P(0) (La propriété est vraie à partir d'un certain rang n(0))

- Vérifier [∀k≤n P(k)] ⇒ P(n+1) (pour tout n ∈ N) (Pour tout rang n plus grand que n(0), les propriétés des rangs compris entre n(0) et n entraînent la propriété au rang n+1)

Ce que tu proposes ne fonctionne que pour les entiers, ma version, avait l'avantage de fonctionner pour tout ordre bien fondé.

Les principales différences de la version de la récurrence forte que j'ai donnée, c'est qu'au lieu de parler de "inférieur ou égal" et de "n+1" je parle de "inférieur strict" et de "n".

Je rappelle ma version :

Hérédité :

Supposons la propriété vraie pour tout rang <n, et vérifions qu'elle est aussi vraie au rang n.

En fait, si on montre cette hérédité, alors on peut en déduire P(0). Il n'est donc pas besoin de prouver l'initialisation.

Pour ceux qui ont la flemme de chercher, la preuve :

- Tu dis que tu démontres une hérédité mais tu ne la démontres pas.

- J'ai un doute en n=0. En gros c'est en n=0 : vide=> vrai. Le vide ça doit pas exister en logique.

En n=0, P(k) vrai est ni vrai ni faux, on ne peut rien dire en fait.

Moi ce qui me choque c'est que tu parles de fonctionner pour tout ordre bien fondé, mais que impose une restriction aux naturels dans ta démonstration :blush:

De plus, je n'ai jamais vu ton approche ailleurs, ça ne veut pas dire que c'est forcément faux, mais j'aurais du la voir dans ma formation si elle était connue et reconnue.

Il y a un truc que je ne comprends pas... on se passe de l'initialisation en supposant P(n) vraie pour tout n ? Mais on ne le sait pas, ce n'est qu'une hypothèse... l'initialisation -quel que soit le rang- a pour but de valider (ou d'invalider) l'hypothèse, non ?

J'ai du mal à comprendre le raisonnement de Grenouille...

- Tu dis que tu démontres une hérédité mais tu ne la démontres pas.

Je dis juste que, dans le cas de la récurrence généralisée, on peut se passer de l'initialisation.

Autrement dit, si la propriété d'hérédité est vraie (*), alors l'initialisation est aussi vraie.

(*) Sous la forme que j'ai donnée, sinon ça ne marche pas

- J'ai un doute en n=0. En gros c'est en n=0 : vide=> vrai. Le vide ça doit pas exister en logique.

En n=0, P(k) vrai est ni vrai ni faux, on ne peut rien dire en fait.

Le "ni vrai ni faux" n'existe pas en logique.

Par contre, toute propriété qui commence par "Pour tout x appartenant à l'ensemble vide ..." est vraie.

En effet, "Pour tout x appartenant à A P(x)" n'est qu'une abréviation de "Pour tout x, (x appartient à A) implique P(x)".

Lorsque A est vide, celà revient à dire que "Pour tout x, faux => P(x)". Or faux implique n'importe quoi, donc c'est toujours vrai.

Il y a un truc que je ne comprends pas... on se passe de l'initialisation en supposant P(n) vraie pour tout n ? Mais on ne le sait pas, ce n'est qu'une hypothèse... l'initialisation -quel que soit le rang- a pour but de valider (ou d'invalider) l'hypothèse, non ?

J'ai du mal à comprendre le raisonnement de Grenouille...

Je suppose l'hérédité.

Autrement dit, je suppose que la propriété suivante est vraie : ∀n( [∀k<n P(k)] ⇒ P(n) )

J'en déduis de cela que la propriété P(0) est vraie.

Autrement dit, de l'hérédité, je déduis l'initialisation.

C'est une méthode classique, extrêmement utile lorsqu'on veut raisonner sur un ordre bien fondé quelconque. Car, s'il s'agit d'un ordre bien fondé qui n'est pas total, alors l'initialisation est vraiment très pénible.

Avec cette méthode, on montre tout d'un coup.

Moi ce qui me choque c'est que tu parles de fonctionner pour tout ordre bien fondé, mais que impose une restriction aux naturels dans ta démonstration :blush:

Je n'ai effectivement fait la démonstration que dans le cas particlier de N.

Seulement, la propriété est encore vraie pour n'importe quel ordre bien fondé.

Démonstration :

On suppose qu'on a déjà montré cela : ∀n( [∀k<n P(k)] ⇒ P(n) )

On suppose que < est un ordre (éventuellement partiel) bien fondé.

On veut montrer que ∀n P(n).

On raisonne par l'absurde. Supposons qu'il existe x tel que non P(x).

On appelle u_0 ce x.

Comme ∀n( [∀k<n P(k)] ⇒ P(n) ) et que non P(u_0), cela signifie qu'il existe y < u_0 tel que non P(y).

On appelle u_1 ce y.

On construit ainsi par récurrence une suite infinie strictement décroissante.

Contradiction.

Je ne comprends toujours pas, Grenouille...

Je suppose l'hérédité.

Autrement dit, je suppose que la propriété suivante est vraie : ∀n( [∀k<n P(k)] ⇒ P(n) )

J'en déduis de cela que la propriété P(0) est vraie.

Autrement dit, de l'hérédité, je déduis l'initialisation

Je suppose que tous les êtres humains sont féminins, j'en déduis que le premier être humain était une femme ?

Seulement, la supposition de départ est fausse...

Bref, si l'hérédité que tu supposes est fondée sur qqch de vrai, ça fonctionne. Si elle ne l'est pas, ça ne fonctionne pas. Et l'initialisation permet de vérifier si ce que l'on avance est vrai ou pas...

On construit ainsi par récurrence une suite infinie strictement décroissante.

Contradiction.

Contradiction, et conclusion : P(n) est fausse ?

(Bref, je ne comprends toujours pas comment tu peux te passer d'initialisation... pour moi ça revient à vouloir trouver deux inconnues à l'aide d'une seule équation... l'analogie est sans doute bancale, mais c'est pour te donner une idée de ma perplexité. Même si les maths un peu poussées et moi, ça fait longtemps qu'on ne s'est pas croisées... :blush:)

Il faut commencer ta récurrence quelque part.

Mais il faut bien montrer P(0)=>P(1) donc vérifier que P(0) est vrai à l'écart.

Là j'ai un gros doute : "On suppose qu'on a déjà montré cela : ∀n( [∀k<n P(k)] ⇒ P(n) )".

J'aurai plutôt dit, pour n dans N (fixé) on suppose montré ( [∀k<n P(k)] ⇒ P n) )