Three basis sequences

The right reflex: linearity

We now study the family of recurrences

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

where γ, β₀ and β₁ are integers.

If f answers to the parameters (γ, β₀, β₁) and f̃ to (γ̃, β̃₀, β̃₁), then f + f̃ answers to the sum of the parameters, and λ·f to λ times the parameters. The set of solutions therefore behaves like a three-dimensional vector space, parametrised by (γ, β₀, β₁).

So it is enough to solve three well-chosen special cases, then recombine.

The three basis sequences

Write n = 2^α + ℓ, with ℓ between 0 and 2^α − 1: α is the largest exponent in the binary expansion of n, and ℓ the number read off the last α digits.

parameters (γ, β₀, β₁)	sequence	expression
(1, 0, 0)	A(n)	2^α
(0, 1, 0)	B(n)	2^α − 1 − ℓ
(0, 0, 1)	C(n)	ℓ

In binary the reading is transparent: A(n) keeps only the leading 1, C(n) counts the positions where the digit of n is 1 (leading digit aside), and B(n) those where it is 0. Their sum A + B + C is in fact 2^{α+1} − 1, that is α + 1 digits equal to 1.

The general solution

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

This formula satisfies the three original relations, by linearity; and since the recurrence determines f uniquely from f(1), it is the solution.