11 Replies - 2481 Views - Last Post: 17 January 2013 - 12:33 PM

#1 DkSnowdon  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 128
  • Joined: 31-October 12

A Look at Recurrence Relations

Posted 07 January 2013 - 07:35 AM

i haven been given this question to solve and i have having truble understanding the problem and that the function f actually does.

III  Calculating  Programs
Suppose that you are part of a team developing an avionics software system. There is a component 
in the system that reads values from the physical environment, transforms those values into natural 
numbers and converts them using a function f defined as:
f(0) =0, f(1) =1, and
f(k+2)  = f(k) +f(k+1) for k≥0 .
According to the system requirements, there are three program variables x, y, and n that need to 
be updated every few seconds maintaining the following system invariant:
(1)       x = f(n)  ∧  y = f(n+1)    .
It is assumed that this invariant should be valid throughout the execution of the system. The 
requirements also specify that the value of the program variable n is initially zero and should be 
incremented by 1 whenever x and y are updated. Now, answer the following questions:
Question 1 (5%) 
What are the values of f(0), f(1), f(2) and f(3) ?   Your answer should make clear how the definition 
of f is used.



any help is appreciated , i dont want the answer just a more in depth explanation of whats going on

thanks dale

This post has been edited by macosxnerd101: 07 January 2013 - 10:09 AM
Reason for edit:: Renamed title to be more descriptive


Is This A Good Question/Topic? 0
  • +

Replies To: A Look at Recurrence Relations

#2 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7645
  • View blog
  • Posts: 12,898
  • Joined: 19-March 11

Re: A Look at Recurrence Relations

Posted 07 January 2013 - 08:32 AM

The easiest way to understand what f() does is to calculate it for some values. Plug in the values 1 through 10 for n and calculate f(n).

Writing it as f(k+2) = f(k) +f(k+1) for k≥0 is a little confusing, maybe. Try looking at it like this:

f(k):
  if k == 0:  return 0
  else if k == 1:  return 1
  else return f(f-2)+ f(k-1) 





Digression (this is not strictly related to your question)

If you try calculating this manually for, say, f(7), you'll see that you're calculating the same value over and over again. This shows the value of a technique called "memoization", which remembers the values that you've already calculated. Imagine that we have a function called "store" which writes a key, value pair to some map somewhere in memory, and another function called "get" which takes a key and either returns a value or some "no value here" sentinel.

Now you can write the function somewhat like this:

store (0,0)
store (1,1)
f(k):
  value = get (k)    # if we know the answer
  if (value) return (value)  # then just return it
  else store (k, f(f-2)+ f(k-1))   #otherwise, calculate it and store it
  return get(k)             # now we've stored it, so just get it and return it


This post has been edited by jon.kiparsky: 07 January 2013 - 08:32 AM

Was This Post Helpful? 1
  • +
  • -

#3 lordofduct  Icon User is online

  • I'm a cheeseburger
  • member icon


Reputation: 2533
  • View blog
  • Posts: 4,633
  • Joined: 24-September 10

Re: A Look at Recurrence Relations

Posted 07 January 2013 - 08:54 AM

I'm going to avoid giving the actual answer directly, but I'll just say that the sequence defined by f(k) is a very very famous sequence discovered by an Italian man while away in Africa based on maths he obtained from the Muslims... and he applied it to rabbits... dirty dirty rabbits.


Anyways, the "make clear" part I think is asking you to show each f(0) f(1) f(2)... etc but show what you calculated to get each

Quote

f(0) = 0 as defined
f(1) = 1 as defined
f(2) = f(0) + f(1) = ...

Was This Post Helpful? 1
  • +
  • -

#4 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7645
  • View blog
  • Posts: 12,898
  • Joined: 19-March 11

Re: A Look at Recurrence Relations

Posted 07 January 2013 - 08:57 AM

Cuddly, cute, fuzzy bunnies, you mean. Also, tasty.
Was This Post Helpful? 0
  • +
  • -

#5 lordofduct  Icon User is online

  • I'm a cheeseburger
  • member icon


Reputation: 2533
  • View blog
  • Posts: 4,633
  • Joined: 24-September 10

Re: A Look at Recurrence Relations

Posted 07 January 2013 - 09:08 AM

