# Recurrence relation

• Jan 30th 2009, 07:45 PM
drthea
Recurrence relation
Hello,
I am trying to understand how to solve this kind of problems but I am stuck in this.
It is given this recurrence relation:

$\displaystyle T(n) = 3T(n - 1) - 2T(n - 2), T(1)=1, T(2)=2$

and the solution is as follows:

$\displaystyle T(n) = 3T(n - 1) - 2T(n - 2) = 7T(n - 2) - 6T(n - 3) = 15T(n - 3) - 14T(n - 4)$

so $\displaystyle T(n)=(2^k -1)T(n-k-1)-(2^k -2)T(n-k)$

I don't get how it goes from $\displaystyle T(n) = 3T(n - 1) - 2T(n - 2)$
to $\displaystyle 7T(n - 2) - 6T(n - 3)$,
Also why T(1)=1, T(2)=2 are given? Where should I use them?
• Jan 30th 2009, 08:22 PM
drthea
Actually I found out how to do it (Nod)

$\displaystyle \begin{array}{rcl} T(n) = (3T(n - 1) - 2T(n - 2) \\ = 3( 3T(n - 2) - 2T(n - 3)) - 2T(n - 2) \\ = 9T(n - 2) - 6T(n - 3) - 2T(n - 2) \\ = 7T(n - 2) - 6T(n - 3) \end{array}$

By the way, how can I add a new line in the latex code?
If I type // at the end (where I'd like the new line to begin), It doesn't work for me. Am I doing something wrong?
• Jan 30th 2009, 08:36 PM
Rincewind
Quote:

Originally Posted by drthea
By the way, how can I add a new line in the latex code?
If I type // at the end (where I'd like the new line to begin), It doesn't work for me. Am I doing something wrong?

You can do it within an array environment where you use the & to delimit cells and \\ to start new lines. See example below...

$\displaystyle \begin{array}{rcl} e^{in\theta} & = & \left(\cos\theta + i \sin\theta\right)^n \\ & = & \cos n\theta + i \sin n\theta \end{array}$

Which is written

\begin{array}{rcl}
e^{in\theta} & = & \left(\cos\theta + i \sin\theta\right)^n \\
& = & \cos n\theta + i \sin n\theta
\end{array}
• Jan 31st 2009, 03:32 AM
PaulRS
Let $\displaystyle a_n=T(n+1)-T(n)$

From your equation we find that: $\displaystyle T(n)-T(n-1)=2\cdot{\left(T(n-1)-T(n-2)\right)}$

That is: $\displaystyle a_n=2\cdot{a_{n-1}}$ then $\displaystyle a_n=a_0\cdot{2^n}$

Now $\displaystyle \sum_{k=0}^{n-1}a_{k}=\sum_{k=0}^{n-1}{\left[T(k+1)-T(k)\right]}=T(n)-T(0)$

However: $\displaystyle \sum_{k=0}^{n-1}a_{k}=a_0\cdot \sum_{k=0}^{n-1}2^k=a_0\cdot(2^n -1)$

Hence: $\displaystyle T(n)=T(0)+\left[T(1)-T(0)\right]\cdot(2^n -1)$
• Jan 31st 2009, 07:03 AM
Jester
Quote:

Originally Posted by drthea
Hello,
I am trying to understand how to solve this kind of problems but I am stuck in this.
It is given this recurrence relation:

$\displaystyle T(n) = 3T(n - 1) - 2T(n - 2), T(1)=1, T(2)=2$

and the solution is as follows:

$\displaystyle T(n) = 3T(n - 1) - 2T(n - 2) = 7T(n - 2) - 6T(n - 3) = 15T(n - 3) - 14T(n - 4)$

so $\displaystyle T(n)=(2^k -1)T(n-k-1)-(2^k -2)T(n-k)$

I don't get how it goes from $\displaystyle T(n) = 3T(n - 1) - 2T(n - 2)$
to $\displaystyle 7T(n - 2) - 6T(n - 3)$,
Also why T(1)=1, T(2)=2 are given? Where should I use them?

Another way, maybe a little more straight forward. You have a second order difference equation. Seek solutions of the form

$\displaystyle T(n) = c \rho^n$

so substituting into

$\displaystyle T(n)-3T(n-1)+2T(n-2) =0$

gives

$\displaystyle c\rho^{n-2}\left( \rho^2-3 \rho + 2 \right)=0$

or

$\displaystyle \rho = 1,\;\;\; \rho = 2$

Then general solution of the difference equation is

$\displaystyle T(n) = c_1 1^n + c_2 2^n = c_1 + c_2 2^n$

$\displaystyle T(1)=1,\;\;\;T(2) = 2$

to find the constants. Your final answer $\displaystyle T(n) = 2^{n-1}$.
• Jan 31st 2009, 10:19 AM
drthea
@danny arrigo: I like that solution, it is really simple but it is required to solve them by repeated substitution.
@PaulRS: I don't understand how to do that (Worried)
• Jan 31st 2009, 10:25 AM
Jester
Quote:

Originally Posted by drthea
@danny arrigo: I like that solution, it is really simple but it is required to solve them by repeated substitution.
@PaulRS: I don't understand how to do that (Worried)

What do you mean by repeated substitution? Do you mean substituting the form

$\displaystyle T(n) = c \rho^n$ into the difference equation?
• Jan 31st 2009, 10:40 AM
drthea
Quote:

Originally Posted by danny arrigo
What do you mean by repeated substitution? Do you mean substituting the form

$\displaystyle T(n) = c \rho^n$ into the difference equation?

Hello,
no it is another method, please see here Solving Recurrence Relations-Repeated Substitution.
But I don't know if those methods are somehow related to each other.
• Jan 31st 2009, 11:07 AM
Jester
Quote:

Originally Posted by drthea
Hello,
no it is another method, please see here Solving Recurrence Relations-Repeated Substitution.
But I don't know if those methods are somehow related to each other.

They appear different to me but lead to the same answer. Your method backs down to the initial condition. Consider the following ex.

$\displaystyle T(n) = 2 T(n-1),\;\;\;T(0)=3$

$\displaystyle T(n) = 2 T(n-1) = 2 \cdot 2 \,T(n-2) = 2^3 \,T(n-3) = \cdots = 2^k \,T(n-k)$

Set $\displaystyle k = n$ so

$\displaystyle T(n) = 2^n T(0) = 3 \;2^n$

My method:

Subs $\displaystyle T(n) = c\cdot \rho^n$ so from the difference equation$\displaystyle c \rho^n = 2c \rho^{n-1}$ so $\displaystyle \rho = 2$. Thus

$\displaystyle T(n) = c\; \rho^n$. From the IC $\displaystyle T(0) = c2^0 = c = 3$ so we have the solution

$\displaystyle T(n) = 3 \,2^n$

same answer. With higher order difference equations, I think your method would be cumbersome whereas as mine not so much. Just my thoughts :)
• Jan 31st 2009, 11:11 AM
PaulRS
With all the details... - you should have said what exactly you didn't understand-

