Une conjecture

Bonjour,

Amateur de jeux mathématiques et logiques, je tente parfois de résoudre
les problèmes posés lors du championnat international des jeux
mathématiques et logiques. Là, je suis en train de réfléchir à la
question numéro 17 de la finale québécoise 2004/2005 :
http://aqjm.fsg.ulaval.ca/exercezvous/annees_anterieures/20042005/index.html
http://aqjm.fsg.ulaval.ca/fileadmin/AQJM/Archives/Classee_par_annee/2004-2005/Finale/04-05_Questionnaire_Finale.pdf

Pour ceux qui ne voudraient pas télécharger le PDF, voici une copie de
l'énoncé :
------------------------------------------------------------------------
17 EN L'HONNEUR DE L'ANNÉE
On écrit la liste des 2005 premiers nombres entiers : 1, 2, 3, ...
2005. On raie les deux premiers et on écrit leur somme 3 à la fin de
la liste. On continue en barrant les deux prochains nombres non rayés
et on reporte leur somme 7 à la fin de la liste :
 1, 2, 3, 4, 5, ... 2005
 () () 3, 4, 5, ... 2005, 3
 () () () () 5, ... 2005, 3, 7
On continue ainsi jusqu'à ne plus avoir qu'un seul nombre.
Quelle est la somme de tous les nombres écrits depuis le début ?
------------------------------------------------------------------------

J'ai trouvé la solution, mais en conjecturant un certain résultat que je
n'ai pas su démontrer, et c'est pour cela que je fais appel à vous.

Tout d'abord, entendons-nous sur les notations. On commence par écrire
u(1), u(2), u(3), ..., u(n) avec u(k)=k pour tout k compris entre 1 et
n. Dans l'énoncé, n=2005. Ensuite on fait :
 u(n+1) = u(1)+u(2)
 u(n+2) = u(3)+u(4)
 ...
 u(n+k) = u(2k-1)+u(2k)
 ...
 u(2n-1) = u(2n-3)+u(2n-2)

On montre très facilement que le dernier terme est u(2n-1), et aussi
qu'il est égal à la somme u(1)+u(2)+...+u(n). Mais ce qui nous intéresse
c'est la somme u(1)+u(2)+...+u(2n-1).

Nouvelle notation : je définis S(k) = u(1)+u(2)+...+u(k). Ainsi,
u(2n-1)=S(n), et on cherche S(2n-1).


Ma conjecture est la suivante :
------------------------------------------------------------------------
Si on écrit n sous la forme n=2^p+q, avec 0 <= q < 2^p,
Alors S(2n-1) = (p+1)S(n) + S(2q)
------------------------------------------------------------------------

J'ai vérifié qu'elle était vraie pour tout n compris entre 2 et 9. Par
ailleurs, j'ai aussi vérifié que la valeur trouvée pour n = 2005 était
bien celle donnée dans les réponses, à savoir 24 046 868 :
http://aqjm.fsg.ulaval.ca/fileadmin/AQJM/Archives/Classee_par_annee/2004-2005/Finale/04-05_Reponses_Finale.pdf

En effet, sachant que 2q est strictement inférieur à n, et que S(k) vaut
k(k+1)/2 pour tout k compris entre 1 en n, on a :
 S(2n-1) = (p+1)S(n) + S(2q) = (p+1)n(n+1)/2 + q(2q+1)
Avec n = 2005, on a p=10 et q=981, d'où S(4009) = 24 046 868.

Est-ce que quelqu'un voudrait bien m'aider à démontrer cette conjecture
qui, de toute évidence, doit être vraie ?

À tout hasard, j'ai aussi essayé d'exprimer n en fonction de la
puissance de 2 suivante au lieu de la puissance de 2 précédente.
Sauf erreur (mais là j'ai vérifié moins soigneusement) cela
donnerait :
------------------------------------------------------------------------
Si on écrit n sous la forme n=2^p-r, avec 0 < r <= 2^(p-1),
Alors S(2n-1) = p.S(n) + S(n-r)
------------------------------------------------------------------------

Merci à ceux qui auront le courage de s'y pencher !

-- 
Olivier Miakinen