Results 1 to 7 of 7
Like Tree3Thanks
  • 1 Post By SlipEternal
  • 1 Post By romsek
  • 1 Post By SlipEternal

Math Help - Recurrence Relations

  1. #1
    Member Henderson's Avatar
    Joined
    Dec 2007
    Posts
    127
    Thanks
    2

    Recurrence Relations

    It's been a while since I stopped by, but when I get 100% stumped I know to turn here. Hoping someone can point me down the right path with this, not only with a solution, but suggestions on reading material (on or offline) to help me learn this content.


    Find the solution of the recurrence relation u_{n} = 2u_{n-1} - 2u_{n-2}, n \geq 2, where u_{0} = 2, u_{1} = 2. Express your solution in the form 2^{f(n)} \cos (g(n)\pi), where the functions f and g map the non-negative integers onto the reals.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,653
    Thanks
    1063

    Re: Recurrence Relations

    Quote Originally Posted by Henderson View Post
    It's been a while since I stopped by, but when I get 100% stumped I know to turn here. Hoping someone can point me down the right path with this, not only with a solution, but suggestions on reading material (on or offline) to help me learn this content.


    Find the solution of the recurrence relation u_{n} = 2u_{n-1} - 2u_{n-2}, n \geq 2, where u_{0} = 2, u_{1} = 2. Express your solution in the form 2^{f(n)} \cos (g(n)\pi), where the functions f and g map the non-negative integers onto the reals.
    well I solved the thing for you but I don't know that it's going to help you understand general recurrence relations any.

    You should be able to put the relation into excel or something and get the sequence it produces.

    Doing this I just just determined f and g by inspection.

    Are you able to generate the sequence from the recurrence relation?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,930
    Thanks
    782

    Re: Recurrence Relations

    I would recommend checking out Method 4 from this website: Wikihow: Solve Recurrence Relations

    Method 4 involves solving Linear Recurrences. It suggests the recurrence relation is closely tied to the polynomial x^2-2x+2, called the "characteristic polynomial" of the recurrence relation. Solving the characteristic polynomial gives x = 1\pm i. Then u_n = c_1(1+i)^n + c_2(1-i)^n. Plugging in, u_0 = 2 = c_1(1+i)^0 + c_2(1-i)^0 and u_1 = 2 = c_1(1+i)^1+c_2(1-i)^1 you have c_1+c_2 = 2 and (c_1+c_2)+(c_1-c_2)i = 2. This gives c_1 +c_2 = 2 and c_1-c_2 = 0, so c_1=c_2 = 1.

    So, you have u_n = (1+i)^n + (1-i)^n. In polar notation, you can rewrite this as u_n = (\sqrt{2}e^{i\pi/4})^n+(\sqrt{2}e^{-i\pi/4})^n. Then using Euler's Formula, you have:

    u_n = 2^{n/2}(\cos(n\pi/4)+i\sin(n\pi/4)+\cos(n\pi/4)-i\sin(n\pi/4)) = 2^{n/2}(2\cos(n\pi/4))

    This gives f(n) = 2g(n)+1 and g(n) = \dfrac{n}{4}.

    I am not sure if this method is what you had in mind, but it is the simplest method I know.
    Last edited by SlipEternal; May 19th 2014 at 06:46 AM.
    Thanks from romsek
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Henderson's Avatar
    Joined
    Dec 2007
    Posts
    127
    Thanks
    2

    Re: Recurrence Relations

    Thank you- that is the path I have taken, and finding the roots using the characteristic equation has been something we have practiced in class. I had found the roots of 1+i and 1-i, and the coefficients of c_{1} = c_{2} = 1, but stopped there, because when I check my working up to that point, I get different values than the sequence gives me.

    For example, when n=7:
    u_{7} = 176

    The sequence I've made to get there is
    u_{n}: (2, 2, 0, 4, -8, 24, -64, 176)

    But 1 (1 + i) ^7 + 1 (1 - i) ^7
    = (8 - 8i) + (8 + 8i)
    =16

    Any thoughts?
    Last edited by Henderson; May 19th 2014 at 08:34 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,653
    Thanks
    1063

    Re: Recurrence Relations

    Quote Originally Posted by Henderson View Post
    Thank you- that is the path I have taken, and finding the roots using the characteristic equation has been something we have practiced in class. I had found the roots of 1+i and 1-i, and the coefficients of c_{1} = c_{2} = 1, but stopped there, because when I check my working up to that point, I get different values than the sequence gives me.

    For example, when n=7:
    u_{7} = 176

    The sequence I've made to get there is
    u_{n}: (2, 2, 0, 4, -8, 24, -64, 176)

    But 1 (1 + i) ^7 + 1 (1 - i) ^7
    = (8 - 8i) + (8 + 8i)
    =16

    Any thoughts?
    24 is incorrect. 16 is the correct value for $u_7$

    Recurrence Relations-clipboard02.jpg
    Last edited by romsek; May 19th 2014 at 08:45 AM.
    Thanks from Henderson
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,930
    Thanks
    782

    Re: Recurrence Relations

    The correct sequence for u_n is \begin{matrix}n & u_n \\ 0 & 2 \\ 1 & 2 \\ 2 & 0 \\ 3 & -4 \\ 4 & -8 \\ 5 & -8 \\ 6 & 0 \\ 7 & 16 \\ 8 & 32\end{matrix}

    So, you calculated several of the terms incorrectly.
    Thanks from Henderson
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member Henderson's Avatar
    Joined
    Dec 2007
    Posts
    127
    Thanks
    2

    Re: Recurrence Relations

    Oh, honestly. So characteristic equations and complex numbers, I can do, but subtracting 0-4 and getting positive 4 will keep me stuck on a problem for hours.

    Never mind. Thanks, all!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 2nd 2012, 10:50 PM
  2. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 1st 2010, 06:59 AM
  3. recurrence relations
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: January 11th 2010, 03:52 AM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 9th 2008, 11:33 AM

Search Tags


/mathhelpforum @mathhelpforum