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
f[n] == 1+2 f[n]
is not a proper recurrence relation. For instance, usingSolve
would givef[n]->-1
. Perhaps you meanf[n+1] == 1+2 f[n]
. Please clarify. Also, conditions typically can be expressed using/;
. $\endgroup$Condition
is described here $\endgroup$