# Finding characteristic equation of problem and solve recurrence relation

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,

-
I've corrected my answer look at that and let me know if it is useful to you. –  leo Sep 6 '11 at 23:44

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.
-
hey, Thanks for the answer I am struggling with point No.2 wouldn't it just be $e(n) = 4o(n-1)$? –  Jason Sep 5 '11 at 17:54
@Jason: yes, that's it exactly! (Note that expressing it in terms of just $o(n-1)$ is technically 'expressing it in terms of $e(n-1)$ and $o(n-1)$' - I didn't want to give away the trick there that it doesn't depend on $e(n-1)$ at all...) –  Steven Stadnicki Sep 5 '11 at 17:59
Oh ok cool :) i'll get back to trying to finish this in a moment –  Jason Sep 5 '11 at 18:33
So... $a(n) = 4(a(n-1))+16(a(n-2))$? –  Jason Sep 5 '11 at 18:42
That's the answer that I came up with, yes (although of course you're going to want to show the work behind this!). –  Steven Stadnicki Sep 5 '11 at 19:14

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

-
Hi, I wrote this question from a friends computer - I meant to say there can't be 2 even number adjacent like 2,6 –  Jason Sep 5 '11 at 16:18
ok @Jason, I'll fix it. –  leo Sep 5 '11 at 16:51
Try to break your $a(n-1)$ into cases. If it ends with an odd number, then you can freely append any of the 8 digits. If it ends with an even number, then you may only append the 4 odd digits. –  Austin Mohr Sep 5 '11 at 16:56
so $8\frac{a(n-1)}{2}+4\frac{a(n-1)}{2}$? –  Jason Sep 5 '11 at 17:06
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. –  Steven Stadnicki Sep 5 '11 at 17:09

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 .

-
I don't get why that is the recurrence relation if I can't have two consecutive even numbers not two consecutive equal numbers –  Jason Sep 5 '11 at 17:04
@Jason:Yes, the recurrence relation that I posted here is incorrect under your assumption. I'll correct it. –  leo Sep 5 '11 at 17:23