Second-Order Linear Recurrences

Date: 06/08/2001 at 11:51:25
From: Lanada M. Jones
Subject: Discrete Math/Recurrence relation

Hi, 

I was wondering if I could get help with the following problems:

1. Find a recurrence relation for the number of bit strings of 
   length n that do not contain a pair of consecutive zeroes. What are 
   the initial conditions?

2. Solve the following recurrence relations together with the inital 
   conditions given:
   a n = 4 a n-1 - 4 a n-2; a0 = 6 a1 = 8

   In other words, a sub n = 4 times a sub n minus 1  minus 4 times a 
   sub n minus 2; a sub zero equals six, a sub one equals eight.

3. Consider the sequence 0, 1, 1/2, 3/4, 5/8, 11/16, ..., in which 
   each term is the average of the previous two terms (eg., the next 
   term will be 1/2(5/8 + 11/16) = 21/32. Find the formula for the 
   general term using a recurrence equation. Make sure you state the 
   inital condition. Then give a formula for the general term using a 
   non-recursive equation by solving the above recurrence equation.

I would appreciate any help you can give to help me get started with 
these problems.

Date: 06/08/2001 at 13:08:00
From: Doctor Rob
Subject: Re: Discrete Math/Recurrence relation

Thanks for writing to Ask Dr. Math, Lanada.

Here are the steps to solving second-order linear recurrences.

1. Find the recurrence relations and initial conditions. In the
   first problem, it is given. In the second, you have to find it:

   a(n) = [a(n-1)+a(n-2)]/2, a(0) = 0, a(1) = 1.

2. Write it in the form

   a(n) + c(1)*a(n-1) + c(2)*a(n-2) = 0,

   where c(1) and c(2) are constants.

3. Write down the characteristic polynomial

   x^2 + c(1)*x + c(2).

4. Find the roots of this polynomial. They can be r(1) and r(2),
   distinct roots, or r(1), a double root.

5. Write down the general solution of the recurrence. In the case
   of distinct roots, that is

   a(n) = k(1)*r(1)^n + k(2)*r(2)^n.

   In the case of a double root, that is

   a(n) = [k(1)*n + k(2)]*r(1)^n.

Here k(1) and k(2) are two arbitrary constants.

6. Use the initial conditions to set up equations in the unknown
   constants k(1) and k(2).

7. Solve those simultaneous linear equations and find the values
   of k(1) and k(2).

8. Write the explicit solution of the recurrence satisfying the
   initial conditions.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 06/09/2001 at 05:19:01
From: Doctor Anthony
Subject: Re: Discrete Math/Recurrence relation

>1. Find a recurrence relation for the number of bit strings of 
    length n that do not contain a pair of consecutive zeroes. What 
    are the initial conditions?

Let u(n) be the number of strings of length n that DO NOT contain 
consecutive 0's. 

Let u(n0) = number of strings that start with 0
    u(n1) = number of strings that start with 1 

Then  u(n) = u(n0) + u(n1)

If the first number in the string is 1 then the string can be 
completed in  u(n-1) ways.  So u(n1) = u(n-1).

If the first number in the string is 0, then the second number must 
be 1.  So u(n0) = u((n-1)1) 
                = u(n-2)

Therefore  u(n) = u(n0) + u(n1)  becomes

           u(n) = u(n-2) + u(n-1)

Note that this is the recurrence relation for the number of strings 
that DO NOT have consecutive 0's.  

This is the familiar recurrence relation for the Fibonacci series. 
 

>2. Solve the following recurrence relations together with the inital 
    conditions given:
    a n = 4 a n-1 - 4 a n-2; a0 = 6 a1 = 8

   a(n) = 4.a(n-1) - 4.a(n-2)

   a(n) - 4.a(n-1) + 4.a(n-2) = 0

    The auxiliary equation is

       x^2 - 4x + 4 = 0

       (x-2)^2 = 0   With the double root the solution is

         a(n) = (A + B.n)2^n     

  a0 = 6,   a1 = 8  

     6 = A

     8 = (6 + B)2   so B+6 = 4   and  B = -2

Therefore   a(n) = (6 - 2n)2^n

>3. Consider the sequence 0, 1, 1/2, 3/4, 5/8, 11/16, ..., in which 
    each term is the average of the previous two terms (eg., the next 
    term will be 1/2(5/8 + 11/16) = 21/32. Find the formula for the 
    general term using a recurrence equation. Make sure you state the 
    inital condition. Then give a formula for the general term using a 
    non-recursive equation by solving the above recurrence equation.

   u(n) = (1/2)[u(n-1) + u(n-2)]

  2.u(n) - u(n-1) - u(n-2) = 0

  The auxiliary equation is

      2x^2 - x - 1 = 0

     (2x+1)(x-1) = 0    x=1   or  x = -1/2

So   u(n) = A + B(-1/2)^n

       0  = A + B   so A = -B

       1  = A - B/2
       1 = -B - B/2
       1 = -3B/2      therefore  B = -2/3  then  A = 2/3

      u(n) = 2/3 - (2/3)(-1/2)^n

check:   u(5) = (2/3)[1 - (-1/2)^5]

              = (2/3)[1 + 1/32]

              = (2/3)[33/32]

              =  11/16     which is correct.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/