TD 02 - Comptage, suites et séries

1 Les suites

1.1 Exercice 1

Dans chacun des cas, identifier s’il s’agit d’une suite arithmétique, géométrique ou arithmético-géométrique, puis donner leur terme général.

  1. \(u_0 =3, u_{n+1} = u_n + 2\)
  2. \(u_0 =5, u_{n+1} = u_n \times 8\)
  3. \(u_0 = 1, u_{n+1} = 2u_n -1\)
  4. 🏠 À faire à la maison : \(u_0 = 1, u_{n+1} = 2u_n +1\)

2 Récurrence

2.1 Exercice 2

Prouver par récurrence les résultats suivants :

  1. \(\forall n \geq 1,\displaystyle\sum_{i=1}^n(2i+1) = n^2 + 2n\)
  2. \(\forall n \geq 1,\displaystyle\sum_{i=1}^n i^2 = \dfrac{n(n+1)(2n+1)}{6}\)
  3. \(\forall n \geq 2,6^{n}\) est un multiple de 9
  4. 🏠 À faire à la maison : \(\forall n \geq 0,n^3-n\) est un multiple de 3
  5. \(\forall n \geq 4, n! > 2^n\)
  6. 🏠 À faire à la maison : \(\forall n \geq 10,n^3 \leq 2^n\)

2.2 Exercice 3 🏠

Prouver par récurrence les résultats suivants :

  1. \(\forall n \geq 1,\displaystyle\sum_{i=1}^n i^3 = \dfrac{n^2(n+1)^2}{4}\)
  2. \(\forall n \geq 1,\displaystyle\sum_{i=1}^n i(i+1) = \dfrac{n(n+1)(n+2)}{3}\)
  3. \(\forall n \geq 1,\displaystyle\sum_{i=1}^n i(i+1)(i+2) = \dfrac{n(n+1)(n+2)(n+3)}{4}\)
  4. \(\forall n \geq 1,\displaystyle\sum_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1}\)
  5. \(\forall n \geq 1,\displaystyle\sum_{i=1}^n (-1)^{i-1}i^2 = \dfrac{(-1)^{n-1}n(n+1)}{2}\)
  6. \(\forall n \geq 1,\displaystyle\sum_{i=1}^n ii! = (n+1)!-1\)
  7. \(\forall n \geq 0,2^{4n+2}+3^{n+2}\) est un multiple de 13
  8. \(\forall n \geq 1, n\) impair, \(n^2-1\) est un multiple de 8
  9. \(\forall n \geq 1, 4^n+15n-1\) est un multiple de 9

3 Sommes partielles

3.1 Exercice 4

  1. Calculer \(\displaystyle\sum_{k=3}^{8} 1\)
  2. Calculer \(\displaystyle\sum_{k=2}^{6} k\)
  3. Calculer \(\displaystyle\sum_{k=4}^{10} (2k+1)\)
  4. 🏠 À faire à la maison : Calculer \(\displaystyle\sum_{k=5}^{12} k^2\) (indication : utiliser le résultat de l’exercice 2.2)
  5. 🏠 À faire à la maison : Soit la suite arithmétique \((u_n)\) de premier terme \(u_0 = 5\) et de raison \(r = 3\). Calculer la somme \(S = u_0 + u_1 + \cdots + u_{15}\)
  6. 🏠 À faire à la maison : Calculer la somme \(S = 11 + 15 + 19 + \cdots + 59\)
  7. 🏠 À faire à la maison : Soit la suite géométrique \((v_n)\) de premier terme \(v_0 = 2\) et de raison \(q = 1.5\). Calculer la somme \(S = v_0 + v_1 + \cdots + v_{10}\)

3.2 Exercice 5 🏠

Donner le terme général des suites définies par récurrence suivantes.

  1. \(u_0 =0, u_{n+1} = u_n + n -1\)
  2. \(u_0 = 1, u_{n+1} = u_n + 2^n\)
AstuceIndication

Poser la suite \((W_n)\) définie par \(\begin{cases} W_0=0 \\ W_{n}=u_{n}-u_{n-1} & \text{pour } n\geq 1 \end{cases}\)

et étudier la somme partielle \(S_n=\displaystyle\sum_{i=0}^n W_i\) en l’écrivant de deux façons différentes.

4 Comptage d’opérations

4.1 Exercice 6

Dans chacun des cas, compter le nombre d’opérations effectuées en fonction de \(n\).

BOUCLE 1
DEBUT
  x ← 0
  i ← 1
  TQ i ≤ n FAIRE
    j ← 1
    TQ j ≤ i FAIRE
      x ← x+1
      j ← j+1
    FTQ
    i ← i+1
  FTQ
FIN
BOUCLE 2
DEBUT
  i ← 1
  TQ i ≤ n FAIRE
    j ← 2
    TQ j < √n FAIRE
      j ← j+1
    FTQ
    i ← i+1
  FTQ
FIN
BOUCLE 3
DEBUT
  j ← 1
  TQ j ≤ n FAIRE
    k ← 1
    TQ k ≤ 2^j FAIRE
      k ← k+1
    FTQ
    j ← j+1
  FTQ
FIN
BOUCLE 4
DEBUT
  i ← n
  TQ 0 < i FAIRE
    j ← 1
    TQ j < n FAIRE
      j ← j+1
    FTQ
    i ← ⌊i/10⌋
  FTQ
FIN
ImportantRappel : Formules utiles
  • Somme arithmétique : \(\displaystyle\sum_{i=1}^n i = \frac{n(n+1)}{2}\)
  • Somme de carrés : \(\displaystyle\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\)
  • Somme géométrique : \(\displaystyle\sum_{i=0}^n q^i = \frac{1-q^{n+1}}{1-q}\) (si \(q \neq 1\))
  • Somme exponentielle : \(\displaystyle\sum_{i=1}^n 2^i = 2^{n+1} - 2\)