Prove that $F(n+1) = g(n)+1$ 
Let $g(n)$ be defined by $g(1) = 0,g(2) = 1, g(n+2) = g(n)+g(n+1)+1$. Prove that if the Fibonacci sequence is defined by $F_n = F_{n-1}+F_{n-2}$ where $F_1 = 1, F_2 = 1$, then $F(n+1) = g(n)+1$ for $n \geq 1$.

I was thinking about proving this using induction, but I was wondering if there was an easier way to make sense of it.

Hint $\ f(n) := g(n\!-\!1)+ 1\,$ satisfies the same recurrence as $\,F_n\,$ and has the same initial conditions $\,f(2) = 1,\, f(3) = 2\,$ so $\,f(n) = F_n\,$ for all $\,n>1\,$ by the uniqueness theorem for recurrences (which has an extremely short and easy proof by induction)
Remark $  $ You could, of course, do the inductive proof directly, skipping the language of the uniqueness theorem, but the slight amount of extra effort to understand it from the perspective of uniqueness will prove very useful for solving similar problems. 
