Big-O of recursive function

Question

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?

Answer 1

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$.

Answer 2

from iteration :

$f(n)=3f(n-1)+2$

...

$\space\space\space\space\space\space\space\space=3^if(n-i-1)+2+6+18+...+2*3^i$

(n-i-1)=1 => i=n-2

$f(n)=3^{n-2}f(1)+\sum _{n=0}^{i}2*3^n$

$\sum_{n=0}^{i}2*3^n= {2(1-2*3^i) \over -2}=-(1-2*3^i) $

$f(n)=3^{n-2}-(1-2*3^{n-2})=-1+3^{n-2}(3)=-1+3^{n-1}$

induction :

n=0

$-1-3^{-1} $is O(1)

n=k

$-1+3^{k-1}=O(6^{k})$ => $3^{k-1}=O(6^{k})=> 6*3^k\le 3c6^{k+1}$

n=k+1

$-1+3^{k}\le3^{k}\le6*3^k\le 3c 6^{k+1}=> -1+3^k\le c'6^{k+1}=> -1+3^k=O(6^{k+1})$