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

— 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 Donner les complexités en nombre d’opérations des bouts de code suivants :

  1. for(i=1;i<=n;i++)
       for(j=1;j<=i;j++)
         operation(i,j);
  2. for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
         operation(i,j);

Comparer ces deux résultats.

▶ Exercice 3 Retrouver les résultats de l’exercice 1 en sachant que les solutions sont des polynômes de degré 2.

▶ Exercice 4 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 5 Donner les complexités en nombre d’opérations du bout de code suivant :

for(i=1;i<=n;i++)
  for(j=1;j<=i;j++)
    for(k=1;k<=j;k++)
      operation(i,j,k);

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

▶ Exercice 7 Retrouver les résultats de l’exercice 4 en sachant que les solutions sont des polynômes de degré 3.

▶ Exercice 8 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 9 Calculer les sommes suivantes :

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

(a) en observant que c’est une somme géometrique;

(b) en écrivant ce nombre en base 2;

2. ∑_{k=0}^{n}(1 + x)^{k} en s’inspirant de la question précédente;

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

(a) en utilisant le résultat de la question précédente;

(b) par récurrence;

(c) en écrivant de deux façons différentes S_{n+1} en fonction de S_{n}.