Big-O of recursive function Let $f:\mathbb{Z}_+ \to \mathbb{Z}_+$ be the function defined by $f(k)=3f(k-1)+2$ for any $k \in \mathbb{Z}_+$. Prove that $f(n)$ is $O(6^n)$.
How do I prove it with mathematical induction?

Let $g(k) = f(k)+1$, then $g(k) = 3 g(k-1)$ is a geometric sequence, hence $g(k)=3^k g(0)$ and $f(k) = 3^k (f(0)+1)-1$.
