5
$\begingroup$

Solve the recurrence of $T(n)= 3T(n-1)+1$ with $T(0)=2$ by iteration of the recurrence. (I was told that there is no need to prove it by induction)

I googled "iteration of the recurrence." I did not really get much except general proofs. Does anyone have a good explanation of this phrase that I can use to get me started?

$\endgroup$
4
$\begingroup$

$$T(n) = 3T(n-1)+1 = 9T(n-2) + 3 + 1 = 27T(n-3) + 9 + 3 + 1 = ...$$ So, $$T(n) = \sum_{m=0}^{n-1} 3^m + 2\cdot3^n = \frac{5\cdot 3^n-1}{2}$$ Using the formula for a sum of a geometric series.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

This cached copy tells me that 'iteration of recurrence' is a brute force way of listing the values of $T(n)$ for various values of $n$.

For example,

$T(1) = 3T(0) + 1 = 3 \cdot 2 + 1 = 7$. $T(2) = 3T(1) + 1 = 3 \cdot 7 + 1 = 3(3 \cdot 2 + 1) + 1 = 9 \cdot 2 + 3 + 1 = 22$. $T(3) = 3T(2) + 1 = 3 \cdot 22 + 1 = 3(3(3 \cdot 2 + 1)+1)+1 = 27 \cdot 2 + 9 + 3 + 1 = 67$.

We observe the pattern and guess
$T(n) = 2 \cdot 3^n + 3^{n-1} + \cdots + 1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Are you using $.$ instead of "\cdot" $\cdot$ on purpose? $\endgroup$ – nbubis Jul 13 '13 at 2:30
  • $\begingroup$ I am using \cdots and not the period. $\endgroup$ – Isomorphism Jul 13 '13 at 2:51
  • $\begingroup$ ok.. so why not \cdot? $\endgroup$ – nbubis Jul 13 '13 at 4:20
  • $\begingroup$ @Isomorphism maybe it's my browser, but I also see period there, not \cdots. Who does use \cdots for multiplication anyway? $\endgroup$ – Kaster Jul 14 '13 at 23:07
  • $\begingroup$ @Kaster: Thanks for the clarification. nbubis was talking about the dot used for multiplication. Yes, I have used the '.' for multiplication. Is it confusing? $\endgroup$ – Isomorphism Jul 15 '13 at 15:25

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.