Induction et récursion

Sommes

Dans les sommes suivantes, remplacer l’indice de sommation par .

  1. .

  2. .

Étendez les sommes de l’exercice précédent en remplaçant par .

Preuves sur les entiers

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

  1. Pour tout entier ,  ;
  2. Pour tout entier , est divisible par 6 ;
  3. Pour tout entier , est divisible par 3 ;
  4. Pour tout entier ,  ;
  5. Pour tout entier ,  ;
  6. Pour tout entier , .

Rappel : On note est on lit « factoriel » le produit .

Prouver les inégalités suivantes.

  1. pour tout .
  2. pour tout .
  3. L’inégalité de Bernoulli: pour tout entier et tout nombre réel tel que .

Suites récurrentes

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

Prouver les identités suivantes:

  1. pour tout .

  2. pour tout .

  3. pour tout .

  4. pour tout .

Définitions récursives

Donner une définition récursive des fonctions suivantes :

  1. ,
  2. .

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

  1. est une puissance de .
  2. est pair.
  3. L’écriture décimale de ne contient que des .

Combinaisons

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

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

  1. .

  2. pour tout .

Suggestion : ces inductions sont plus facilement réalisées sur la variable . 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 par lignes de longueur croissante, avec la variable qui parcourt les lignes et la variable qui parcourt les colonnes.

En utilisant le signe de sommation , écrire les sommes suivantes :

  1. La somme des coefficients de la -ème ligne.
  2. La somme des coefficients de la -è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 , 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 :

  1. Prouver par induction que la somme des coefficients de la -ième ligne vaut .

Rappel : Les nombres de Fibonacci sont définis par la récurrence , , .

  1. Prouver par induction que la -ème somme anti-diagonale vaut .
Fork me on GitHub