How can I write a recursive function based on the outputs of a function python

Question

I have to write a recursive function in python that generalizes the following function:

f(n)   result
0      1
1      1
2      2
3      5
4      13
5      34
6      89
7      233

I made something like this:

def F(n):
   if n <= 0:
      return 1
   else:
      return 2*( F(n-1) + F(n-2) ) - F(n-3)

It works with almost all values of the range but it doesn't match with the 3 first results so. How can I determine a recursive function based on the outputs?

I have this information:

"Hint: F(n) is recursively defined in terms of F(n-1) and F(n-2). You have to figure out the math expression that will make this happen. Hint: no coefficient of the function in this expression is greater than 5, nor less than 1, and any such coefficient is an integer."

Is the hint saying that F(n) is defined as exactly a*F(n-1) + b*F(n-2), where the exercise is to determine what a and b are? — quamrana
– quamrana, Commented Jul 10, 2021 at 17:30
The goal is to get the function that produces the result. It doesn't matter how many coefficients you use as they are in the range(1, 5) and the function is based on f(n-1) and f(n-2). In my code f(n-3) should not be there but it was a coincidence — Isaac Garcia
– Isaac Garcia, Commented Jul 10, 2021 at 17:34
Ok, but there might be a infinite range of forms to search. For instance, why have you chosen: 2*F(n-1) + 2*F(n-2) - F(n-3)? — quamrana
– quamrana, Commented Jul 10, 2021 at 17:37
I used 2*F(n-1) + 2*F(n-2) - F(n-3) just by coincidence. because using my calculator it matched with the results for the bigger values. but I couldn't get the right answer so I am looking is someone can give an idea of how to solve this type of problem — Isaac Garcia
– Isaac Garcia, Commented Jul 10, 2021 at 17:42
I think its a case of just searching for the values of the coefficients. The hint mentions: F(n-1) and F(n-2). Are these the only terms you are expected to use? — quamrana
– quamrana, Commented Jul 10, 2021 at 17:43

Epsi95 · Accepted Answer · 2021-07-10 17:31:50Z

1

you need 3 base case

def F(n):
    if n <= 1:
      return 1
    elif(n == 2): #-------->
        return 2
    else:
      return 2*( F(n-1) + F(n-2) ) - F(n-3)

or

def F(n):
    if n<= 1:
        return 1
    else:
        return 3*F(n-1) - F(n-2)

answered Jul 10, 2021 at 17:31

Epsi95

9,1071 gold badge19 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Epsi95 Over a year ago

I did not see the problem statement, I was jut pointing that u need 3 base case, lemme check

Isaac Garcia Over a year ago

Thanks is a good solution. Any advice on how to find the best base case?

Epsi95 Over a year ago

check you n should be >=0 like 0,1,2 so if you don't put the base case elif(n == 2): it becomes return 2*( F(1) + F(0) ) - F(-1), -1 so you need to put this in the base case

user_na · Accepted Answer · 2021-07-10 17:57:36Z

0

A good source for integer sequences is OEIS. Your sequence has the number A001519. From there we learn that:

a(n) = 3*a(n-1) - a(n-2) for n >= 2, with a(0) = a(1) = 1.

Which is the solution @Epsi95 found.

Another nice property of this sequence is:

This is a bisection of the Fibonacci sequence A000045. a(n) = F(2*n-1), with F(n) = A000045(n) and F(-1) = 1

answered Jul 10, 2021 at 17:57

user_na

2,2831 gold badge20 silver badges37 bronze badges

Collectives™ on Stack Overflow

How can I write a recursive function based on the outputs of a function python

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related