Turning the problem around

Another way in: start from known solutions

The first method guessed A, B and C then checked them. The second does the opposite: it first grants the existence of a decomposition

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

with A, B, C independent of the parameters, then determines these three sequences by feeding in particular functions f whose expression is already known.

Two free functions

The constant function f₁(n) = 1 satisfies the recurrence: f₁(1) = 1 gives γ = 1, then 1 = 2·1 + β₀ gives β₀ = −1, and 1 = 2·1 + β₁ gives β₁ = −1. Parameters: (1, −1, −1).

The identity function f₂(n) = n satisfies it too: f₂(1) = 1 gives γ = 1, then 2n = 2n + β₀ gives β₀ = 0, and 2n + 1 = 2n + β₁ gives β₁ = 1. Parameters: (1, 0, 1).

The system

Writing the decomposition for these two functions, and for J (parameters (1, −1, 1)), yields three equations in three unknowns:

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

Three equations, three unknowns: the system solves effortlessly and returns A(n) = 2^α, B(n) = 2^α − 1 − ℓ, C(n) = ℓ.

The moral

Guess then verify, or set up a system and solve: both roads lead to the same place. The second is shorter to write up, but it requires granting the existence of the decomposition — which is proved by strong induction.