Cours du 7 septembre 2016 : suites et récurrence

7 septembre 2016 : suites et récurrence [répertoire]

Faire des fiches !

rappel sur les puissances :

voir : exponentielles

a^p × a^q = a^p+q

a^p	×	a^q
a × a × . . . × a	×	a × a × . . . × a
← p termes →		← q termes →
← . . . . . . (p + q) . . . . . . . termes →			= a^p+q

en particulier : a × aⁿ = a¹ × aⁿ = aⁿ⁺¹
et : aⁿ = aⁿ⁺⁰ = aⁿ × a⁰ ⇒ a⁰ = 1

a^p / a^q = a^p−q

	← . . . . . . . . . p termes . . . . . . . . . →
a^p =	a × a × . . . × a × a × a × . . . . . × a
a^q =	a × a × . . . × a
a^p / a^q =		a × a × . . . . . × a	= a^p−q
	← q termes →	← (p−q) termes →

1 = a⁰ = aⁿ⁻ⁿ = aⁿ × a⁻ⁿ = aⁿ / aⁿ
⇒ a⁻ⁿ = 1 / aⁿ
on se souvient des vitesses v exprimées en m/s ou en m.s⁻¹
ou des masse volumiques ρ en kg/m³ ou en kg.m⁻³

suites : u(n+1) = f(u(n)) et u(0) ou u(n) = F(n)

définition d'une suite
- définition par récurrence : u_départ = a et u_n+1 = f(u_n)
  u_n est ainsi défini ∀ x ≥ départ
- définition explicite : u_n = F(n)
- exemples :
  voir suite arithmétique : u_n+1 = u_n + r
  voir suite géométrique : u_n+1 = q u_n
  voir suite arithmético-géométrique : u_n+1 = q u_n + r

Somme de suite arithmétique ; calcul direct : on écrit la somme à l'envers et on additionne

S_n =

. . .

(n−1)

(suite de raison +1)

S_n =

(n−1)

(n−2)

. . .

(suite de raison −1)

2 S_n =

(n+1)

. . .

(n+1)

= n × (n+1)

d'où : S_n = n × (n+1) / 2

Somme de suite arithmétique ; cas général : raison r et terme initial u_k : S_n = u_k + u_k+1 + . . . + u_n
S_n = nombre de termes × moyenne = (n − k + 1) × (u_k + u_n) / 2
nombre de termes = indice du dernier terme − indice du permier terme + 1 = n − k + 1
(pour trouver le nombre de termes, on retire les (k−1) termes absents des n termes)
remarque : si l'on part de u₀ : k = 0 : on aura (n+1) termes

u₁	u₂	. . .	u_k−1	u_k	u_k+1	. . .	u_n
n termes
(k−1) termes				n − (k−1) termes = n − k + 1 termes

moyenne = (premier terme + dernier terme) /2 = (u_k + u_n) / 2

Somme de suite géométrique ; calcul direct : on écrit la somme multipliée par q et on soustrait
(attention : S₁ = 1 + q¹ = 1 + q et S₀ = q⁰ = 1)

S_n =

q²

. . .

qⁿ⁻¹

qⁿ

(suite de terme initial q⁰)

q S_n =

q²

q³

. . .

qⁿ

qⁿ⁺¹

(suite de terme initial q¹)

(1 − q) S_n =

−

qⁿ⁺¹

= 1 − qⁿ⁺¹

(tous les autres termes disparaissent)

d'où : S_n = (1 − qⁿ⁺¹) / (1 − q)

Somme de suite géométrique ; cas général : raison q et terme initial u_k : S_n = u_k + u_k+1 + . . . + u_n
u_n = u₀ qⁿ
u_k = u₀ q^k
en divisant : u_n / u_k = q^n−k soit : u_n = u_k q^n−k (on vérifie avec n=k : u_k = u_k q⁰ : ok)
S_n = u_k (1 + q + . . . + q^n−k) = u_k (1 − q^n−k+1) / (1 − q)
avec : u_k = premier terme
et : (n − k + 1) = nombre de termes
S_n = premier terme × (1 − raison^{nombre de termes}) / 1 − raison)

