Big-O de la función recursiva

Question

Dejemos que $f:\mathbb{Z}_+ \to \mathbb{Z}_+$ sea la función definida por $f(k)=3f(k-1)+2$ para cualquier $k \in \mathbb{Z}_+$ . Demostrar que $f(n)$ es $O(6^n)$ .

¿Cómo lo demuestro con la inducción matemática?

Answer 1

Dejemos que $g(k) = f(k)+1$ entonces $g(k) = 3 g(k-1)$ es una secuencia geométrica, por lo que $g(k)=3^k g(0)$ y $f(k) = 3^k (f(0)+1)-1$ .

Answer 2

de la iteración :

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

inducción :

n=0

$-1-3^{-1} $ es 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})$