Retourner le problème

Une autre entrée : partir de solutions connues

La première méthode devinait A, B et C puis vérifiait. La seconde fait l'inverse : elle admet d'abord l'existence d'une décomposition

   f(n) = γ·A(n) + β₀·B(n) + β₁·C(n)

avec A, B, C indépendants des paramètres, puis détermine ces trois suites en injectant des fonctions f particulières dont on connaît déjà l'expression.

Deux fonctions gratuites

La fonction constante f₁(n) = 1 vérifie la récurrence : f₁(1) = 1 donne γ = 1, puis 1 = 2·1 + β₀ donne β₀ = −1, et 1 = 2·1 + β₁ donne β₁ = −1. Paramètres : (1, −1, −1).

La fonction identité f₂(n) = n la vérifie aussi : f₂(1) = 1 donne γ = 1, puis 2n = 2n + β₀ donne β₀ = 0, et 2n + 1 = 2n + β₁ donne β₁ = 1. Paramètres : (1, 0, 1).

Le système

En écrivant la décomposition pour ces deux fonctions, et pour J (paramètres (1, −1, 1)), on obtient trois équations à trois inconnues :

   A − B − C = 1          (venant de f₁ = 1)
   A     + C = n          (venant de f₂ = n)
   A − B + C = J(n)       (venant de J)

Trois équations, trois inconnues : le système se résout sans effort et redonne A(n) = 2^α, B(n) = 2^α − 1 − ℓ, C(n) = ℓ.

La morale

Deviner puis vérifier, ou poser un système et résoudre : les deux chemins mènent au même endroit. Le second est plus court à rédiger, mais il exige d'admettre l'existence de la décomposition — ce qui se démontre par récurrence forte.