1
$\begingroup$

I have a homework assignment to find the characteristic equation of the set which a(n) = the number of sequences of length n which can be build from ${1,2,3...8}$ but you can't have two even numbers adjacent to each other, for example (1,2,2,3) is not legal.

I came up with the recurrence $a(n) = 8a(n-1) -16$ which I hope is correct.

But how can I find the characteristic equation of this recurrence and then use it to solve the recurrence?

P.S.
I don't know Taylor series and we have not learned it yet so the solution should not include it ( I saw some solutions on the Internet using it)

Thanks,

  • 0
    I've corrected my answer look at that and let me know if it is useful to you.2011-09-06

3 Answers 3

3

As @Austin pointed out in comments, the correct solution comes down to a case-by-case analysis. To make things a little bit easier, we'll let $o(n)$ be the number of suitable sequences of length $n$ ending with an odd number, and $e(n)$ be the number of suitable sequences of length $n$ ending with an even number. Obviously $a(n) = o(n)+e(n)$; also, of course, if a sequence is suitable (has no two even numbers adjacent), then any subsequence is also suitable - this is the key point that lets us write our formulas for suitable sequences of length $n$ in terms of the sequences of length $n-1$.

  1. If the last term of a sequence is odd, the rest of the terms can be anything; how does this let you express $o(n)$ in terms of $a(n-1)$?
  2. If the last term of a sequence is even, what does this say about the last term of the rest of the sequence (the $n-1$st term)? How does this let you express $e(n)$ in terms of $o(n-1)$ and $e(n-1)$?
  3. Can you use what you used in (1) (and your base knowledge that $a(n)=o(n)+e(n)$) to rewrite the formula you found in (2) and express $e(n)$ in terms of only the sequence $a$?
  4. Finally, add the formulas from (1) and (3) together; this should give you your expression for $a(n)$. Once you have this, if you need more help with the characteristic equation, I'd suggest either editing your question to reflect the updated knowledge or asking a new one to cover that specific part of the Q.
  • 0
    @Jason: do you want to find the characteristic equation or solve the recurrence relation?2011-09-07
1

Remark: I read the question incorrectly. This post enumerates the number of sequences in which no two consecutive entries are the same.

If you have a valid sequence of length $n-1$, how can you add a number to the end to extend it to a valid sequence of length $n$?

Since the smaller sequence is assumed to be valid, you know illegal configurations in it (i.e. no consecutive entries with the same number). All that's left is to add an element to the end. We have 7 choices for this, since we cannot choose whatever number is on the end of the shorter sequence. So, we get the recursion $ a(n) = 7a(n-1), $ with initial condition $a(1) = 8$.

Think about the first few terms of $a(n)$: 8, $8 \cdot 7$, $8 \cdot 7^2$, $8 \cdot 7^3$, $\dots$.

From this, we can conclude that $ a(n) = 8 \cdot 7^{n-1}. $

  • 0
    Jason: that doesn't work because you can't assume that the number of sequences which end with an even number and the number which end with an odd number are the same - in fact, the latter will always be greater than the former.2011-09-05
1

To begin with, the recurrence relation that you give is incorrect. Now, consider a valid string of length $n$: $b_1b_2\ldots b_{n-1}b_n.$

There are two cases:

If $b_n$ is odd: then any legal string $b_1b_2\ldots b_{n-1}$ can precede $b_n$. Since There are $a(n-1)$ of these strings the amount of valid strings of length $n$ with $b_n$ odd is $a(n-1)\cdot 4$.

If $b_n$ is even: then $b_{n-1}$ is odd and $b_n$ is even. Any legal string of length $n-2$ can precede $b_{n-1}b_n$. Since there are $a(n-2)$ of this these strings, the number of valid strings with length $n$ with the last digit even is $a(n-2)\cdot 4\cdot 4$.

Since the total amount of valid strings of length $n$ is the sum of the two quantities above, we get $a(n)=4a(n-1)+16a(n-2).$ For the initial conditions note that $a(1)=8$ and $a(2)=48$.

Secondly, given a recurrence relation $ a(n+k)+c_1a(n+k-1)+\ldots+c_ka(n)=f(n),\; k>1 $ of order $k$, with $c_i$ constants, you can find the characteristic equation of the associated homogeneous recurrence relation: $a(n+k)+c_1a(n+k-1)+\ldots+c_ka(n)=0,$ namely $x^{k}+\sum_{i=1}^k c_ix^{k-i}=0.$

This can be useful to you http://applied-discrete-structures.wiki.uml.edu/Chapter+8 .

  • 0
    @Jason:Yes, the recurrence relation that I posted here is incorrect under your assumption. I'll correct it.2011-09-05