Solving Recurrences using Telescoping/Backwards Substitution Specifically, 

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

I have
\begin{align*}
T(n) &amp; = 3T(n-1)+1 \\
&amp; = 3(3T(n-2)+1)+1 \\
&amp; = 9T(n-2)+4 \\
&amp; = 9(3T(n-3)+1)+4 \\
&amp; = 27T(n-3)+13 \\
&amp; = \cdots \\
&amp; = (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
Here is a general method. You are given $T_n=A(T_{n-1})$ for some affine function $A$, defined by $A(x)=ax+b$, and you want to iterate $A$ because you know that $T_n=A^{n-1}(T_1)$ for every $n\geqslant1$. This is doable because:


Affine functions are conjugate to linear functions.
Linear functions are easy to iterate, to wit, if $L:x\mapsto cx$, then $L^n(x)=c^nx$.


Thus, the task is to find $L$ linear such that $A$ and $L$ are conjugate. Here is the only bit to remember: 


  The function $A$ is conjugate to a linear function $L$ through a translation, for every $a\ne1$, and the translation should send the fixed point of $L$, which is $0$, to the fixed point of $A$.


Hence the first task is to find the fixed point $z_A$ of $A$: this solves $z_A=A(z_A)=az_A+b$, that is, $z_A=b/(1-a)$ (since $a\ne1$). 

And now, behold, for every $t$, $A(z_A+t)=A(z_A)+at=z_A+at$. Iterating, one sees that, for every $n$, $A^n(z_A+t)=z_A+a^nt$ for every $t$, that is, $A^n(x)=z_A+a^n(x-z_A)$. (Once again, this algebraic miracle occurs due to the conjugation of $A$ to $L:t\mapsto at$.)

Here, $(a,b)=(3,1)$ hence $z_A=-\frac12$ and $T_n=A^{n-1}(1)=z_A+3^{n-1}(1-z_A)=\frac12(3^n-1)$.
There is a simple way to make this kind of recurrence homogenous. Let $A(n)=T(n) +a$
such that the recurrence satisfied by it is homogenous. We get, $a=3a+1$,$a=-\frac{1}{2}$

The question is simplified to:

$A(n)=3A(n-1)$

which is easy to solve.