Find an non recursive function from recursive function $f(n) = f(n-1) + 3^n$

Question

We have $f(0) = 1 , f(1) = 4 , f(2) = 13 , f(n) = f(n-1) + 3^n$ (number of all of triangles in Sierpinski triangle)

I want to find a non recursive function. I know the answer but I want a solution for it.

Answer 1

Hint

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

write:

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

sum everything and get:

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

The LHS is a sum of geometric sequence.

Can you finish?

Answer 2

HINT: $f(n)$ is the sum of a series - that is, $f(n)=3^0+3^1+3^2+...+3^n$. Do you recognize what kind of series this is (how do successive terms relate to one another)? Do you know a method for summing such a series?

Answer 3

Well, this case is not difficult. It is clear that $$f(n)=1+3+3^2+\cdots+3^n$$ But this is a finite sum of a geometric progression: $$f(n)=\frac{3^{n+1}-1}{2}$$

Answer 4

You wrote

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

We note that $f(0) = 3^0 = 1$ and we start rewriting equation $(1)$ by substituting some $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$$

which is a geometric series of ratio $3$; therefore,

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

(assuming you are familiar with geometric series)