# A Look at Recurrence Relations

Page 1 of 1

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

### #1 dsnowdon

Reputation: 0
• Posts: 221
• Joined: 18-January 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

• Beginner

Reputation: 11017
• Posts: 18,801
• 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

### #3 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• 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) = ...

### #4 jon.kiparsky

• Beginner

Reputation: 11017
• Posts: 18,801
• 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.

### #5 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• 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

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12267
• Posts: 45,362
• 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.

### #7 dsnowdon

Reputation: 0
• Posts: 221
• Joined: 18-January 12

## Re: A Look at Recurrence Relations

Posted 17 January 2013 - 04:48 AM

lordofduct, 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)

### #8 mojo666

Reputation: 408
• Posts: 882
• 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

### #9 dsnowdon

Reputation: 0
• Posts: 221
• Joined: 18-January 12

## Re: A Look at Recurrence Relations

Posted 17 January 2013 - 12:08 PM

mojo666, 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

### #10 jon.kiparsky

• Beginner

Reputation: 11017
• Posts: 18,801
• Joined: 19-March 11

## Re: A Look at Recurrence Relations

Posted 17 January 2013 - 12:14 PM

DkSnowdon, 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)

### #11 dsnowdon

Reputation: 0
• Posts: 221
• Joined: 18-January 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

### #12 jon.kiparsky

• Beginner

Reputation: 11017
• Posts: 18,801
• 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.