RSolve with conditional equation

Question

I have the following conditional equation:

$f(n) = 1+2 f(n/2)$ when n is even

$f(n) = 1+f((n-1)/2)+f((n+1)/2)$ when n is odd

I want to represent this as a conditional equation to be used in RSolve with $f(1)=1$.

The following doesn't work.

eqn = { f[2 n]== 1 + 2 * f[ n], f[2 n+1]== 1 + f[n+1] + f[ n] , f[1]==1}
RSolve[ eqn,f[n],n]

I also tried If[cond,e1,e2], but no luck. How can I express a conditional recurrence relation in Mathematica?

A related question:

One can also express the above function as f(n) = 1 + f(Ceiling(n/2)) + f(Floor(n/2)) without any need for conditional. However, RSolve can't solve this as well. Any thoughts?

Answer 1

According to the documentation RSolve cannot solve equations containing conditional branching.

We can nevertheless do it with RSolve investing some "preprocessing".

Define the difference function

d[n_] = f[n]- f[n-1]

where f[n] is defined resursively by

f[n_] := 1 + 2 f[n/2]/; EvenQ[n]
f[n_] := 1 + (f[(n+1)/2] + f[(n-1)/2]) /; OddQ[n] 

Now insert the definition of f[n] to get the sequence of transformations (no code to be run but just a manner of writing)

For even n:

d[n] /; EvenQ[n];
f[n] /; EvenQ[n] - f[n - 1] /; OddQ[n - 1];
(1 + 2 f[n/2]) - (1 + f[((n - 1) + 1)/2] + f[((n - 1) - 1)/2]);
2 f[n/2] - f[n/2] - f[n/2 - 1], f[n/2] - f[n/2 - 1]; 
d[n/2];

For odd n:

d[n] /; OddQ[n];
f[n] /; OddQ[n] - f[n - 1] /; EvenQ[n - 1];
(1 + f[(n-1)/2] + f[(n+1)/2]) - (1 + 2 f[(n-1)/2]);
f[(n-1)/2] + f[(n+1)/2] - 2 f[(n-1)/2];
f[(n+1)/2] - f[(n-1)/2];
f[(n+1)/2] - f[(n+1)/2-1];
d[(n+1)/2];

That is

d[n] = d[(n+1)/2] (* n odd *)
d[n] = d[n/2] (* n even *) 

The downward sequence for d[n] quickly arrives at d[2], independently of the starting value of n.

But d[2] = f[2] - f[1] = 1 + 2f[1] - f[1] = 1 + f[1].

This finalizes the preprocessing and now we return to f using the inverse definition of d[n]

f[n] = d[n] + f[n-1]

which, inserting d[n] = d[2], can be put in RSolve to give

RSolve[f[n] == d[2] + f[n - 1], f[n], n]

(*
Out[26]= {{f[n] -> C[1] + n d[2]}}
*)

The constant C[1] is determined at n=1 from

f[1] = C[1] + (1+f[1]) 

which gives C[1] -> -1

f[n] -> n(1+f[1]) - 1

For f[1] = 1 we get indeed the odd numbers.

Remark 1

The trick has been, of course, that I have got rid of the condition by considering the "breakdown" of the d[n] sequence as obvious and not to be done formally in MMA.

If we attempt to do it strictly in MMA we should write

RSolve[d[n]==d[Floor[n/2]], d[n],n]

This is, however, returned unevaluated.

Remark 2

As mentioned already in one of my comments, assuming a linear function f[n] = a + b*n, both formulas (for even and odd n) are identical giving

f[n] = a + b*n = 1 + 2 f[n/2] = 1 + 2a + 2 b*n/2

from which a = -1. b is determined from the initial value at n = 1, f[1] = f1, giving b = 1 + f1, so that

f[n] = -1 + (1+f1)n

Answer 2

This problem can be solved as follows.

f[1] = 1;
f[n_] := If[EvenQ[n], 2 f[n/2] + 1, f[(n + 1)/2] + f[(n - 1)/2] + 1]    
FindSequenceFunction[Table[f[n], {n, 20}], n]
(* -1 + 2 n *)

(My thanks to Bob Hanlon for recommending the use of FindSequenceFunction.)

Addendum

In answer to a Comment,

RSolve[{f[2 n] == (1 + 2*f[n]), f[1] == 1}, f[n], n]
(* {{f[n] -> -1 + 2 n}} *)

gives the same answer. However, I do not find the result satisfying, because RSolve has sufficient information only to provide an answer for n a power of 2. How it concludes that the result is valid for other values of n is unclear to me.