# recurrence relations

• Oct 8th 2008, 05:27 AM
narbe
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.

• Oct 8th 2008, 07:27 AM
Soroban
Hello, narbe!

Quote:

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

. . $\displaystyle x_{n+2} \:= \:2x_{n+1} + 3x_n\qquad x_0 = 1,\;\;x_1 = \text{-}1$

Crank out the new few terms . . .

. . $\displaystyle \begin{array}{ccccc} x_2 &=&2(\text{-}1) + 3(1) &=& 1 \\ x_3 &=& 2(1) + 3(\text{-}1) &=& \text{-}1 \\ x_4 &=& 2(\text{-}1) + 3(1) &=& 1 \\ x_5 &=& 2(1) + 3(\text{-}1) &=& \text{-}1 \\ \vdots & & \vdots & & \vdots \end{array}$

Got it?

• Oct 8th 2008, 08:32 AM
narbe
yeah but ...
yes I got the solution! but how can I demonstrate it as a function (Speechless)??????
• Oct 8th 2008, 12:26 PM
Opalg
Quote:

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 $\displaystyle 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 $\displaystyle y_{n+1} = y_n+y_{n-1}+y_{n-2}$.

Now let $\displaystyle x_n$ denote the number of strings of length n that do contain three consecutive zeros. There are altogether $\displaystyle 2^n$ strings of length n, so $\displaystyle x_n = 2^n-y_n$. It easily follows from the relation for the y's that $\displaystyle x_{n+1} = x_n+x_{n-1}+x_{n-2}+2^{n-2}$. The initial conditions are $\displaystyle 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 $\displaystyle x_7=47$, but don't rely on my arithmetic.)
• Oct 8th 2008, 06:43 PM
Soroban
Hello, narbe!

It's easy . . .

Look at the terms:

. . $\displaystyle \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}$

• Oct 9th 2008, 11:33 AM
bkarpuz
Quote:

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 $\displaystyle x(n)=c_{1}\lambda_{1}^{n}+c_{2}\lambda_{2}^{n}$ for $\displaystyle n\in\mathbb{N}$, where $\displaystyle c_{1},c_{2}$ are arbitrary constants.
Just substitute this value into the solution and solve $\displaystyle \lambda_{1}$ and $\displaystyle \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, $\displaystyle y(n):=x(2n)$ for $\displaystyle n\in\mathbb{N}$, then from the equation, we get
$\displaystyle y(n+1)=x(2n+2)=4x(2n)=4y(n)$ or simply $\displaystyle y(n+1)=4y(n)$ for $\displaystyle n\in\mathbb{N}$.
It is easy to solve this equation and we get $\displaystyle y(n)=c_{1}4^{n}$ for all $\displaystyle n\in\mathbb{N}$, where $\displaystyle c_{1}$ is an arbitrary constant.
Since $\displaystyle y(0)=x(0)=2$, we see that $\displaystyle c_{1}=2$.
Thus, we have $\displaystyle x(n)=24^{n/2}=2^{n+1}$ is a solution of the equation.

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

Finally, sum these results.