Concrete Maths, The Josephus Problem

[glacial karma]

I was working through this proof and trying to understand how to construct the general closed form solution for a general recurrence formula

The recurrence looks like:

f(1) = α
f(2n) = 2f(n) + β , for n >= 1
f(2n + 1) = 2f(n) + γ , for n >=1

If we visualise the recurrence we get the image attached

We can tell the closed form will be something like:

f(n) = A(n)α + B(n)β + C(n)γ

Where,
A(n) = 2^m ;
B(n) = 2^(m −1) − l
C(n) = l

(where n = 2^m + l)

What I don't understand is the next part where the book begins to use induction to prove this, the book reads:

Let's illustrate this by considering the special case α = 1, β = γ = 0, when f(n) is supposed to be equal to A(n):

A(1) = 1;
A(2n) = 2A(n), for n >= 1
A(2n+1) = 2A(n), for n >=1

Sure enough, it's true (by induction on m) that A(2m + l) = 2m

Why are we able to just choose arbitrary values for α = 1, β = γ = 0 why does proving the special case prove things are generally true?

[analog yoke]

see

f(2n+1)-f(2n)

= gamma - beta

this is a constant

so it means the terms are in ap

so general term must be linear

assume a+bn

now f(1) = first term

and gamma - beta = common difference

[glacial karma]

I understood until you said assume a+bn, what does this assumption help with and where is the common difference used?

[analog yoke]

the term in ap is linear

so first term is a+b

and d = a2-a1 = (a+2b)-(a+b)=b

[glacial karma]

I get that the difference is b now, but what does this prove? why are we able to apply random values for beta, gamma and alpha

[analog yoke]

f(n)=an+b