# 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}
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 /;. Feb 25, 2015 at 14:11
• Ups, sorry, it was supposed to be f[n] == 1 + 2 f[n/2]. Feb 25, 2015 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. Feb 25, 2015 at 14:17
• Condition is described here Feb 25, 2015 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, independently of the starting value of n.

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

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, can be put in RSolve to give

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

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


The constant C is determined at n=1 from

f = C + (1+f)


which gives C -> -1

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


For f = 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 = 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. Feb 25, 2015 at 16:47
• @bbgodfrey I have provided all code which was executed (just the line with RSolve). Please read the remark in my solution. Feb 25, 2015 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. Feb 26, 2015 at 10:22

This problem can be solved as follows.

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

In answer to a Comment,

RSolve[{f[2 n] == (1 + 2*f[n]), f == 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.

• Thanks for your answer, but I would like to get a closed form expression using RSolve, I don't want to inspect the result to conclude that f[n] = 2*n-1. Do you know how to plug in a pure function to RSolve? Feb 25, 2015 at 15:14
• Rather than using "inspection" use FindSequenceFunction, i.e., FindSequenceFunction[seq][n] Feb 25, 2015 at 15:16
• @heykell: I agree, it is not the (trivial) solution which is important, but you want to get it using RSolve. You might wish to consult the help "more Information" section to see that RSolve does not solve conditional equations. Feb 25, 2015 at 15:21
• @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. Feb 25, 2015 at 15:40
• @bbgodfrey: I agree. You might wish to have a look at my RSolve solution with "preprocessig" just uploaded. Feb 25, 2015 at 15:48