Tutorial 3, Question 3: Fibonacci galore!

I was working on the last question for this week's tutorial today:

The first thing I noticed was that the definition of G(n) was very similar to the definition of the Fibonacci sequence we developed in class. In the back of my mind, I wanted to dive immediately into mucking around with the closed form definition of the Fibonacci sequence. However, I decided to stick with what the question asked me to do first: unwind the recurrence according to the provided pattern.

I noticed that in each unwinding, the terms were somehow related to Fibonacci numbers, whereas the input to G(n) was increasing by 1 in each time:

What could I do with that? I wasn't sure. I felt like there was some link that I should be grasping, but I just couldn't get a hold of it. After toying with some equations that didn't get me the right values, I decided to try a different tack: I'd find a closed form definition without using this unwinding pattern.

First, I wrote out some examples:

G(0) = 1
G(1) = 1
G(2) = 3
G(3) = 5
G(4) = 9
G(5) = 15
G(6) = 25
G(7) = 41

The numbers looked vaguely Fibonacci-like, but I couldn't quite grasp the exact pattern. So I made a chart of Fibonacci numbers (F(n)) vs. G(n). I noticed something suspicious about the differences... I subtracted F(n+1) from G(n), and the result was always F(n+1) - 1:

So I'd found my relation! G(n) = 2F(n+1) - 1. There was still the tiny problem that this definition is wrong for G(0); instead of G(0) = 1, it gives G(0) = -1. So I made a tiny adjustment:

...and proved that my closed form definition was the same as the open form definition provided in the question (I was rather tired, so instead of writing each side of the equation out, I just did LS = RS (left side = right side)):

I wonder how I would've discovered this closed form definition by unwinding the pattern given in the question. I suspect that it should be very easy to do, given all the observations I've already made. However, my mind is so clouded with numbers right now that I just don't see it. So, I'll walk away from this question for now, and come back to it tomorrow. Some problems cannot be solved without a refreshed mind.

Today: Pisa, Italy
It only makes sense for us to talk about Leonardo Pisano Bigollo (1170 - 1250), better known just as Fibonacci, today. Despite the sequence's name, Fibonacci did not discover it; the sequence was known to Indian mathematicians much earlier. The sequence is named after Fibonacci because he introduced the sequence to Western European mathematics.

One more thing Fibonacci introduced to (and popularized in) Europe: Hindu-Arabic numbers (e.g. 1, 22, 108) in Europe. Before that, math was done with the dreadfully inconvenient Roman numbers (e.g. I, XXII, CVIII). So, make sure you thank Fibonacci for making mathematics a lot easier for us to notate today.