Induction et récursion

Sommes

Dans les sommes suivantes, remplacer l’indice de sommation par \(k=i-1\).

  1. \(\sum_{i=1}^n i(i-1) = \frac{n(n^2 - 1)}{3}\).

  2. \(\sum_{i=1}^n\sum_{j=1}^n 1^i 1^j = n^2\).

Étendez les sommes de l’exercice précédent en remplaçant \(n\) par \(n+1\).

Preuves sur les entiers

Démontrer par induction les propriétés suivantes.

  1. Pour tout entier \(n\), \(\sum_{i=0}^n i = n(n + 1)/2\) ;
  2. Pour tout entier \(n\), \(7^n - 1\) est divisible par 6 ;
  3. Pour tout entier \(n\), \((n^3 - n)\) est divisible par 3 ;
  4. Pour tout entier \(n \ge 1\), \(1+3+5+\cdots+(2n-1) = n^2\) ;
  5. Pour tout entier \(n\), \(\sum_{i=0}^n i^2 = \frac{n(n+1)(2n+1)}{6}\) ;
  6. Pour tout entier \(n\), \(\sum_{i=0}^n i^3 = \frac{n^2(n+1)^2}{4}\).

Rappel : On note \(n!\) et on lit « \(n\) factoriel » le produit \(1\cdot 2\cdot 3\cdots n\).

Prouver les inégalités suivantes.

  1. \(2^n < n!\) pour tout \(n\ge 4\).
  2. \(n! < n^n\) pour tout \(n > 1\).
  3. L’inégalité de Bernoulli: \(1 + nh \le (1+h)^n\) pour tout entier \(n\) et tout nombre réel \(h\) tel que \(h > 0\).

Suites récurrentes

Rappel : On définit les nombres de Fibonacci par la récurrence suivante :

Prouver les identités suivantes:

  1. \(\sum_{i=0}^n F(i) = F(n+2) - 1\) pour tout \(n\ge0\).

  2. \(\sum_{i=0}^n F(i)^2 = F(n)F(n+1)\) pour tout \(n\ge0\).

  3. \(F(n)^2 = F(n-1)F(n+1) + (-1)^{n+1}\) pour tout \(n>0\).

  4. \(1 < \frac{F(n+1)}{F(n)} < 2\) pour tout \(n>2\).

Définitions récursives

Donner une définition récursive des fonctions \(f:\mathbb{N}\to\mathbb{N}\) suivantes :

  1. \(f(n) = 2^n\),
  2. \(f(n) = n!\).

Donner une définition récursive des propriétés suivantes :

  1. \(n\) est une puissance de \(10\).
  2. \(n\) est pair.
  3. L’écriture décimale de \(n\) ne contient que des \(1\).

Combinaisons

Rappel : on note \(\binom{n}{k}\), et on lit « \(k\) parmi \(n\) », le nombre de \(k\)-combinaisons de \(n\) éléments, c’est à dire le nombre de façons de choisir \(k\) éléments parmi \(n\). La récurrence fondamentale des combinaisons dit que

\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.\]

Prouver par induction (en utilisant l’égalité ci dessus) les égalités suivantes.

  1. \(\binom{n}{k} = \binom{n}{n-k}\).

  2. \(\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}\) pour tout \(0 < k \le n\).

Suggestion : ces inductions sont plus facilement réalisées sur la variable \(n\). Ceci correspond à prouver les égalités en remontant le triangle de Pascal ligne par ligne.

Rappel : Le triangle de Pascal est obtenu en arrangeant les coefficients binomiaux \(\binom{n}{k}\) par lignes de longueur croissante, avec la variable \(n\) qui parcourt les lignes et la variable \(k\) qui parcourt les colonnes.

\[\begin{array}{c@{}c@{}c@{}c@{}c} && \binom{0}{0}\\ & \binom{1}{0} && \binom{1}{1}\\ \binom{2}{0} && \binom{2}{1} && \binom{2}{2} \end{array}\]

En utilisant le signe de sommation \(\Sigma\), écrire les sommes suivantes :

  1. La somme des coefficients de la \(n\)-ème ligne.
  2. La somme des coefficients de la \(k\)-ème colonne.

On définit les sommes diagonales et anti-diagonales du triangle de Pascal comme suit :

  1. Dessiner le triangle de Pascal et, pour chaque entier \(n\), tracer des droites passant par les coefficients qui forment les sommes diagonales. Même chose pour les sommes anti-diagonales.

Rappel : On utilisera à nouveau la récurrence fondamentale des coefficients binomiaux, qui dit en pratique que chaque coefficient du triangle de Pascal est obtenu en faisant la somme des deux coefficients immédiatement au dessus :

\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.\]
  1. Prouver par induction que la somme des coefficients de la \(n\)-ième ligne vaut \(2^n\).

Rappel : Les nombres de Fibonacci \(F(n)\) sont définis par la récurrence \(F(0)=0\), \(F(1)=1\), \(F(n)=F(n-1)+F(n-2)\).

  1. Prouver par induction que la \(n\)-ème somme anti-diagonale vaut \(F(n+1)\).
Fork me on GitHub