# Solving Recurrences using Telescoping/Backwards Substitution

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?

-
There is a mistake in $3^k-1$, it's not quite that. Fix it, and then see what happens once $k \to n$. –  gt6989b Oct 3 '12 at 18:44
@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? –  Extinct23 Oct 3 '12 at 20:36

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)$.

-

The solution is

$$\frac{1}{2}\,{3}^{n}-\frac{1}{2}\,.$$

Here is how you solve it.

-

You're on the right track. Note that for any positive integer $k$ and any $x\in\Bbb R$ with $x\neq 1$, we have $$\sum_{j=0}^{k-1}x^j=\frac{x^k-1}{x-1}.$$ That should let you fix the problem. (Hint: The $3^k-1$ isn't right.)

Better Hint: You can use the above (with $x=3$) to see that instead of $3^k-1$, you should have $\frac{3^k-1}{3-1}=\frac{3^k-1}2$. That fits $2,4,13,$ and so on. You were very close.

-
I'm not following how that helps? Could you possibly restate it? –  Extinct23 Oct 3 '12 at 20:37

I always like to do such problems with matrix-expressions. For simpliness of notation let's write $x_k$ for the k'th iterate of the function beginning at $x_0$ . Then $$\begin{array} {rrr} &* & \begin{bmatrix} 1 & 1 \\ 0 & 3 \end{bmatrix} \\ \begin{bmatrix} 1 & x_1 \end{bmatrix} &=& \begin{bmatrix} 1 & x_2 \end{bmatrix} \end{array}$$ Let's denote the x-matrices with a capital letter $X$, and the transfermatrix $T$. Then obviously iterating means iterating the matrix-multiplication, aka using powers of $T$. So $$X_1 \cdot T^n = X_{1+n}$$ This "catches" in some sense the problem, how to express the repeated application of a transformation rule or "Operator" beginning at some start-value. Then you hope for a more convenient expression of such matrix-powers.

This has a very clear (in my view) formulation now even if you simply observe the pattern (and arrive at the same solutions as already given in other posts, just try it with some multiplications.)

Moreover, one can then use the concept of matrix-diagonalization, where $T = M \cdot D \cdot M^{-1}$ where $D$ is diagonal and then $T^n = M \cdot D^n \cdot \ M^{-1}$ where $D^n$ is then simply the n'ths powers of the diagonal elements in $D$ and because the matrices are only 2x2 there is a short expression for the second element in $T_n$ (and from this then in $X_n$) containing the n'th power of some values $d_0$ and $d_1$ in a linear expression in the initial selection of $x_0$ . This is then a pretty general ansatz for such problems.
In this case the two diagonal elements of $D$ are 1 and 3 which makes, that the full expression for the general $x_n$ involves simply $3^n$ as the "most complicated" term, just try it. (If you caught "fire" for this method look out for a nice article of Rob Johnson with title "Fibonacci numbers with matrices" which gives a wide&deep insight on the most introductory level in the similar problem-solution using $x_{k+2}= x_k + x_{k+1} \quad$ with that matrix-method).

-

Write your equation as $$T(n)-3T(n-1)=1\qquad(n\geq1)\ .\qquad(1)$$ It's an inhomogeneous linear problem, like $Ax=c$. The general solution $n\mapsto T(n)$ of such a problem can be written as a sum of the general solution of the associated homogeneous problem $Ax=0$, or in our case: $$x(n)- 3x(n-1)=0\qquad(n\geq1)\ ,\qquad(2)$$ and a single (so-called "particular") solution of the original problem $(1)$ found by whatever means, e.g., guessing.

The general solution of $(2)$ is obviously $x_h(n)=C\cdot 3^n$, with arbitrary $C$.

The inhomogeneity of $(1)$ is a constant function, and this leads us to conjecture that there is a particular solution $n\mapsto x_p(n)$ which is constant as well. So we try with $x_p(n):=a$ with an as yet undetermined $a$. This leads to the condition $a-3a=1$, and we see that $x_p(n):=-{1\over2}$ is in fact a particular solution of $(1)$.

Therefore the general solution of $(1)$ is given by $$T(n)=x_h(n)+x_p(n)=C\cdot 3^n -{1\over2}\ .$$ The condition $T(1)=1$ enforces $C={1\over2}$, so that we have definitively $$T(n)={1\over2}(3^n-1)\qquad(n\geq1)\ .$$

-

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.

-