1
$\begingroup$

Specifically,

$$T(n)=3T(n-1)+1; \quad T(1)=1.$$

I have \begin{align*} T(n) & = 3T(n-1)+1 \\ & = 3(3T(n-2)+1)+1 \\ & = 9T(n-2)+4 \\ & = 9(3T(n-3)+1)+4 \\ & = 27T(n-3)+13 \\ & = \cdots \\ & = (3^k)T(n-k)+(3^k - 1). \end{align*}

Am I on the right track? I feel like something is off, b/c it doesn't work for the base case, but I don't know where I went wrong? and is there any hard and fast rule about how far you should "telescope" backwards?

Thanks in advance

  • 0
    There is a mistake in $3^k-1$, it's not quite that. Fix it, and then see what happens once $k \to n$.2012-10-03
  • 0
    @gt6989b - Alright I recognize it is wrong now, but I can't figure out a rule that works out for 2, 4, & 13. Is it relatively close?2012-10-03

6 Answers 6