Trois suites de base

Le bon réflexe : la linéarité

On étudie maintenant la famille de récurrences

   f(1)      = γ
   f(2n)     = 2·f(n) + β₀      pour n ≥ 1
   f(2n + 1) = 2·f(n) + β₁      pour n ≥ 1

où γ, β₀ et β₁ sont des entiers relatifs.

Si f répond aux paramètres (γ, β₀, β₁) et f̃ aux paramètres (γ̃, β̃₀, β̃₁), alors f + f̃ répond à la somme des paramètres, et λ·f à λ fois les paramètres. L'ensemble des solutions se comporte donc comme un espace vectoriel de dimension 3, paramétré par (γ, β₀, β₁).

Il suffit donc de résoudre trois cas particuliers bien choisis, puis de recombiner.

Les trois suites de base

On note n = 2^α + ℓ, avec ℓ compris entre 0 et 2^α − 1 : α est l'exposant maximal dans l'écriture binaire de n, et ℓ le nombre lu sur les α derniers chiffres.

paramètres (γ, β₀, β₁)	suite	expression
(1, 0, 0)	A(n)	2^α
(0, 1, 0)	B(n)	2^α − 1 − ℓ
(0, 0, 1)	C(n)	ℓ

En binaire, la lecture est limpide : A(n) ne garde que le 1 de tête, C(n) compte les positions où le chiffre de n vaut 1 (hors tête), et B(n) celles où il vaut 0. Leur somme A + B + C vaut d'ailleurs 2^{α+1} − 1, soit α + 1 chiffres 1.

La solution générale

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

Cette formule vérifie les trois relations de départ, par linéarité ; et comme la récurrence détermine f de manière unique à partir de f(1), c'est la solution.