1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Unfold" the recurrence and use induction. $\endgroup$ – Sean Roberson Jan 11 '17 at 17:31
  • $\begingroup$ @SeanRoberson While that will indeed provide a proof of the fact, it won't necessarily communicate to the OP how to find the right answer in the first place. $\endgroup$ – Noah Schweber Jan 11 '17 at 17:35
2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.