Récurrences et fonctions génératrices

L’application résout les récurrences linéaires à coefficients constants de tout ordre par l’équation caractéristique – racines multiples et complexes comprises (la forme complexe de la solution et son passage à la forme réelle par la formule de Moivre) – et avec un second membre de la forme P(n)·qⁿ (aussi cos nφ, sin nφ, résonance et somme de seconds membres). Les conditions initiales déterminent les constantes ; pour vérifier, l’application calcule d’autres termes par la récurrence et les compare à la formule.

La puce « Méthode » propose aussi la fonction génératrice (A(x) = Σ aₙxⁿ, éléments simples, séries géométriques), les puissances d’une matrice (diagonalisation) ou, à l’ordre 1, la sommation. Une récurrence d’ordre 1 à coefficient variable (aₙ₊₁ = (n + 1)aₙ) se résout par un produit (factorielles), les récurrences non linéaires convertibles par la substitution bₙ = 1/aₙ ou bₙ = ln aₙ. Un système de deux récurrences se résout en éliminant une suite ou par la matrice, une récurrence « diviser pour régner » T(n) = aT(n/b) + f(n) par n = bᵏ – avec l’estimation du théorème maître.

Avec l’opération « Fonction génératrice », l’application trouve la fonction génératrice d’une suite donnée par une formule (n² + 2ⁿ) ou par ses premiers termes (1, 0, 1, 0, …), et inversement la formule de aₙ à partir d’une fonction A(x). Le nombre de solutions entières positives ou nulles de x₁ + x₂ + … = N (aussi avec des bornes ou des coefficients – payer avec des pièces) est un coefficient d’une fonction génératrice.

Le graphique montre les termes de la suite sous forme de points (les deux suites d’un système).

Comment le saisir

`a(n+2) = 5a(n+1) - 6a(n), a(0) = 1, a(1) = 4`	Avec des parenthèses, les conditions après une virgule.
`a_{n+2} = 5a_{n+1} - 6a_n`	Avec des indices (aussi depuis une photo). Sans conditions : la solution générale avec les constantes C₁, C₂.
`F_n = F_{n-1} + F_{n-2}, F_1 = F_2 = 1`	L’indice peut descendre (aₙ₋₁, aₙ₋₂) ; une même valeur peut être donnée à plusieurs termes.
`a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0`	Un système – les équations sur des lignes, les conditions sur la dernière.
`T(n) = 2T(n/2) + n, T(1) = 1`	Diviser pour régner – un terme en n/b.
`n^2 + 2^n`	La formule d’une suite avec l’opération « Fonction génératrice » (aussi aₙ = …).
`1, 0, 1, 0, ...`	Les premiers termes séparés par des virgules.
`1/(1 - x - x^2)`	Une fonction génératrice en x (aussi A(x) = …) – la formule de aₙ.
`nombre de solutions x_1 + x_2 + x_3 = 10, x_1 <= 3`	Le nombre de solutions entières positives ou nulles avec des bornes.

Exemples

Deux racines réelles distinctes, la vérification par d’autres termes.

Énoncé: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

La suite de Fibonacci – la formule de Binet.

Énoncé: F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$ $F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

Racines complexes 1 ± i – la forme complexe et la formule de Moivre.

Énoncé: a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

Le second membre n, une racine double 2.

Énoncé: a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

La même récurrence par la fonction génératrice.

Énoncé: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Fonction génératrice

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

La même récurrence par les puissances d’une matrice.

Énoncé: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Puissances d’une matrice

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

Une récurrence d’ordre 1 par sommation.

Énoncé: a_{n+1} = 2a_n + 1, a_0 = 0 Sommation

$a_{n+1} = 2a_n + 1, a_0 = 0$

$a_{n+1} = 2a_n + 1, a_0 = 0$ $a_{n+1} = 2a_n + 1, a_0 = 0$

Un coefficient variable – le produit donne une factorielle.

Énoncé: a_{n+1} = (n+1)a_n, a_0 = 1

$a_{n+1} = (n+1)a_n, a_0 = 1$

$a_{n+1} = (n+1)a_n, a_0 = 1$ $a_{n+1} = (n+1)a_n, a_0 = 1$

Une récurrence non linéaire – la substitution bₙ = 1/aₙ.

Énoncé: a_{n+1} = a_n/(1 + a_n), a_0 = 1

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$

Un système de deux récurrences en éliminant la suite bₙ.

Énoncé:

a_{n+1} = a_n + 2b_n
b_{n+1} = 3a_n + b_n
a_0 = 1, b_0 = 0

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

Diviser pour régner (tri fusion) – n = 2ᵏ et le théorème maître.

Énoncé: T(n) = 2T(n/2) + n, T(1) = 1

La fonction génératrice de la suite n² + 2ⁿ.

Énoncé: n^2 + 2^n Fonction génératrice

La formule de aₙ à partir d’une fonction génératrice – éléments simples avec des racines irrationnelles.

Énoncé: 1/(1 - x - x^2) Fonction génératrice

Le nombre de solutions de x₁ + x₂ + x₃ = 10 avec x₁ ≤ 3.

Énoncé: nombre de solutions x_1 + x_2 + x_3 = 10, x_1 <= 3

počet řešení x_1 + x_2 + x_3 = 10, x_1 <= 3

Limitations connues

Pas encore : les récurrences linéaires d’ordre supérieur à coefficients variables, les systèmes de trois récurrences ou plus, « diviser pour régner » avec plusieurs termes (T(n/2) et T(n/3)) et les récurrences non linéaires que ces substitutions ne rendent pas linéaires.