0

Consider this recursive function:

F(i)=F(F(i-1)-F(i-2))

It looks like a Fibonacci sequence. however, it has an extra F on the right side.

  1. is there any known reduction available for F?
  2. is there any known lower(upper) bound for F?
  3. what is the complexity of F?
Mauro ALLEGRANZA
  • 35,764
  • 3
  • 35
  • 79
morteza
  • 3
  • 1
  • Well, if you start with F(0)=1 F(1)=1, all elements of the sequence end up 1. So it is constant in that case. If you start with F(0)=0, F(1)=1, then it goes 0 1 1 0 and you can't calculate F(4) because it requires the definition of F(-1), which is not given. But this is the wrong place to post this. – causative Jul 27 '22 at 22:21
  • It is easy to find some particular solutions for example: f(i) = i/2 +3/4 (is the only affine solution). – Davius Jul 27 '22 at 22:30
  • What are the base cases for that? – haxor789 Jul 28 '22 at 07:37
  • suppose that we have F(0) and F(1), and F=eig(somthing ^ -1 + something which is solved though least square fitting) @haxor789 – morteza Jul 28 '22 at 08:58
  • I know how f is calculated using dynamic programming or recursion, i just want to now the bounds which are imposed due to this form: Fi=F(Fi-1,Fi-2) @causative – morteza Jul 28 '22 at 09:03
  • Also is it F(F(n-1) + F(n-2)) or F(F(n-1) -F(n-2))? See difference between title and question – haxor789 Jul 28 '22 at 09:34

2 Answers2

0

I mean that crucially depends on the base cases. Like if there are no base cases that's an infinite recursion because in order to now just about any n you'd also have to know F(n-1), F(n-2) and F(F(n-1)-F(n-2)). Which means you also need to know F(n-2), F(n-3) and F(F(n-2)-F(n-3)) and so on. So without any fixed value(s) of F(n) = X and likely also an F(n-1) =Y or F(n+1) = Y that is not possible to compute.

But even if we were to have arbitrary base cases like F(0) = F0 and F(1) = F1 then we'd still have the problem that F(2) for example would require the knowledge of what F(F1-F0) is and the answer to what F0-F1 is effects the complexity of that thing majorly.

if it's 0 for example than F(2) = F(0) = F0. Then F(3) = F(F(2)-F(1)) = F(F0 -F1) which is likely also 0 as A-B = 0 implies B-A = 0. So F(3) = F(0) = F0. So F(n) would be F0 for any n > 2. Which is constant. And F1 would be F0 in order for F1-F0 to be 0 and as F(1) = F(F0-F(n-1)) and F(1) = F(0) Therefore F(n-1) must also be F0 Meaning F(n) = F0 drop all the recursions it's one constant all the way through.

If it's 1 then F(2) = F(1) = F1. The F(3) would be F(F1-F1) which would be 0 so F(3) would be F(0). So F(4) = F(F3-F2) = F(F0-F1). Where is F1-F0 = 1 then F0 -F1 = -1. And you're back in an infinite recursion because in order to compute F(-1) you'd need to know F(-3) and for that you'd need F(-5) and so on.

If it's 2 you'd also get something interesting like: F(2) = F(F1 -F0) = F(2). So a tautology F(2) is F(2). Meaning all other n > 2 are not able to be computed because it's unknown what even F(2) is.

Not to mention that if I'd take F1-F0 to be arbitrary large that obviously takes a lot more computations then if it were small. So the complexity changes rapidly. Whether the number is increasing and I'd need more calculations to reach the base case or whether it is decreasing.

And if it reached negative numbers I'd again be screwed because it would turn again into an infinite recursion.

So no you kinda need a base case otherwise that could behave so differently for different cases that it's hard to impossible to make any generalizing statements.

haxor789
  • 4,203
  • 3
  • 25
0

You run into major trouble even calculating the various values.

One set of solutions is picking any constant c and letting F(i) = c. Then the recursion formula will tell you that for every i, F(i) = F(c-c) = F(0) = c, so there you have a solution.

For all other values you run into trouble sooner or later. The next simpler case is F0 = 0, F1 = 1. Write down the recursion formulas for F(-4) to F(10) and fill in what you know (that F0 = 0 and F1 = 1 initially) You run into trouble at F(5) = F(-1), so you let F(5) = F(-1) = c for unknown c, except you can prove that a few values for c are not possible. Soon after the possibilities will just explode. You may reduce this by adding restrictions, like F(i) >= 0 for i >= 0, or F(-i) = -F(i) or other restrictions.

gnasher729
  • 5,048
  • 11
  • 15