1
$\begingroup$

So I'm not looking for a general solution but rather a specific one. I'm calculating the time complexity of an algorithm and I would want to be able to formulate the growth of the constants with a good-looking formula.

The sequence is as follows: {1, 4, 13, 40, 121, 364...}. I see that the sequence grows as $f(n) = 3 * f(n-1) + 1$, but is there any way to formulate this sequence non-recursively?

$\endgroup$
2
$\begingroup$

You have $f(1)=1$, and $f(n)=3f(n-1)+1$ gives you, via recursive substitution, $f(2)=3f(1)+1$, $f(3)=3^2f(1)+3^1+1$, $f(4)=3^3+3^2+3^1+1$, and generally $f(n)=3^{n-1}f(1)+3^{n-2}+\ldots+3^{1}+1$. Since $f(1)=1$, you have $f(n)=\sum_{i=1}^{n}3^{i-1}$. Multiply the expression by $\frac{-1+3^n}{-1+3^n}$ and simplify to $f(n)=\frac{-1+3^n}{2}$.

$\endgroup$
  • $\begingroup$ Thank you so much, that's perfect! $\endgroup$ – Nyfiken Gul Feb 7 '17 at 11:49
1
$\begingroup$

Motivated by the growth rate one could expect that $f(n)=a3^n+b$ for some numbers $a,b$. Solving $f(1)=1$ and $f(2)=4$ for $a,b$ yields $a=1/2$ and $b=-1/2$, which works for the rest of the given sequence.

$\endgroup$
  • $\begingroup$ Thanks chap, that looks great! $\endgroup$ – Nyfiken Gul Feb 7 '17 at 11:49

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.