Generalized Josephus problem

Question

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as

f(1) = a
f(2n) = 2f(n) + b, for n >= 1
f(2n+1) = 2f(n) + y, for n >= 1

The closed form is given as

f(n) = A(n)a + B(n)b + C(n)y
where,
A(n) = 2^m                       
B(n) = 2^m-1-l                   
C(n) = l                         

The book then says

Next, let’s use recurrence and solution in reverse, by starting with a 
simple function f(n) and seeing if there are any constants (a, b, y)
that will define it. Plugging in the constant function f(n) = 1 says that

1 = a
1 = 2.1+b;
1 = 2.1+y;

hence the values (a, b, y) = (1, -1, -1) satisfying these equations will 
yield

A(n) - B(n) - C(n) = f(n) = 1. Similarly, we can plug in f(n) = n:

1 = a;
2n = 2.n+ b;
2n+l = 2.n+y;

I am unable to understand how f(2n) has been replaced with 1 when we assumed f(n) = 1, and how it has been replaced with 2n and 2n+1 when we assumed f(n) = n. I know its something silly that I am missing but I am unable to see it. Can someone please explain.

Answer 1

You may have confused yourself by using different variable names $n$ and $m$ on different sides of the equations. The variable $n$ here doesn't have a specific value; it stands for the general argument of the function $n$. Thus, if the ansatz $f(n)=1$ is made, you can replace all values of $f$ by $1$, not just ones that literally use 'n' as an argument. Likewise, if $f(n)=n$ for general $n$, then $f(2n)=2n$ and $f(2n+1)=2n+1$.