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[101]!

Type your code here:

See your results here: