Partition d'un entier

Pour tout n de lN, c(n) définie le nombre de partition de l'entier n.
Exemple :
3 =3 (un terme)
3 = 2+1 = 1+2 (deux termes)
3 = 1+1+1 (trois termes)

c(3) = 4

J'ai induit que c(n) = 2^(n-1)

Comment puis-je le prouver ?

Il faut d'abord montrer que c(n) = (Somme (k=1 -> n-1),c(k)) + 1 (Somme pour k allant de 1 à n-1 des c(k), le tout +1)
On note d(p,n) une décomposition de n dont la somme des termes excepté le dernier est n-p.
On a pour tout p et pour tout n d(p,n)+p=n dont l'ensemble forme la totalité des décompositions de n : on a toutes les partitions dont la somme des termes excepté le dernier est n-p, p variant de 0 à n.
Le nombre de d(p,n) est en fait c(n-p) : c'est le nombre de partitions de n-p
Pour p=n, on a 1 décomposition.
Donc c(n) = (Somme (p=0 -> n-1),c(n-p)) + 1 ce qui correspond à la formule du début avec p=n-k

Avec ce résultat on peut démontrer que c(n) = 2^(n-1) par récurrence forte sur n
c(1)=1
2^(1-1)=1
La propriété est vraie pour n=1
Soit n quelconque fixé
On suppose que c(m) = 2^(m-1) pour tout m c {1..n}
c(n+1)=(Somme (k=1 -> n),c(k)) + 1
c(n+1)=(Somme (k=1 -> n),2^(k-1)) + 1
On reconnait la somme des termes d'une suite géométrique de raison 2, de n termes
c(n+1)=1*(1-2^n)/(1-2)+1=2^n
Conclusion : par le principe de récurrence forte sur n, on a montré que le nombre de partitions de n est c(n)=2^(n-1)

Tu es un géni Sam, bien vu pour le fait que c(n) = (Somme (k=1 -> n-1),c(k)) + 1, je n'avais même pas remarqué puis dans l'hérédité remplacer le terme général de la somme par la somme des n termes d'une suite géométrique, bravo
Il faut croire que le Yétisport augmente la facilité de raisonnement.

Merci!
Sa me permet de vous donner quelques conseils pour rédiger une récurrence parceque peu de profs de lycée sont d'accord et qu'il existe plusieurs types de récurrence. Notamment, Soustelle rédige toutes ses récurrences comme des récurrences fortes ce qui est inutile voire faux et peut parfois perdre les éleves.


Récurrence simple
Soit P(n) une propriété mathématique qui dépend de n.
Si P(0) est vraie (resp P(k))
pour tout n de |N (resp>=k) on a (P(n) => P(n+1))
Alors P(n) est vraie pour tout n de |N (resp >=k)

Rédaction
Par récurrence sur n, montrons que [P(n)] est vraie pour tout n de |N
[P(0)] donc vrai pour n=0
Soit n de |N quelconque fixé
On suppose que [P(n)] est vraie
[On montre que P(n+1) est vraie en mettant en évidence l'utilisation de l'hypothèse de récurrence]
Conclusion : [P(n)] pour tout n de |N]

note: la notation []signifie qu'il ne faut pas écrire "P(n)" mais son expression

Récurrence double, voire plus si affinité
Soit P(n) une propriété mathématique qui dépend de n.
Si P(0) et P(1) sont vraies
pour tout n de |N on a (P(n) et P(n+1) => P(n+2))
Alors P(n) est vraie pour tout n de |N

Rédaction
Par récurrence double sur n
puis idem avec 2 initialisations et 2 hypothèses de récurrence

Récurrence forte
Soit P(n) une propriété mathématique qui dépend de n.
Si P(0) vraie
pour tout n de |N on a (pour tout k de {0...n} P(k) vraie => P(n+1) vraie)
Alors P(n) est vraie pour tout n de |N

Rédaction
Par récurrence forte sur n, montrons que [P(n)] est vraie pour tout n de |N
[P(0)] donc vrai pour n=0
Soit n de |N quelconque fixé
On suppose que [P(k)] est vraie pour tout k de {0...n}
(ou encore P(n) vraie jusqu'à l'ordre n)
[On montre que P(n+1) est vraie en mettant en évidence l'utilisation de l'hypothèse de récurrence]
Conclusion : [P(n)] pour tout n de |N]

Attention, à chaque type de problème correspond une récurrence.
Dans le problème ci dessus, on utilise la récurrence forte car on en a besoin pour le raisonnement.
De même pour la récurrence double : ne l'utilisez que si vous vous rendez compte que vous avez besoin aussi de la propriété à l'ordre précédent.

