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.

$\endgroup$
  • 4
    $\begingroup$ Note that there is no communication between the odd and even $n$, so you can make it $T(m)=3T(m-1)+9$ with $T(1)=1$. $\endgroup$ – Ross Millikan Jul 7 '11 at 19:28
  • $\begingroup$ I have to ask, is this homework? $\endgroup$ – Aryabhata Jul 7 '11 at 19:45
  • $\begingroup$ No, it is not.. $\endgroup$ – user6163 Jul 7 '11 at 20:26
  • $\begingroup$ I deteted my answer, because it was wrong. @user6312:Thanks! You are right, my answer was for a different recursion, as you wrote $U(n)=3U(n-1)+9U(n-2)$. $\endgroup$ – Américo Tavares Jul 7 '11 at 21:08
  • $\begingroup$ Nir, @user6312: I decided to undelete and edit my answer. $\endgroup$ – Américo Tavares Jul 7 '11 at 21:54
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @user6312: I undeleted and edited the answer. Thanks again! $\endgroup$ – Américo Tavares Jul 7 '11 at 21:52
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you please extend your hint? I don't see how I can consider it. $\endgroup$ – user6163 Jul 7 '11 at 19:27
  • 1
    $\begingroup$ @Nir: Try to get a recurrence which $G(n)$ satisfies. $\endgroup$ – Aryabhata Jul 7 '11 at 19:28
  • $\begingroup$ Sorry, but I don't understand. $\endgroup$ – user6163 Jul 7 '11 at 19:37
  • $\begingroup$ @Nir: If $T(n) = 3 T(n-2) + 9$ and $G(n) = T(n) + 9/2$ then can you try an write $G(n)$ in terms of $G(n-2)$? $\endgroup$ – Aryabhata Jul 7 '11 at 19:45
  • $\begingroup$ Sure I can, it's simply $G(n)=3G(n-2)$. $\endgroup$ – user6163 Jul 7 '11 at 20:23
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy