I am solving warm up problem 1.2 from Concrete Mathematics book. I've got the right answer by induction:
$$ f(0) = 0\\ f(n) = 3f(n-1) + 2, $$
But I can not figure how to simplify it to the closed form. I've looked in the answers and saw this: $$ f(n) = 3^n -1 $$
Can anyone clarify to me how to get this closed form solution?
Set $f(m)=g(m)-1$
$\implies g(0)=1$ and $g(m+1)=3g(m)$
$\implies g(m+1)=3^{r+1}g(m-r)$ for $0\le r\le m$
$g(m+1)=\cdots=3^{m+1}\cdot g(0)$