Travaux Dirigés de Structures Discrètes n^{o}1

Cours d’Informatique —Licence Informatique—

Exercice 1. Montrer par récurrence les formules suivantes :

1. 1 + 2 + ⋯ + n = \frac{n(n + 1)}{2} ;

2. 1 + 3 + ⋯ + 2n − 1 = n^{2} ;

3. 2 + 4 + ⋯ + 2n = n(n + 1) .

Trouver une interprétation combinatoire de la somme des entiers impairs.

Exercice 2. Retrouver les résultats de l’exercice précédent en sachant que les solutions sont des polynômes de degré 2.

Exercice 3. Montrer par récurrence les formules suivantes :

1. ∑_{i=1}^{n} i^{2} = \frac{n(n + 1)(2n + 1)}{6} ;

2. ∑_{i=1}^{n}(2i)^{2} = \frac{2n(n + 1)(2n + 1)}{3} ;

3. ∑_{i=1}^{n}(2i − 1)^{2} = \frac{n(2n − 1)(2n + 1)}{3} .

Montrer directement (i.e. sans utiliser la formule ci-dessus) que \frac{n(n+1)(2n+1)}{6} est un entier.

Exercice 4. Déduire de l’exercice précédent, la somme ∑_{i=0}^{n}(−1)^{i}i^{2}. Retrouver ce résultat

par récurrence.

Exercice 5. Retrouver les résultats de l’exercice précédent en sachant que les solutions sont des polynômes de degré 3.

Exercice 6. Montrer par récurrence les formules suivantes :

1. ∑_{i=1}^{n} i^{3} = \frac{n^{2}(n + 1)^{2}}{4} ;

2. ∑_{i=1}^{n}(2i)^{3} = 2n^{2}(n + 1)^{2} ;

3. ∑_{i=1}^{n}(2i − 1)^{3} = n^{2}(2n^{2} − 1) .

Retrouver la formule :

∑_{i=1}^{n} i^{3} = (∑_{i=1}^{n} i)^{2} .

Exercice 7. Calculer les sommes suivantes :

1. ∑_{k=0}^{n} 2^{k};

2. ∑_{k=0}^{n}(1 + x)^{k};

3. ∑_{k=0}^{n} k2^{k}.

Exercice 8. (Nombres de Fibonacci) On considère la suite de Fibonacci définie

par : F_{0} = F_{1} = 1 et la formule de récurrence F_{n+2} = F_{n+1} + F_{n}.

1. Montrer que deux nombres de Fibonacci consécutifs sont premiers entre eux ;

2. Soit Φ = \frac{1+\sqrt{5}}{2}. Calculer Φ^{2} et en déduire Φ^{n−1} ≤ F_{n} ≤ Φ^{n}. Calculer une approximation de F_{1000}. Combien de chiffres contient l’écriture en base 10 de F_{1000} ?

3. Démontrer la formule :

F_{m+n+2} = F_{m}F_{n} + F_{m+1}F_{n+1} .

4. Montrer que si l’on pose G_{n} = F_{n−1} pour n > 0, on a la formule G_{m} ∧ G_{n} = G_{m∧n} .