Results 1 to 6 of 6

Math Help - recurrence relations

  1. #1
    Banned
    Joined
    Sep 2008
    Posts
    21

    Question recurrence relations

    1)
    Find a recurrence relation for the number of bit string of length n that contain three consecutive 0's
    What are the initial conditions? how many bit strings of length 7 contain three consecutive 0's?

    2)
    Give the recursive algorithm for finding the minimum of a finite set of
    integers.

    3)
    Find the solution to the following recurrence relation and initial
    condition:
    xn+2 = 4xn; n = 0, 1, 2, ... x0 = 2, x1 = 1.

    4)
    Give the recursive algorithm for finding the sum of the first n odd
    positive integers.

    5)
    Find the solution to the following recurrence relation and initial
    condition:
    xn+2 = 2xn+1 + 3xn; n = 0, 1, 2, ... x0 = 1, x1 = -1.

    Thanks in advance
    Last edited by narbe; October 8th 2008 at 05:40 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,803
    Thanks
    693
    Hello, narbe!

    5) Find the solution to the following recurrence relation and initial condition:

    . . x_{n+2} \:= \:2x_{n+1} + 3x_n\qquad x_0 = 1,\;\;x_1 = \text{-}1
    Crank out the new few terms . . .

    . . \begin{array}{ccccc} x_2 &=&2(\text{-}1) + 3(1) &=& 1 \\<br />
x_3 &=& 2(1) + 3(\text{-}1) &=& \text{-}1 \\<br />
x_4 &=& 2(\text{-}1) + 3(1) &=& 1 \\<br />
x_5 &=& 2(1) + 3(\text{-}1) &=& \text{-}1 \\<br />
\vdots & & \vdots & & \vdots \end{array}

    Got it?

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2008
    Posts
    21

    yeah but ...

    yes I got the solution! but how can I demonstrate it as a function ??????
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by narbe View Post
    1)
    Find a recurrence relation for the number of bit string of length n that contain three consecutive 0's
    What are the initial conditions? how many bit strings of length 7 contain three consecutive 0's?
    I think it's easiest to count the number of strings of length n that do not contain three consecutive zeros. Call this number y_n.

    We can get a string of length n+1 without three consecutive zeros in three ways: (1) take such a string of length n and add a 1 at the end, (2) take such a string of length n-1 and add 10 at the end, (3) take such a string of length n-2 and add 100 at the end. Therefore y_{n+1} = y_n+y_{n-1}+y_{n-2}.

    Now let x_n denote the number of strings of length n that do contain three consecutive zeros. There are altogether 2^n strings of length n, so x_n = 2^n-y_n. It easily follows from the relation for the y's that x_{n+1} = x_n+x_{n-1}+x_{n-2}+2^{n-2}. The initial conditions are x_1=x_2=0,\ x_3=1. From there, you can use the recurrence relation to work your way up to 7. (I get the answer x_7=47, but don't rely on my arithmetic.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,803
    Thanks
    693
    Hello, narbe!

    It's easy . . .


    Look at the terms:

    . . \begin{array}{ccccc}x_0 &=& 1 \\ x_1 &=& \text{-}1 \\ x_2 &=& 1 \\ x_3 &=& \text{-}1 \\ \vdots \\ x_n &=& (\text{-}1)^n  & \Leftarrow &\text{There!}\end{array}

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2
    Quote Originally Posted by narbe View Post
    3) Find the solution to the following recurrence relation and initial
    condition:
    x_{n+2}= 4x_{n}; n = 0, 1, 2, ... x_{0} = 2, x_{1} = 1.
    This is a second order difference equation with a constant coefficient, there is a very simple way for this equation.
    Such equations have solution of the type x(n)=c_{1}\lambda_{1}^{n}+c_{2}\lambda_{2}^{n} for n\in\mathbb{N}, where c_{1},c_{2} are arbitrary constants.
    Just substitute this value into the solution and solve \lambda_{1} and \lambda_{2}, then use these values together with the initial conditions to find the desired solution.

    However, here, I would like to show you a different solution way for this equation.
    First set, y(n):=x(2n) for n\in\mathbb{N}, then from the equation, we get
    y(n+1)=x(2n+2)=4x(2n)=4y(n) or simply y(n+1)=4y(n) for n\in\mathbb{N}.
    It is easy to solve this equation and we get y(n)=c_{1}4^{n} for all n\in\mathbb{N}, where c_{1} is an arbitrary constant.
    Since y(0)=x(0)=2, we see that c_{1}=2.
    Thus, we have x(n)=24^{n/2}=2^{n+1} is a solution of the equation.

    Next, set z(n):=x(2n-1) for n\in\mathbb{N} and solve z(n+1)=x(2(n+1)-1)=x(2n+1)=4x(2n-1)=z(n) or simply z(n+1)=4z(n) for n\in\mathbb{N} with z(1)=x(1)=1.

    Finally, sum these results.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 28th 2011, 02:50 PM
  2. Recurrence relations
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 24th 2011, 09:45 AM
  3. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 1st 2010, 06:59 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: 3
    Last Post: February 10th 2008, 11:57 PM

Search Tags


/mathhelpforum @mathhelpforum