Results 1 to 12 of 12

Math Help - Recurrence relation

  1. #1
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17

    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:

     T(n) = 3T(n - 1) - 2T(n - 2), T(1)=1, T(2)=2

    and the solution is as follows:

    T(n) = 3T(n - 1) - 2T(n - 2)<br />
= 7T(n - 2) - 6T(n - 3)<br />
= 15T(n - 3) - 14T(n - 4)

    so  T(n)=(2^k -1)T(n-k-1)-(2^k -2)T(n-k)

    I don't get how it goes from T(n) = 3T(n - 1) - 2T(n - 2)
    to 7T(n - 2) - 6T(n - 3),
    could you explain please?
    Also why T(1)=1, T(2)=2 are given? Where should I use them?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17
    Actually I found out how to do it

    <br />
\begin{array}{rcl} <br />
T(n) = (3T(n - 1) - 2T(n - 2) \\<br />
 =  3( 3T(n - 2) - 2T(n - 3)) - 2T(n - 2) \\  <br />
= 9T(n - 2) - 6T(n - 3) - 2T(n - 2) \\<br />
= 7T(n - 2) - 6T(n - 3) \end{array}<br />

    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?
    Last edited by drthea; January 30th 2009 at 08:47 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2009
    From
    Australia
    Posts
    59
    Quote Originally Posted by drthea View Post
    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...

    <br />
\begin{array}{rcl}<br />
e^{in\theta} & = & \left(\cos\theta + i \sin\theta\right)^n \\<br />
 & = & \cos n\theta + i \sin n\theta<br />
\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}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Let a_n=T(n+1)-T(n)

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

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

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

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

    Hence: T(n)=T(0)+\left[T(1)-T(0)\right]\cdot(2^n -1)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Jester's Avatar
    Joined
    Dec 2008
    From
    Conway AR
    Posts
    2,367
    Thanks
    42
    Quote Originally Posted by drthea View Post
    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:

     T(n) = 3T(n - 1) - 2T(n - 2), T(1)=1, T(2)=2

    and the solution is as follows:

    T(n) = 3T(n - 1) - 2T(n - 2)<br />
= 7T(n - 2) - 6T(n - 3)<br />
= 15T(n - 3) - 14T(n - 4)

    so  T(n)=(2^k -1)T(n-k-1)-(2^k -2)T(n-k)

    I don't get how it goes from T(n) = 3T(n - 1) - 2T(n - 2)
    to 7T(n - 2) - 6T(n - 3),
    could you explain please?
    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

    T(n) = c \rho^n

    so substituting into

    T(n)-3T(n-1)+2T(n-2) =0

    gives

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

    or

    \rho = 1,\;\;\; \rho = 2

    Then general solution of the difference equation is

    T(n) = c_1 1^n + c_2 2^n = c_1 + c_2 2^n

    Now use your conditions

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

    to find the constants. Your final answer T(n) = 2^{n-1}.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17
    Hello and thank you for your answers.
    @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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Jester's Avatar
    Joined
    Dec 2008
    From
    Conway AR
    Posts
    2,367
    Thanks
    42
    Quote Originally Posted by drthea View Post
    Hello and thank you for your answers.
    @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
    What do you mean by repeated substitution? Do you mean substituting the form

    T(n) = c \rho^n into the difference equation?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17
    Quote Originally Posted by danny arrigo View Post
    What do you mean by repeated substitution? Do you mean substituting the form

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Jester's Avatar
    Joined
    Dec 2008
    From
    Conway AR
    Posts
    2,367
    Thanks
    42
    Quote Originally Posted by drthea View Post
    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.

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

    Your method:
    T(n) = 2 T(n-1) = 2 \cdot 2 \,T(n-2) = 2^3 \,T(n-3) = \cdots = 2^k \,T(n-k)

    Set k = n so

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

    My method:

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

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

    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    With all the details... - you should have said what exactly you didn't understand-

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

    That is equivalent to: 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: b_{n}=a_{n}-a_{n-1} since (1) translates into: b_{n}=2b_{n-1}

    Which can be solved iterating like this: 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: <br />
\sum\limits_{k = 1}^n {b_k } <br />
?

    Well, on the one hand we can say that: <br />
\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 <br />
just by using the definition of b_n and noticing that the sum is telescoping. (3)

    On the other hand: <br />
\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 } <br />
just by using the result we obtained in (2)

    But we have: <br />
\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<br />
because we have a telescoping sum again.

    Thus: <br />
\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)<br />
(4)

    Now mixing (3) and (4) we get: <br />
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 <br />

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

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

    Indeed we get: <br />
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}<br />
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17
    Quote Originally Posted by PaulRS View Post
    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 View Post
    Let a_n=T(n+1)-T(n)

    From your equation we find that: T(n)-T(n-1)=2\cdot{\left(T(n-1)-T(n-2)\right)}
    from  T(n) = 3T(n - 1) - 2T(n - 2)
    But I really understand it now. Sorry for not being clear about this and thanks again.


    Edit: (to prevent double posting)
    What can we say about the closed form of a reccurence when the result is an integer?
    For example, solving T(n)=nT(n/2), T(0)=3/2 the result is 3.
    Last edited by drthea; February 9th 2009 at 02:50 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17
    How could we solve this type of reccurence?
     T_n = 6T(n-1)-9T(n-2)+(n+1)3^n, T_1= {3/2} , T_2=27
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 15th 2011, 11:27 PM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 02:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 01:18 PM
  4. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 06:20 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 08:02 AM

Search Tags


/mathhelpforum @mathhelpforum