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)$.

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)$.

`F[101]`

!
Type your code here:

See your results here:

In this code, we've started you out by setting up the array

`F`

, and that we know `F[1]=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."