-1
$\begingroup$

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

  • 0
    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.2012-06-30

1 Answers 1

3

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)\;.$

  • 0
    Thanks, this was really use$f$ul to know.2012-06-30