Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

up vote 0 down vote accepted

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

share|improve this answer
    
Thanks, this was really useful to know. –  wvxvw Jun 30 '12 at 16:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.