# Math Help - recurrence relations

1. ## 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.

2. 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 \\
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?

3. ## yeah but ...

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

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

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

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