recurrence relations

**narbe** · October 8th 2008, 05:27 AM

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

**Soroban** · October 8th 2008, 07:27 AM

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?

**narbe** · October 8th 2008, 08:32 AM

yes I got the solution! but how can I demonstrate it as a function

??????

**Opalg** · October 8th 2008, 12:26 PM

Originally Posted by narbe

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.)

**Soroban** · October 8th 2008, 06:43 PM

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}$

**bkarpuz** · October 9th 2008, 11:33 AM

Originally Posted by narbe

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.

Thread: recurrence relations

LinkBack

Thread Tools

Display

recurrence relations

yeah but ...

Similar Math Help Forum Discussions

Recurrence Relations

Recurrence relations

Recurrence relations

recurrence relations - degree of the recurrence

recurrence relations

Search Tags