démonstration par récurrence d'une formule : u_n = F(n)
- voir : Rédaction d'un raisonnement par récurrence
  voir : raisonnement par récurrence TS (début de la page)
  - (définition) La propriété à démontrer est u_n = F(n) pour n ≥ 0
  - (initialisation) Montrons que la propriété est vraie pour n = 0 :
    on a d'une part : u₀ = . . .
    on a d'autre part : F(0) = . . .
    on vérifie que u₀ = F(0)
  - (hérédité) Montrons que la propriété est héréditaire à partir du rang 0 :
    soit n ≥ 0 ; on suppose que u_n = F(n)
    on a d'une part : u_n+1 = f(u_n) = . . .
    on a d'autre part : F(n+1) = . . .
    on vérifie que u_n+1 = F(n+1) : la propriété est héréditaire
  - (conclusion) La propriété u_n = F(n) étant vraie au rang 0 et héréditaire, on en déduit par récurrence qu'elle est vraie ∀ n ≥ 0 :
    u_n = F(n) ∀ n ≥ 0
démonstration par récurrence de la formule : S_n = n × (n+1) / 2 avec S_n = 1 + 2 + 3 + . . . + (n−1) + n
on nous donne la formule, mais on ne sait pas si elle est vraie tant qu'on ne l'a pas démontrée.
- La propriété à démontrer est S_n = n × (n+1) / 2 pour n ≥ 1
- Montrons que la propriété est vraie pour n = 1 :
  on a d'une part : S₁ = 1
  on a d'autre part : n × (n+1) / 2 = 1 × (1+1) / 2 = 1 × 2 / 2 = 1
  on vérifie que la propriété est vraie pour n = 1
- Montrons que la propriété est héréditaire à partir du rang 1 :
  soit n ≥ 1 ; on suppose que S_n = n × (n+1) / 2
  on a d'une part, par définition : S_n+1 = S_n + (n+1) = n × (n+1) / 2 + (n+1)
  on factorise (n+1) : S_n+1 = (n+1) (n/2 + 1) = (n+1) (n/2 + 2/2) = (n+1) (n+2) / 2
  on a d'autre part : (n+1) × ((n+1)+1) / 2 = (n+1) (n+2) / 2
  on vérifie que la propriété est héréditaire
- La propriété étant vraie au rang 1 et héréditaire, on en déduit par récurrence qu'elle est vraie ∀ n ≥ 1 :
  S_n = n × (n+1) / 2 ∀ n ≥ 1
démonstration par récurrence de la formule : S_n = (1 − qⁿ⁺¹) / (1 − q) avec S_n = 1 + q + q² + . . . + qⁿ⁻¹ + qⁿ
- La propriété à démontrer est S_n = (1 − qⁿ⁺¹) / (1 − q) pour n ≥ 0
- Montrons que la propriété est vraie pour n = 0 :
  on a d'une part : S₀ = 1
  on a d'autre part : (1 − qⁿ⁺¹) / (1 − q) = (1 − q⁰⁺¹) / (1 − q) = (1 − q) / (1 − q) = 1
  on vérifie que la propriété est vraie pour n = 0
- Montrons que la propriété est héréditaire à partir du rang 0 :
  soit n ≥ 0 ; on suppose que S_n = (1 − qⁿ⁺¹) / (1 − q)
  on a d'une part, par définition : S_n+1 = S_n + qⁿ⁺¹ = (1 − qⁿ⁺¹) / (1 − q) + qⁿ⁺¹
  S_n+1 = (1 − qⁿ⁺¹) / (1 − q) + qⁿ⁺¹ (1 − q) / (1 − q) = (1 − qⁿ⁺¹ + qⁿ⁺¹ − qⁿ⁺²) / (1 − q) = (1 − qⁿ⁺²) / (1 − q)
  on vérifie que la propriété est héréditaire
- La propriété étant vraie au rang 0 et héréditaire, on en déduit par récurrence qu'elle est vraie ∀ n ≥ 0 :
  S_n = (1 − qⁿ⁺¹) / (1 − q) ∀ n ≥ 0

retour aux menus : cours 2016 math TS math