The sequence $g_1,g_2,$dots is defined by the recurrence relation

$g_n=g_{n-1}+g_{n-2}+1,n3,$

and initial conditions $g_1=1,g_2=3.$ By using mathematical

induction or otherwise, show that

$g_n=2f_{n+1}-1,n1,$

where $f_1,f_2,$dots is the Fibonacci sequence.