Let T(n) be defined by the following recurrence relation
$\begin{equation} \begin{cases} T(0) = T(1) = 1 \\ T(n) = T(n−1) + T(n−2) + 1 \quad for \quad n ≥ 2 \end{cases} \end{equation}$
Show that T(n) = $2F_n − 1$ for $n \geq 0$, where $F_n$ is the $n$'th Fibonacci number, i.e.
$\begin{equation} \begin{cases} F_0 = F_1 = 1 \\ F_n = F_{n−1} + F_{n − 2} \quad for \quad n ≥ 2 \end{cases} \end{equation}$
I'm attempting to do this by induction, but perhaps it might not be the best route, I'm not entirely sure. I get stuck using that method. Any insight?
From the first equalities,
$$2T(0)-1=2T(1)-1=1$$ and from the recurrence
$$2T(n)-1=2(T(n-1)+T(n-2)+1)-1=2T(n-1)+2T(n-2)-1,$$
and you recognize the definition of the Fibonacci numbers.