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