# RSolve with conditional equation

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?

• f[n] == 1+2 f[n] is not a proper recurrence relation. For instance, using Solve would give f[n]->-1. Perhaps you mean f[n+1] == 1+2 f[n]. Please clarify. Also, conditions typically can be expressed using /;. – bbgodfrey Feb 25 '15 at 14:11
• Ups, sorry, it was supposed to be f[n] == 1 + 2 f[n/2]. – heykell Feb 25 '15 at 14:15
• What do you mean by /; ? Can you give an example? Note that I don't want a pure function, I need an equation to use in RSolve. – heykell Feb 25 '15 at 14:17
• Condition is described here – bbgodfrey Feb 25 '15 at 14:28

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

• Interesting approach. Could you display the sequence of code actually executed by Mathematica to obtain the final answer? Thanks. – bbgodfrey Feb 25 '15 at 16:47
• @bbgodfrey I have provided all code which was executed (just the line with RSolve). Please read the remark in my solution. – Dr. Wolfgang Hintze Feb 25 '15 at 18:26
• @bbgodfrey I have revised my original text to provide more comprehensive information. The result is the same: no way for RSolve to attack If, Floor, etc. – Dr. Wolfgang Hintze Feb 26 '15 at 10:22

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.)

RSolve[{f[2 n] == (1 + 2*f[n]), f[1] == 1}, f[n], 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.
• Rather than using "inspection" use FindSequenceFunction, i.e., FindSequenceFunction[seq][n] – Bob Hanlon Feb 25 '15 at 15:16
• @Dr.WolfgangHintze RSolve "Details and Options" documentation lists several allowed forms for recurrence, and Condition is not among them. RSolve objected with RSolve::deqn: Equation or list of equations expected ... when I tried to include one, perhaps because the expression is an equation only for n even. But, using an If causes RSolve to return unevaluated. On the other hand, I believe that my approach with @BobHanlon suggestion can handle many problems, not just the simple (but interesting) one here. – bbgodfrey Feb 25 '15 at 15:40