# Recurrence relation, error in generating function - where did I go wrong?

This is the homework. If you are interested in precise formulation, it is as follows: write a recurrence relation and a generating function that would generate a sequence of trites (elements of a set $\{0, 1, 2\}$), where subsequences of 01 and 00 are not allowed.

I've recognized this as being the following recurrence relation: $f(n) = 2f(n - 1) + f(n - 2)$. I've built a model of it and tested, it looks like this is correct. Now, below is my effort at writing a generating function, which does not give me the expected result, but I cannot find the error.

\begin{align*} a_n = 2a_{n-1} + a_{n-2}\\ s^2 = 2s + 1\\ s^2 - 2s - 1 = 0\\ \end{align*}

\begin{align*} s = \frac{ 2 \pm \sqrt{ 4 + 4 } } { 2 }\\ s_0 = \frac{ 2 + 2 \sqrt{ 2 } } { 2 } = 1 + \sqrt{ 2 }\\ s_1 = \frac{ 2 - 2 \sqrt{ 2 } } { 2 } = 1 - \sqrt{ 2 }\\ \end{align*}

\begin{align*} a_n = \alpha s_0^n + \beta s_1^n\\ a_0 = \alpha + \beta = 1\\ a_1 = (1 + \sqrt{ 2 }) \alpha + (1 - \sqrt{ 2 }) \beta = 3\\ \alpha = 1 - \beta\\ (1 + \sqrt{ 2 }) (1 - \beta) + (1 - \sqrt{ 2 }) \beta = 3\\ (1 + \sqrt{ 2 }) - (1 + \sqrt{ 2 }) \beta + (1 - \sqrt{ 2 }) \beta = 3\\ \beta ((1 - \sqrt{ 2 }) - (1 + \sqrt{ 2 })) = 3 - (1 + \sqrt{ 2 })\\ \beta = \frac{ 3 - (1 + \sqrt{ 2 }) } { (1 - \sqrt{ 2 }) - (1 + \sqrt{ 2 }) }\\ \beta = \frac{ 3 - (1 + \sqrt{ 2 }) } { 1 - \sqrt{ 2 } - 1 - \sqrt{ 2 } }\\ \beta = \frac{ 2 - \sqrt{ 2 } } { -2 \sqrt{ 2 } }\\ \alpha = 1 - \frac{ 2 - \sqrt{ 2 } } { -2 \sqrt{ 2 } }\\ \alpha = \frac{ -2 \sqrt{ 2 } - 2 - \sqrt{ 2 } } { -2 \sqrt{ 2 } }\\ \alpha = \frac{ -3 \sqrt{ 2 } - 2 } { -2 \sqrt{ 2 } }\\ \end{align*}

\begin{align*} a_n = \frac{ -3 \sqrt{ 2 } - 2 } { -2 \sqrt{ 2 } } \times (1 + \sqrt{ 2 }) + \frac{ 2 - \sqrt{ 2 } } { -2 \sqrt{ 2 } } \times (1 - \sqrt{ 2 })\\ a_n = \frac{ (-3 \sqrt{ 2 } - 2)(1 + \sqrt{ 2 })^n + (2 - \sqrt{ 2 })(1 - \sqrt{ 2 })^n }{ -2 \sqrt{ 2 } }\\ a_n = \frac{ (-3 \sqrt{ 2 } - \sqrt{ 2 } \sqrt{ 2 })(1 + \sqrt{ 2 })^n + (\sqrt{ 2 } \sqrt{ 2 } - \sqrt{ 2 })(1 - \sqrt{ 2 })^n } { -2 \sqrt{ 2 } }\\ a_n = \frac{ \sqrt{ 2 } (-3 - \sqrt{ 2 })(1 + \sqrt{ 2 })^n + \sqrt{ 2 } (\sqrt{ 2 } - 1)(1 - \sqrt{ 2 })^n } { -2 \sqrt{ 2 } }\\ a_n = \frac{ \sqrt{ 2 } ((-3 - \sqrt{ 2 })(1 + \sqrt{ 2 })^n + (\sqrt{ 2 } - 1)(1 - \sqrt{ 2 })^n) } { -2 \sqrt{ 2 } }\\ a_n = \frac{ (-3 - \sqrt{ 2 })(1 + \sqrt{ 2 })^n + (\sqrt{ 2 } - 1)(1 - \sqrt{ 2 })^n } { -2 } \end{align*}

Sorry, my TeX-fu isn't strong enough to make this look good. Feel free to edit it to make ti look more comprehensible.

You may find the model to test my calculations here: http://pastebin.com/R1aRmeL7

-
A generating function is a function $a_0+a_1x+a_2x^2+\dots$. You don't seem to be heading in the direction of a generating function at all; rather, you are finding a formula for $a_n$, which is a different question. – Gerry Myerson Jun 30 '12 at 11:05
There is a sign error in the lign where you express $\alpha$ as a single fraction (with denominator $-2\sqrt2$). As a result, the term $-3\sqrt2$ in the numerator should read $-\sqrt2$. – Did Jun 30 '12 at 11:07
@GerryMyerson sorry, I'm translating the task from another language, that was a mistranslation on my side. Then I don't need the generating function but (... that other thing) which given $n$ returns the number of sequences of length $n$ it is possible to generate while not solving for $n-1, n-2, ... n-(n-1), 0$. – wvxvw Jun 30 '12 at 11:33
@did Oh, ok... thanks! – wvxvw Jun 30 '12 at 11:34
You seem to like minus signs, I don't. Example: $\alpha = 1 - \frac{ 2 - \sqrt{ 2 } } { -2 \sqrt{ 2 } }$ and the line that follows. It is better to automatically convert to $\alpha = 1 + \frac{ 2 - \sqrt{ 2 } } {2 \sqrt{ 2 } }$. Also, solving the system of linear equations by substitution is less structured than elimination. – André Nicolas Jun 30 '12 at 14:01

You could have made things a little easier for yourself after you found $s_0=1+\sqrt2$ and $s_1=1-\sqrt2$, starting with finding $\alpha$ and $\beta$. You have $\alpha+\beta=1$ and $(1+\sqrt2)\alpha+(1-\sqrt2)\beta=3$. The latter can be written $(\alpha+\beta)+\sqrt2(\alpha-\beta)=3$, and since $\alpha+\beta=1$, this simplifies immediately to give you the system
\left\{\begin{align*} &\alpha+\beta=1\\ &\alpha-\beta=\sqrt2\;. \end{align*}\right.
Clearly $2\alpha=1+\sqrt2=s_0$ and $2\beta=1-\sqrt2=s_1$, so the general term is $$a_n=\frac12\left(s_0^{n+1}+s_1^{n+1}\right)\;,$$ or, if you prefer,
$$a_n=\frac12\left((1+\sqrt2)^{n+1}+(1-\sqrt2)^{n+1}\right)\;.$$