Associated Topics || Dr. Math Home || Search Dr. Math

### Second-Order Linear Recurrences

```
Date: 06/08/2001 at 11:51:25
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

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.

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/
```
Associated Topics:
College Number Theory
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search