cuddly and cute, but doing dirty dirty acts
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10469
  • View blog
  • Posts: 38,804
  • Joined: 27-December 08

Re: A Look at Recurrence Relations

Posted 07 January 2013 - 10:12 AM

There is also a very nice way to mathematically solve the recurrence relation. :)
Was This Post Helpful? 0
  • +
  • -

#7 DkSnowdon  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 128
  • Joined: 31-October 12

Re: A Look at Recurrence Relations

Posted 17 January 2013 - 04:48 AM

View Postlordofduct, on 07 January 2013 - 08:54 AM, said:

I'm going to avoid giving the actual answer directly, but I'll just say that the sequence defined by f(k) is a very very famous sequence discovered by an Italian man while away in Africa based on maths he obtained from the Muslims... and he applied it to rabbits... dirty dirty rabbits.


Anyways, the "make clear" part I think is asking you to show each f(0) f(1) f(2)... etc but show what you calculated to get each

Quote

f(0) = 0 as defined
f(1) = 1 as defined
f(2) = f(0) + f(1) = ...


thanks for the help
but then for k(3) = ... = ...
how do i work out the middle part , for f(2) two does it get broken down into f(2) = f(0) + f(1)
Was This Post Helpful? 0
  • +
  • -

#8 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 771
  • Joined: 27-June 09

Re: A Look at Recurrence Relations

Posted 17 January 2013 - 09:50 AM

You can keep breaking all occurences of f(n) until you are left with numbers and then add them up. Alternatively, you can figure out the result of each f on inputs 0 through the number. For example, f(8) = f(7) + f(6). I can break down f(7) and f(6) and then break down those results and so on. This will leave me with a bunch of zeros and ones to add up. It is much faster to figure out f(0)=0, f(1)=1, which means f(2)=1, which means....which means f(6)=8, which means f(7)=13, which means f(8)=8+13=21
Was This Post Helpful? 0
  • +
  • -

#9 DkSnowdon  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 128
  • Joined: 31-October 12

Re: A Look at Recurrence Relations

Posted 17 January 2013 - 12:08 PM

View Postmojo666, on 17 January 2013 - 09:50 AM, said:

You can keep breaking all occurences of f(n) until you are left with numbers and then add them up. Alternatively, you can figure out the result of each f on inputs 0 through the number. For example, f(8) = f(7) + f(6). I can break down f(7) and f(6) and then break down those results and so on. This will leave me with a bunch of zeros and ones to add up. It is much faster to figure out f(0)=0, f(1)=1, which means f(2)=1, which means....which means f(6)=8, which means f(7)=13, which means f(8)=8+13=21



therefor

f(3) = f(2) + f(1)
and f(2) = f(1) + f(1)

sorry if i am completely wrong here , i am haveing truble grasping this subject
Was This Post Helpful? 0
  • +
  • -

#10 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7645
  • View blog
  • Posts: 12,898
  • Joined: 19-March 11

Re: A Look at Recurrence Relations

Posted 17 January 2013 - 12:14 PM

View PostDkSnowdon, on 17 January 2013 - 02:08 PM, said:

therefor

f(3) = f(2) + f(1)
and f(2) = f(1) + f(1)

sorry if i am completely wrong here , i am haveing truble grasping this subject



f(n) = f(n-1) + f(n-2) // for n > 1

so f(2) = f(1) + f(0)
Was This Post Helpful? 0
  • +
  • -

#11 DkSnowdon  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 128
  • Joined: 31-October 12

Re: A Look at Recurrence Relations

Posted 17 January 2013 - 12:27 PM

ahh i get it, i hate things like that how when you know how to do it its so simple.

just to check
f(3) = f(2) + f(1) = 2

also were did you get his from

Quote

f(n) = f(n-1) + f(n-2) // for n > 1

This post has been edited by DkSnowdon: 17 January 2013 - 12:33 PM

Was This Post Helpful? 0
  • +
  • -

#12 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7645
  • View blog
  • Posts: 12,898
  • Joined: 19-March 11

Re: A Look at Recurrence Relations

Posted 17 January 2013 - 12:33 PM

f(3) = f(2) + f(1) = ( f(1) + f(0) ) + f(1) = (1+ 0) +1 = 2

So yes.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1