# Lesson goal: Evaluating a recurrence relation using arrays

Previous: Arrays and averaging numbers | Home | Next: Arrays and histograms

In a past lesson, you learned about arrays, and how they allow you to store a sequence of data under the same variable name.

In this lesson, let's use arrays to evaluate a "recurrence relation." Here is the recurrence relation (from Salkind, 1966): $F(n+1)=\frac{2F(n)+1}{2}$, given that $F(1)=2$.

Hopefully, you can see why this is a "recurrence relation." Suppose we wanted to find $F(2)$. Putting $n=2$ into the above relation, we'll get $F(2)=\frac{2F(1)+1}{2}$. As you can see, in order to find $F(2)$, we need to know what $F(1)$ is. Luckily here, $F(1)$ is given to be $2$ (most recurrence relations are given with some starting value like this). Notice that the function is defined in terms of itself--this is called a "recursive function" and is why the relation is called a "recurrence relation."

Given all of this, your job is to evaluate $F(101)$.

# Now you try. Fix the for loop and program in the recurrence relation to find F!

In this code, we've started you out by setting up the array F, and that we know F=2. Fix the for-loop to run over the proper values of n. Next program in the recurrence relation into the F[n]= line.

When done, try this recurrence relation: $F(n)=F(n-1)+F(n-2)$, given that $F(0)=0$ and $F(1)=1$. Evaluate all $F$'s from $n=2$ to $10$. The numbers you generate are called "Fibonacci Numbers." Dismiss.

Show a friend, family member, or teacher what you've done!