Suppose we have a recurrence of the form $\displaystyle a_n=3a_{n-1}-2a_{n-2}$; $\displaystyle \forall n \in \mathbb{N}/n \geqslant 2$

That is equivalent to: $\displaystyle a_n-a_{n-1}=2a_{n-1}-2a_{n-2}=2\cdot{\left(a_{n-1}-a_{n-2}\right)}$ (1)

Now, would not it be easy to solve for the sequence: $\displaystyle b_{n}=a_{n}-a_{n-1}$ since (1) translates into: $\displaystyle b_{n}=2b_{n-1}$

Which can be solved iterating like this:$\displaystyle b_{n}=2b_{n-1}=2\cdot{\left(2b_{n-1}\right)}=...=2^k\cdot b_{n-k}=...=2^{n-1}\cdot{b_1}$ (2)

What happens if we sum: $\displaystyle \sum\limits_{k = 1}^n {b_k }$ ?

Well, on the one hand we can say that: $\displaystyle \sum\limits_{k = 1}^n {b_k } = \sum\limits_{k = 1}^n {\left( {a_k - a_{k - 1} } \right)} = \left( {a_1 - a_0 } \right) + \left( {a_2 - a_1 } \right) + ... + \left( {a_n - a_{n - 1} } \right) = a_n - a_0$ just by using the definition of $\displaystyle b_n$ and noticing that the sum is telescoping. (3)

On the other hand: $\displaystyle \sum\limits_{k = 1}^n {b_k } = \sum\limits_{k = 1}^n {\left( {b_1 \cdot 2^{k-1} } \right)} =b_1 \cdot \sum\limits_{k = 1}^n {2^{k-1} } =b_1 \cdot \sum\limits_{k = 0}^{n-1} {2^k }$ just by using the result we obtained in (2)

But we have: $\displaystyle \sum\limits_{k = 0}^{n - 1} {2^k } = \sum\limits_{k = 0}^{n - 1} {\left[ {\underbrace {\left( {2 - 1} \right)}_{ = 1} \cdot 2^k } \right]} = \sum\limits_{k = 0}^{n - 1} {\left( {2^{k + 1} - 2^k } \right)} = 2^n - 1$ because we have a telescoping sum again.

Thus: $\displaystyle \sum\limits_{k = 1}^n {b_k } = b_1 \cdot \sum\limits_{k = 0}^{n - 1} {2^k } = b_1 \cdot \left( {2^n - 1} \right)$ (4)

Now mixing (3) and (4) we get:$\displaystyle a_n - a_0 = b_1 \cdot \left( {2^n - 1} \right) \Rightarrow a_n = \underbrace {b_1 }_{\left( {a_1 - a_0 } \right)} \cdot \left( {2^n - 1} \right) + a_0 =\left( {a_1 - a_0 } \right) \cdot \left( {2^n - 1} \right) + a_0$

Thus the solution is given by: $\displaystyle \boxed{a_n = a_0 + \left( {a_1 - a_0 } \right) \cdot \left( {2^n - 1} \right)}$

Set: $\displaystyle a_n=T(n+1)$ to get your answer.

Indeed we get: $\displaystyle T\left( n \right) = a_{n - 1} = a_0 + \left( {a_1 - a_0 } \right) \cdot \left( {2^{n - 1} - 1} \right) = T\left( 1 \right) + \left[ {T\left( 2 \right) - T\left( 1 \right)} \right] \cdot \left( {2^{n - 1} - 1} \right) =2^{n-1}$
• Jan 31st 2009, 11:33 AM
drthea
Quote:

Originally Posted by PaulRS
With all the details... - you should have said what exactly you didn't understand-

I am sorry for not pointing out what I didn't understand.
That was how you got
Quote:

Originally Posted by PaulRS
Let $\displaystyle a_n=T(n+1)-T(n)$

From your equation we find that: $\displaystyle T(n)-T(n-1)=2\cdot{\left(T(n-1)-T(n-2)\right)}$

from $\displaystyle T(n) = 3T(n - 1) - 2T(n - 2)$
For example, solving $\displaystyle T(n)=nT(n/2), T(0)=3/2$ the result is 3.
$\displaystyle T_n = 6T(n-1)-9T(n-2)+(n+1)3^n, T_1= {3/2} , T_2=27$