3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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 /;. $\endgroup$
    – bbgodfrey
    Feb 25, 2015 at 14:11
  • $\begingroup$ Ups, sorry, it was supposed to be f[n] == 1 + 2 f[n/2]. $\endgroup$
    – heykell
    Feb 25, 2015 at 14:15
  • $\begingroup$ 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. $\endgroup$
    – heykell
    Feb 25, 2015 at 14:17
  • $\begingroup$ Condition is described here $\endgroup$
    – bbgodfrey
    Feb 25, 2015 at 14:28

2 Answers 2

2
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ Interesting approach. Could you display the sequence of code actually executed by Mathematica to obtain the final answer? Thanks. $\endgroup$
    – bbgodfrey
    Feb 25, 2015 at 16:47
  • $\begingroup$ @bbgodfrey I have provided all code which was executed (just the line with RSolve). Please read the remark in my solution. $\endgroup$ Feb 25, 2015 at 18:26
  • $\begingroup$ @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. $\endgroup$ Feb 26, 2015 at 10:22
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – heykell
    Feb 25, 2015 at 15:14
  • 2
    $\begingroup$ Rather than using "inspection" use FindSequenceFunction, i.e., FindSequenceFunction[seq][n] $\endgroup$
    – Bob Hanlon
    Feb 25, 2015 at 15:16
  • $\begingroup$ @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. $\endgroup$ Feb 25, 2015 at 15:21
  • $\begingroup$ @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. $\endgroup$
    – bbgodfrey
    Feb 25, 2015 at 15:40
  • $\begingroup$ @bbgodfrey: I agree. You might wish to have a look at my RSolve solution with "preprocessig" just uploaded. $\endgroup$ Feb 25, 2015 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.