Je ne vois pas bien la différence entre la récurence forte et simple.
Dans la simple on démontre l'hérédité en supposant de P(k) est vrai et en montrant que c'est vraie aussi pour P(k+1) donc P(n) est vraie pour n de lN.
Dans la forte, si j'ai bien comprisn, on a k qui peut prendre toutes les valeurs {0...n} et ensuite on fait comme dans la récurence simple.
Quelle est la différence entre les deux ?
La méthode est pourtant identique dans les deux cas.

Pour la double, je n'ai vu d'exemple, je suppose que tu as vu ça en spé ou bien cette année.
Je suppose que c'est pour montrer quelque chose du genre P(n-1) et P(n), mais si on montre P(n) pout tout n de lN on a bien aussi P(n-1), non ?

sam a écrit:

Il faut d'abord montrer que c(n) = (Somme (k=1 -> n-1),c(k)) + 1 (Somme pour k allant de 1 à n-1 des c(k), le tout +1)
On note d(p,n) une décomposition de n dont la somme des termes excepté le dernier est n-p.
On a pour tout p et pour tout n d(p,n)+p=n dont l'ensemble forme la totalité des décompositions de n : on a toutes les partitions dont la somme des termes excepté le dernier est n-p, p variant de 0 à n.
Le nombre de d(p,n) est en fait c(n-p) : c'est le nombre de partitions de n-p
Pour p=n, on a 1 décomposition.
Donc c(n) = (Somme (p=0 -> n-1),c(n-p)) + 1 ce qui correspond à la formule du début avec p=n-k

Avec ce résultat on peut démontrer que c(n) = 2^(n-1) par récurrence forte sur n
c(1)=1
2^(1-1)=1
La propriété est vraie pour n=1
Soit n quelconque fixé
On suppose que c(m) = 2^(m-1) pour tout m c {1..n}
c(n+1)=(Somme (k=1 -> n),c(k)) + 1
c(n+1)=(Somme (k=1 -> n),2^(k-1)) + 1
On reconnait la somme des termes d'une suite géométrique de raison 2, de n termes
c(n+1)=1*(1-2^n)/(1-2)+1=2^n
Conclusion : par le principe de récurrence forte sur n, on a montré que le nombre de partitions de n est c(n)=2^(n-1)

Ce résultat ne peut être montré que par une récurrence forte puisque l'on a besoin, pour prouver que Pn+1 est vrai, d'avoir une propriété vraie à tous les rangs précédents.

Pour la récurrence double c'est idem, on est obligé parfois pour montrer Pn+1, d'avoir les deux propriétés précédentes vraies.
Exemple (exo de DS):
Soit F l'ensemble des applications (fonctions) f : |R -> |R continues sur |R vérifiant la condition :
pour tout x,y de |R f (x+y) + f (x-y) = 2 ( f (x) + f (y) ) (1)
Montrer que (a) f(0) = 0
(c) pour tout n de |N, pour tout t de |R, f (nt) = n^2 f (t)
(a) On applique (1) avec y = 0
f (x+0) + f (x-0) = 2 ( f (x) + f (0) )
2 f (x) = 2 f (x) + 2 f(0)
Donc f (0) = 0

(c) Montrons par récurrence double sur n que "pour tout n de |N, pour tout t de |R,
f (nt) = n^2 f (t)"
pour n=0, f (0t) = f (0) = 0
0^2 f(t) = 0
pour n=1, f (1t) = f (t)
1^2 f(t) = f (t)
Donc vrai pour n=0 et n=1

Soit n quelconque fixé
On suppose que f ((n-1)t) = (n-1)^2 f (t)
f (nt) = n^2 f (t)
f ((n+1)t) = f (nt+t) = 2 ( f (nt) +f (t) ) -f (nt - t) par la relation (1)
= 2 f (nt) +2 f (t) - f ((n-1)t)
= 2 n^2 f (t) + 2 f (t) - (n-1)^2 f (t) par HR
= 2 n^2 f (t) + 2 f (t) - (n^2 - 2n +1) f (t)
= (n^2 + 2n +1) f (t)
= (n+1)^2 f(t)
Conclusion : par le principe de récurrence double sur n, on a montré que
"pour tout n de |N, pour tout t de |R, f (nt) = n^2 f (t)"

Et si on essaye de faire ici une récurrence simple, on aboutit pas. En fait, on se rend compte en rédigeant la récurrence que l'on a besoin d'une double lorsque l'on voit apparaitre f ((n-1)t)

Pas le temps d'y regarder à fond mais j'ai compris sur le principe. (vive le bac blanc!)