Buscar una función no recursiva a partir de una función recursiva $f(n) = f(n-1) + 3^n$

Question

Tenemos $f(0) = 1 , f(1) = 4 , f(2) = 13 , f(n) = f(n-1) + 3^n$ (número de todos los triángulos del triángulo de Sierpinski)

Quiero encontrar una función no recursiva. Conozco la respuesta pero quiero una solución para ello.

Answer 1

Sugerencia

$$f(n)-f(n-1)=3^n$$

escribir:

$$f(1)-f(0)=3^1\\ f(2)-f(1)=3^2\\ f(3)-f(2)=3^3\\ ...\\ f(n)-f(n-1)=3^n$$

suma todo y consigue:

$$f(n)-f(0)=3+3^2+3^3+...+3^n$$

El LHS es una suma de secuencia geométrica.

¿Puedes terminar?

Answer 2

SUGERENCIA: $f(n)$ es la suma de una serie, es decir, $f(n)=3^0+3^1+3^2+...+3^n$ . ¿Reconoces qué tipo de serie es ésta (cómo se relacionan entre sí los términos sucesivos)? ¿Conoces algún método para sumar una serie de este tipo?

Answer 3

Bueno, este caso no es difícil. Está claro que $$f(n)=1+3+3^2+\cdots+3^n$$ Pero esto es una suma finita de una progresión geométrica: $$f(n)=\frac{3^{n+1}-1}{2}$$

Answer 4

Usted escribió

$$f(n) = f(n-1) + 3^n\tag{1}$$

Observamos que $f(0) = 3^0 = 1$ y empezamos a reescribir la ecuación $(1)$ sustituyendo algunos $f(x)$ :

$$f(n) = f(n-1) + 3^n = f(n-2) + 3^{n-1} + 3^n = f(n-3) + 3^{n-2} + 3^{n-1} + 3^n = 3^0 + 3^1 + \cdots + 3^{n-1} + 3^n$$

que es una serie geométrica de razón $3$ por lo tanto,

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

(suponiendo que esté familiarizado con las series geométricas)