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

Cours d’Informatique —Licence Informatique—

Exercice 1. On considère l’opérateur Δ défini par : (Δf)(x) = f(x + 1) − f(x). 1. Calculer Δf_{k} pour f_{k}(x) = \binom{x}{k};

2. Calculer Δ^{n}f pour n = 2, 3, 4 ;

3. Généraliser et démontrer.

Exercice 2.

1. Trouver les coefficients a et b tels que :

\frac{1}{x(x + 1)} = \frac{a}{x} + \frac{b}{x + 1} .

2. En déduire la somme ∑_{i=1}^{m} \frac{1}{i(i + 1)} ;

3. Trouver les coefficients a et b tels que :

\frac{1}{(x + k)(x + n)} = \frac{a}{x + k} + \frac{b}{x + n} .

4. Trouver les coefficients a, b et c tels que :

\frac{1}{x(x + 1)(x + 2)} = \frac{a}{x} + \frac{b}{x + 1} + \frac{c}{x + 2} .

5. En déduire la somme ∑_{i=1}^{m} \frac{1}{i(i + 1)(i + 2)} ;

6. Démontrer par récurrence que

\frac{1}{x(x + 1) … (x + n)} = \frac{1}{n!} ∑_{k=0}^{n} \frac{(−1)^{k}\binom{n}{k}}{x + k} .

Exercice 3. Soit E un ensemble à n éléments. On note Λ = P(E), l’ensemble des parties de E. Calculer les sommes :

1. ∑_{X∈ Λ} 1 ;

2. ∑_{X∈ Λ} |X|;

3. ∑_{X,Y ∈ Λ} 1 ;

4. ∑_{X,Y ∈ Λ} |X ∩ Y |;

5. ∑_{X,Y ∈ Λ} |X ∪ Y |.