5
$\begingroup$

I need your help with solving this recursion equation: $T(n)=3T(n-2)+9$. with the initial condition : $T(1)=T(2)=1$.

I need to find $T(n)$, the complexity of the algorithm which works that way.

I tried to do that with induction.

Edit: The answer should be depend on $n$.

Thank you.

  • 0
    Nir, @user6312: I decided to undelete and edit my answer.2011-07-07

3 Answers 3

4

Undeleted and edited. This idea is an expansion of Ross Millikan's comment. If there's any error the fault is mine.

The first few terms are

$\begin{eqnarray*} T(1) &=&T(2)=U(1)=1 \\ T(3) &=&T(4)=U(2)=12 \\ T(5) &=&T(6)=U(3)=45 \\ &&\cdots \end{eqnarray*}$

Generalizing, we have

$T(2n-1)=T(2n)=U(n),\qquad n\ge 1.\qquad (1)$

Since

$T(2n-1)=3T(2n-3)+9=3T(2n-2)+9,$

we obtain

$U(1)=1,\qquad U(n)=3U(n-1)+9,\qquad n\ge 2.\qquad (2)$

We will apply the rudiments of the theory of recurrences (or difference equations, see e.g. An introduction to difference equations by Saber Elaydi). This is an nonhomogeneous recurrence relation, consequently we have to find a particular solution of the recurrence and solve the homogeneous recurrence, which is linear and has constant coefficients. Hence, the explicit solution is of the form

$U(1)=1,\qquad U(n)=AX^{n}+C,\qquad (3)$

where $X$ is the root of the characteristic equation $X-3=0$ associated to the homogeneous equation $U(n)-3U(n-1)=0$ and $C$ is a particular solution (a constant, in this case) of $U(n)=3U(n-1)+9$. From $(2)$, we must have $C=3C+9$, i.e. $C=-9/2$. So $U(n)=3^{n}A-9/2$.

From the initial conditions $U(1)=1$, we get $1=3A-9/2$, and $A=11/6$. Thus the solution of $(2)$ is

$U(n)=\frac{11}{6}3^{n}-\frac{9}{2},\qquad n\ge 1.\qquad (4)$

Thus the solution of the given recurrence $T(n)=3T(n-2)+9$ is

$T(2n-1)=T(2n)=U(n)=\frac{11}{6}3^{n}-\frac{9}{2},\qquad n\ge 1.\qquad (5)$

  • 0
    @user6312: I undeleted and edited the answer. Than$k$s again!2011-07-07
4

Hint: First consider $G(n) = T(n) + \frac{9}{2}$

  • 0
    @Nir: The idea is to try to get rid of the constant. So you offset $T(n)$. So if $G(n) = T(n) - c$, we want $c$ so that $G(n) = 3G(n-2)$. Put that in, and see if we can solve for $c$ (also see the latter half of Brian's answer).2011-07-07
4

Induction is a way to prove things; it's not generally helpful in solving computational problems, except perhaps in proving that a guessed solution is correct.

Note that the values of $T(n)$ for odd $n$ are completely independent of the values for even $n$, so you can look at it as essentially two separate instances of the recursion $f(n+1) = 3f(n) + 9$ with initial condition $f(1) = 1$. There are lots of ways to solve that recurrence. One is to 'unwind' it, which is a bit like doing an induction: $f(n) = 3f(n-1)+9 = 3(3f(n-2)+9)+9$ = $3^2f(n-2)+3$ and so on. If you continue in this fashion, you'll find that after $k$ steps you have $f(n)$ = $3^kf(n-k) + 9 \sum_{i=0}^{k-1}3^i$; in particular, when $k=n-1$ you have $f(n) = 3^{n-1}f(1)+9\sum_{i=0}^{n-2}3^i$ = $3^{n-1} + 9 \cdot \frac{3^{n-1}-1}{2} = \frac{1}{2}\left(11 \cdot 3^{n-1} - 9\right)$.

Now $T(2n) = f(n) = \frac{1}{2}\left(11 \cdot 3^{n-1} - 9\right)$, and $T(2n-1) = f(n) = \frac{1}{2}\left(11 \cdot 3^{n-1} - 9\right)$.

A neater way to solve the $f$ recurrence is to let $g(n) = f(n) - d$ for some constant $d$ yet to be determined. Then $f(n) = g(n) + d$, so the recurrence can be written $g(n+1)+d$ = $3 \left(g(n)+d \right) + 9$ = $3g(n) + 3d + 9$, or $g(n+1)=3g(n) + 2d + 9$. Setting $d=-9/2$ makes this $g(n+1)=3g(n)$ with initial condition $g(1)=f(1)+9/2=11/2$. This is simple exponential growth: $g(n) = 3^{n-1}g(1)= \frac{11}{2} \cdot 3^{n-1}$. Hence $f(n) = g(n)-9/2 = \frac{1}{2}\left(11 \cdot 3^{n-1} - 9\right)$, of course giving the same solution for the original problem.