7.1 Introduction

Le problème de grains de blé: Une légende raconte que le roi Shirham de l’Inde aurait demandé à son grand vizier Sissa Ben Dahir ce qu’il souhaitait obtenir comme récompense pour avoir inventé le jeu d’échec. Ce dernier fit la demande d’avoir un grain de blé pour la première case du jeu d’échec, deux grains pour la seconde case, 4\displaystyle 4 pour la troisième case, 8\displaystyle 8 pour la quatrième, et ainsi de suite en continuant de doubler pour chacune des cases de l’échiquier. Le roi ravi de la modestie de son vizier, accepta sans hésiter. Ce n’est qu’un peu plus tard, que les trésoriers du roi l’informa que la quantité de grain de blé requis était en fait de loin supérieur à la quantité produite annuellement par l’Inde. [Roberts]

Le problème des grains de blé est en fait un exemple de relation de récurrence. Si on dénote par an\displaystyle a_{n} le nombre de grains de blé se trouvant sur la n-ième case, on a donc la relation suivante:

{an=2⁢an−1,n≥2a1=1\displaystyle\left\{\begin{array}[]{l}a_{n}=2a_{n-1},\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ n\geq 2\\ a_{1}=1\end{array}\right.

Puis, si on dénote par sn\displaystyle s_{n} le nombre total de grain de blé pour couvrir les n\displaystyle n premières cases, on obtient la relation de récurrence suivante:

{sn=sn−1+an,n≥2s1=a1\displaystyle\left\{\begin{array}[]{l}s_{n}=s_{n-1}+a_{n},\leavevmode\nobreak% \ \leavevmode\nobreak\ \leavevmode\nobreak\ n\geq 2\\ s_{1}=a_{1}\end{array}\right.

Il est facile de voir que la solution de la première récurrence est an=2n−1\displaystyle a_{n}=2^{n-1}, ce qui nous permet ensuite de résoudre la seconde récurrence:

sn=∑n=1642n−1=∑n=0632n=264−12−1=264−1=18 446 744 073 709 551 615\displaystyle s_{n}=\sum_{n=1}^{64}2^{n-1}=\sum_{n=0}^{63}2^{n}=\frac{2^{64}-1% }{2-1}=2^{64}-1=18\leavevmode\nobreak\ 446\leavevmode\nobreak\ 744\leavevmode% \nobreak\ 073\leavevmode\nobreak\ 709\leavevmode\nobreak\ 551\leavevmode% \nobreak\ 615

Bien que l’exemple des grains de blé soit relativement simple à résoudre, il est important de noter que les récurrences apparaissent très souvent en combinatoire, et ce dans des contextes très varier. Il est donc important d’étudier les différentes techniques permettant de les résoudre. C’est ce que nous ferons dans les prochaines sections.