More recurrence relations, and bounds on complexity

In finishing up the second assignment, recurrence relations (particularly, the Fibonacci sequence) came up once again. Once I noticed the pattern, it was obvious to see that it was directly related to the Fibonacci sequence (one digit ahead of it), but I unwound it and recombined it to get some practice.

It's interesting how every recurrence relation which somehow involves the summing of the two previous numbers in the sequence has a closed form related to the golden ratio. In the Fibonacci case, the golden ratio satisfies the equations

so the powers of the golden ratio satisfy the Fibonacci recurrence. It's cool to see how it works!

In other news, I've been having some difficulty keeping up with all the new material that gets covered in tutorials. My tutorial section has been a little bit unhelpful in clarifying my difficulties. I plan to do whatever reading I have time to fit in before tutorials (although time is still at a premium).