I haven't written in way too long and just wanted to post this fun little proof.
Assertion: Let \(F_n\) be the \(n\)th Fibonacci number defined by \(F_n = F_{n-1} + F_{n-2}\), \(F_0 = 0, F_1 = 1\). Show that for an odd prime \(p\neq 5\), we have \(p\) divides \(F_{p^2−1}\).
Proof: We do this by working inside \(\mathbb{F}_p\) instead of working in \(\mathbb{R}\). The recurrence is given by
\[ \left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array} \right)
\left( \begin{array}{c}
F_{n-1} \\
F_{n-2} \end{array} \right)
=
\left( \begin{array}{c}
F_{n-1} + F_{n-2} \\
F_{n-1} \end{array} \right)
=
\left( \begin{array}{c}
F_n \\
F_{n-1} \end{array} \right)\]
and in general
\[ \left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array} \right)^{n}
\left( \begin{array}{c}
1 \\
0 \end{array} \right)
=
\left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array} \right)^{n}
\left( \begin{array}{c}
F_1 \\
F_0 \end{array} \right)
=
\left( \begin{array}{c}
F_{n + 1} \\
F_n \end{array} \right)\]
The matrix \(A = \left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)\) has characteristic polynomial
\[\chi_A(t) = (1 - t)(0 - t) - (1)(1) = t^2 - t - 1\]
If this polynomial has distinct roots, then \(A\) is diagonalizable (this is sufficient, but not necessary). Assuming the converse we have \(\chi_A(t) = (t - \alpha)^2\) for some \(\alpha \in \mathbb{F}_p\); we can assume \(\alpha \in \mathbb{F}_p\) since \(-2\alpha = -1\) is the coefficient of \(t\), which means \(\alpha = 2^{-1} \) (we are fine with this since \(p\) odd means that \(2^{-1}\) exists). In order for this to be a root of \(\chi_A\), we must have
\[0 \equiv 4 \cdot \chi_A\left(2^{-1}\right) \equiv 4 \cdot \left(2^{-2} - 2^{-1} - 1\right) \equiv 1 - 2 - 4 \equiv -5 \bmod{p}.\]
Since \(p \neq 5\) is prime, this is not possible, hence we reached a contradiction and \(\chi_A\) does not have a repeated root.
Thus we may write \(\chi_A(t) = (t - \alpha)(t - \beta)\) for \(\alpha, \beta \in \mathbb{F}_{p^2}\) (it's possible that \(\chi_A\) is irreducible over \(\mathbb{F}_p\), but due to degree considerations it must split completely over \(\mathbb{F}_{p^2}\)). Using this, we may write
\[A = P \left(\begin{array}{cc} \alpha & 0 \\ 0 & \beta \end{array} \right) P^{-1}\]
for some \(P \in GL_{2} \left(\mathbb{F}_{p^2}\right)\) and so
\[A^{p^2 - 1} = P \left(\begin{array}{cc} \alpha & 0 \\ 0 & \beta \end{array} \right)^{p^2 - 1} P^{-1}
= P \left(\begin{array}{cc} \alpha^{p^2 - 1} & 0 \\ 0 & \beta^{p^2 - 1} \end{array} \right)P^{-1}\]
Since \(\chi_A(0) = 0 - 0 - 1 \neq 0\) we know \(\alpha\) and \(\beta\) are nonzero, hence \(\alpha^{p^2 - 1} = \beta^{p^2 - 1} = 1 \in \mathbb{F}_{p^2} \). Thus \(A^{p^2 - 1} = P I_2 P^{-1} = I_2\) and so
\[\left( \begin{array}{c}
F_p \\
F_{p^2 - 1} \end{array} \right)
=
\left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array} \right)^{p^2 - 1}
\left( \begin{array}{c}
1 \\
0 \end{array} \right)
=
I_2 \left( \begin{array}{c}
1 \\
0 \end{array} \right)
=
\left( \begin{array}{c}
1 \\
0 \end{array} \right)\]
so we have \(F_{p^2 - 1} = 0\) in \(\mathbb{F}_p\) as desired.
Showing posts with label Algebra. Show all posts
Showing posts with label Algebra. Show all posts
Sunday, August 18, 2013
Tuesday, August 23, 2011
Conway's Topograph Part 3
This is the third (continued from Part 2) in a series of three blog posts. In the following we'll investigate a few properties of an object called Conway’s topograph. John Conway conjured up a way to understand a binary quadratic form – a very important algebraic object – in a geometric context. This is by no means original work, just my interpretation of some key points from his The Sensual (Quadratic) Form that I'll need for some other posts.
Definition: For the form \(f(x, y) = a x^2 + h x y + b y^2\), we define the discriminant as the value \(ab - \left(\frac{1}{2}h\right)^2\). \(\Box\)
The base \((1, 0)\) and \((0, 1)\) take values \(a\) and \(b\) on the form in the Definition above and are part of a sequence with common difference \(h\). In fact, if we know the values \(a'\), \(b'\) and the difference \(h'\) at any base (edge in the topograph), the value \(a'b' - \left(\frac{1}{2}h'\right)^2\) is independent of the base and the direction (left or right) which determines the sign of \(h'\) and hence equal to the discriminant. To see this, first note the sign of \(h'\) is immaterial since it is squared. Also, consider the two other bases (edges) in the superbase. As in the proof of the climbing lemma, one base takes values \(a' = a\) and \(b' = a + b + h\) with common difference \(h' = 2a + h\) which gives
\begin{align*}
a'b' - \left(\frac{1}{2}h'\right)^2 &= a(a + b + h) - \frac{1}{4}\left(2a + h\right)^2 \\
&= a^2 + a b + a h - \left(a^2 + a h + \frac{1}{4} h^2\right) \\
&= ab - \left(\frac{1}{2}h\right)^2.
\end{align*}
Similarly the other base in the given superbase gives
\begin{align*}
a'b' - \left(\frac{1}{2}h'\right)^2 &= (a + b + h)b - \frac{1}{4}\left(2b + h\right)^2 \\
&= b^2 + a b + b h - \left(b^2 + b h + \frac{1}{4} h^2\right) \\
&= ab - \left(\frac{1}{2}h\right)^2.
\end{align*}
Having showed that there are no cycles when starting from a given superbase, our work in understanding the topograph is not complete. We haven't actually showed that we can get from one superbase to any other superbases within the topograph. To show this, we'll use the discriminant and the following.
Definition: A superbase \(W\) is called a well if all the edges at \(W\) point away from \(W\).
\(\Box\)
Notice a well is dependent on the values, hence depends on the form \(f\). In a positive--valued topograph, we may find a well by traveling along the topograph in the opposite direction of the edges. Eventually, we must encounter a superbase where all arrows point out (as above), leaving us nowhere to travel and thus becoming our well. This is because, assuming the topograph is positive--valued, we can only decrease in value for so long (eventually the values must approach the minimum).
Lemma: (The Well Lemma) For a positive--valued form \(f\) and a well (with respect to \(f\)) \(W\), the three values \(f\) takes on the faces in \(W\) are the smallest values that \(f\) takes on the topograph.
Proof: Using the labels from the well in the definition above, the Arithmetic Progression Rule for our differences gives
\[2\alpha = b + c - a, \quad 2\beta = c + a - b, \quad 2\gamma = a + b - c\]
and solving,
\[a = \beta + \gamma, \quad b = \alpha + \gamma, \quad c = \beta + \alpha.\]
Let the superbase \(W = \left\{e_1, e_2, e_3\right\}\). Since \(W\) is a superbase, we may write any vector as
\[v = m_1 e_1 + m_2 e_2 + m_3 e_3\]
for \(m_1\), \(m_2\), \(m_3 \in \mathbf{Z}\). Also due to the fact that \(W\) is a superbase, \(e_1 + e_2 + e_3 = (0, 0)\) and so we may also write
\[v = (m_1 - k) e_1 + (m_2 - k) e_2 + (m_3 - k) e_3\]
for \(k \in \mathbf{Z}\). From this it is clear only the differences of the \(m_i\) matter. With this as our inspiration we write
\[f(v) = \alpha(m_2 - m_3)^2 + \beta(m_1 - m_3)^2 + \gamma(m_1 - m_2)^2,\]
a formula discovered by Selling.
To verify this, notice both sides of the equation are quadratic forms in \(v\) and
\begin{align*}
f(e_1) = a &= \beta + \gamma = \alpha \cdot 0^2 + \beta \cdot 1^2 + \gamma \cdot 1^2 \\
f(e_2) = b &= \alpha + \gamma = \alpha \cdot 1^2 + \beta \cdot 0^2 + \gamma \cdot (-1)^2 \\
f(e_3) = c &= \beta + \alpha = \alpha \cdot (-1)^2 + \beta \cdot (-1)^2 + \gamma \cdot 0^2.
\end{align*}
hence they must be equal since both sides are quadratics that agree on more than two points.
If two of the \(m_i\) are equal, then \(v\) must be an integral multiple of the third vector, hence the value \(f(v)\) will be at least as large as the value of \(f\) on the third vector. If not, all the differences must be non--zero (hence greater than or equal to \(1\) in absolute value, since integers), thus
\[f(v) \geq \alpha \cdot 1^2 + \beta \cdot 1^2 + \gamma \cdot 1^2\]
which is greater than or equal to each of \(a = \beta + \gamma\), \(b = \alpha + \gamma\), and \(c = \beta + \alpha\) since all of \(\alpha\), \(\beta\), and \(\gamma\) are non--negative. \(\Box\)
Corollary: The topograph is connected; one may travel along the topograph from any given superbase to any other.
Proof: Using the same quadratic form \(f\) as we did to show the topograph had no cycles, we can show it is connected. Any arbitrary superbase is on the topograph, hence must be in some connected component of the topograph, but there may be more than one component. Since \(f\) is positive--valued, we must have some well in this component. But, by the above, the values at a well must be the absolute lowest values \(f\) takes on the topograph. This implies the well must take the values \(1\), \(1\), \(1\) and shows all superbases must be in the same component. \(\Box\)
From this point, we will concentrate on a special type of form relevant to our discussion. For a form \(f\) which takes both positive and negative values, but never \(0\), the topograph has a special path that separates the which separates the faces where takes a positive value and those where \(f\) takes a negative value.
Claim: If a form \(f\) takes both positive and negative values, but not zero, then there is a unique path of connected edges separating the positive and negative values. What's more, the values that occur on this river do so periodically.
Proof: Since the topograph is connected, there must be some edge where positive and negative values meet. As we proceed along adjacent edges, we can choose to follow a path of edges which will separate positive and negative (each subsequent value must be positive or negative, allowing us to "turn" left or right).
On first sight, there is no reason that this path should be unique. However, with the climbing lemma in mind, starting on the positive side of the path and moving away from the negative values, we must have only positive values. Using the logic of the climbing lemma instead with negative values, we similarly see that starting on the negative side and more away from the positive values will yield all negative numbers below the path. Hence nowhere above the path can positive and negative values meet and similarly below. Thus the path must be unique.
To show this path is periodic, we must utilize the discriminant. For each edge along the path, we have some positive value \(a\) and a negative \(b\) (by definition of the path) and the common difference \(h\). Thus the determinant \(D\) must be negative since the product \(ab\) is, hence
\[\left|D\right| = \left|ab\right| + \left(\frac{1}{2}h\right)^2.\]
Thus, both \(\left(\frac{1}{2}h\right)^2\) and \(\left|ab\right|\) are bounded by \(\left|D\right|\). So \(a\), \(b\) and \(h\) are bounded (by \(\left|D\right|\). Thus we have finitely many possible triples \((a, b, h)\), hence some value must be repeated in the path. This forces the path to be periodic since the triple starting from one triple \((a, b, h)\) determines next triple along the path and hence the entire path.
This path is so crucial that we give it it's own name.
Definition: If a form \(f\) takes both positive and negative values, but not zero, we call the path separating the positive and negative values the river. \(\Box\)
Thanks for reading, I'll make use of all this in a few days!
Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.
Update: All images were created with the tikz LaTeX library and can be compiled with native LaTeX if pgf is installed.
Definition: For the form \(f(x, y) = a x^2 + h x y + b y^2\), we define the discriminant as the value \(ab - \left(\frac{1}{2}h\right)^2\). \(\Box\)
The base \((1, 0)\) and \((0, 1)\) take values \(a\) and \(b\) on the form in the Definition above and are part of a sequence with common difference \(h\). In fact, if we know the values \(a'\), \(b'\) and the difference \(h'\) at any base (edge in the topograph), the value \(a'b' - \left(\frac{1}{2}h'\right)^2\) is independent of the base and the direction (left or right) which determines the sign of \(h'\) and hence equal to the discriminant. To see this, first note the sign of \(h'\) is immaterial since it is squared. Also, consider the two other bases (edges) in the superbase. As in the proof of the climbing lemma, one base takes values \(a' = a\) and \(b' = a + b + h\) with common difference \(h' = 2a + h\) which gives
\begin{align*}
a'b' - \left(\frac{1}{2}h'\right)^2 &= a(a + b + h) - \frac{1}{4}\left(2a + h\right)^2 \\
&= a^2 + a b + a h - \left(a^2 + a h + \frac{1}{4} h^2\right) \\
&= ab - \left(\frac{1}{2}h\right)^2.
\end{align*}
Similarly the other base in the given superbase gives
\begin{align*}
a'b' - \left(\frac{1}{2}h'\right)^2 &= (a + b + h)b - \frac{1}{4}\left(2b + h\right)^2 \\
&= b^2 + a b + b h - \left(b^2 + b h + \frac{1}{4} h^2\right) \\
&= ab - \left(\frac{1}{2}h\right)^2.
\end{align*}
Having showed that there are no cycles when starting from a given superbase, our work in understanding the topograph is not complete. We haven't actually showed that we can get from one superbase to any other superbases within the topograph. To show this, we'll use the discriminant and the following.
Definition: A superbase \(W\) is called a well if all the edges at \(W\) point away from \(W\).
\(\Box\)Notice a well is dependent on the values, hence depends on the form \(f\). In a positive--valued topograph, we may find a well by traveling along the topograph in the opposite direction of the edges. Eventually, we must encounter a superbase where all arrows point out (as above), leaving us nowhere to travel and thus becoming our well. This is because, assuming the topograph is positive--valued, we can only decrease in value for so long (eventually the values must approach the minimum).
Lemma: (The Well Lemma) For a positive--valued form \(f\) and a well (with respect to \(f\)) \(W\), the three values \(f\) takes on the faces in \(W\) are the smallest values that \(f\) takes on the topograph.
Proof: Using the labels from the well in the definition above, the Arithmetic Progression Rule for our differences gives
\[2\alpha = b + c - a, \quad 2\beta = c + a - b, \quad 2\gamma = a + b - c\]
and solving,
\[a = \beta + \gamma, \quad b = \alpha + \gamma, \quad c = \beta + \alpha.\]
Let the superbase \(W = \left\{e_1, e_2, e_3\right\}\). Since \(W\) is a superbase, we may write any vector as
\[v = m_1 e_1 + m_2 e_2 + m_3 e_3\]
for \(m_1\), \(m_2\), \(m_3 \in \mathbf{Z}\). Also due to the fact that \(W\) is a superbase, \(e_1 + e_2 + e_3 = (0, 0)\) and so we may also write
\[v = (m_1 - k) e_1 + (m_2 - k) e_2 + (m_3 - k) e_3\]
for \(k \in \mathbf{Z}\). From this it is clear only the differences of the \(m_i\) matter. With this as our inspiration we write
\[f(v) = \alpha(m_2 - m_3)^2 + \beta(m_1 - m_3)^2 + \gamma(m_1 - m_2)^2,\]
a formula discovered by Selling.
To verify this, notice both sides of the equation are quadratic forms in \(v\) and
\begin{align*}
f(e_1) = a &= \beta + \gamma = \alpha \cdot 0^2 + \beta \cdot 1^2 + \gamma \cdot 1^2 \\
f(e_2) = b &= \alpha + \gamma = \alpha \cdot 1^2 + \beta \cdot 0^2 + \gamma \cdot (-1)^2 \\
f(e_3) = c &= \beta + \alpha = \alpha \cdot (-1)^2 + \beta \cdot (-1)^2 + \gamma \cdot 0^2.
\end{align*}
hence they must be equal since both sides are quadratics that agree on more than two points.
If two of the \(m_i\) are equal, then \(v\) must be an integral multiple of the third vector, hence the value \(f(v)\) will be at least as large as the value of \(f\) on the third vector. If not, all the differences must be non--zero (hence greater than or equal to \(1\) in absolute value, since integers), thus
\[f(v) \geq \alpha \cdot 1^2 + \beta \cdot 1^2 + \gamma \cdot 1^2\]
which is greater than or equal to each of \(a = \beta + \gamma\), \(b = \alpha + \gamma\), and \(c = \beta + \alpha\) since all of \(\alpha\), \(\beta\), and \(\gamma\) are non--negative. \(\Box\)
Corollary: The topograph is connected; one may travel along the topograph from any given superbase to any other.
Proof: Using the same quadratic form \(f\) as we did to show the topograph had no cycles, we can show it is connected. Any arbitrary superbase is on the topograph, hence must be in some connected component of the topograph, but there may be more than one component. Since \(f\) is positive--valued, we must have some well in this component. But, by the above, the values at a well must be the absolute lowest values \(f\) takes on the topograph. This implies the well must take the values \(1\), \(1\), \(1\) and shows all superbases must be in the same component. \(\Box\)
From this point, we will concentrate on a special type of form relevant to our discussion. For a form \(f\) which takes both positive and negative values, but never \(0\), the topograph has a special path that separates the which separates the faces where takes a positive value and those where \(f\) takes a negative value.
Claim: If a form \(f\) takes both positive and negative values, but not zero, then there is a unique path of connected edges separating the positive and negative values. What's more, the values that occur on this river do so periodically.
Proof: Since the topograph is connected, there must be some edge where positive and negative values meet. As we proceed along adjacent edges, we can choose to follow a path of edges which will separate positive and negative (each subsequent value must be positive or negative, allowing us to "turn" left or right).
To show this path is periodic, we must utilize the discriminant. For each edge along the path, we have some positive value \(a\) and a negative \(b\) (by definition of the path) and the common difference \(h\). Thus the determinant \(D\) must be negative since the product \(ab\) is, hence
\[\left|D\right| = \left|ab\right| + \left(\frac{1}{2}h\right)^2.\]
Thus, both \(\left(\frac{1}{2}h\right)^2\) and \(\left|ab\right|\) are bounded by \(\left|D\right|\). So \(a\), \(b\) and \(h\) are bounded (by \(\left|D\right|\). Thus we have finitely many possible triples \((a, b, h)\), hence some value must be repeated in the path. This forces the path to be periodic since the triple starting from one triple \((a, b, h)\) determines next triple along the path and hence the entire path.
This path is so crucial that we give it it's own name.
Definition: If a form \(f\) takes both positive and negative values, but not zero, we call the path separating the positive and negative values the river. \(\Box\)
Thanks for reading, I'll make use of all this in a few days!
Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.
Update: All images were created with the tikz LaTeX library and can be compiled with native LaTeX if pgf is installed.
Conway's Topograph Part 2
This is the second (continued from Part 1) in a series of three blog posts. In the following we'll investigate a few properties of an object called Conway’s topograph. John Conway conjured up a way to understand a binary quadratic form – a very important algebraic object – in a geometric context. This is by no means original work, just my interpretation of some key points from his The Sensual (Quadratic) Form that I'll need for some other posts.
In the following, as mentioned in Part 1, "when referring to a base/superbase, we are referring to the lax equivalent of these notions."
To begin to form the topograph, note each superbase \(\left\{e_1, e_2, e_3\right\}\) contains only three bases
\[\left\{e_1, e_2\right\}, \left\{e_2, e_3\right\}, \left\{e_3, e_1\right\}\]
as subsets. Going the other direction, a base \(\left\{e_1, e_2\right\}\) can only possibly be contained as a subset of two superbases:
\[\langle e_1, e_2, (e_1 + e_2)\rangle, \langle e_1, e_2, (e_1 - e_2)\rangle.\]
With these two facts in hand, we can begin to form the geometric structure of the topograph. The interactions between bases and superbases (as well as the individual vectors themselves) give us the form. In the graph, we join each superbase (\(\bigcirc\)) to the three bases (\(\square\)) in it.
Each edge connecting two superbases (\(\bigcirc\)) represents a base and we mark each of these edges with a (\(\square\)) in the middle. Since each base can only be in two superbases, we have well--defined endpoints for each base (edge). Similarly, since each superbase contains three bases as subsets, each superbase (endpoint) has three bases (edges) coming out of it.
As we traverse each edge (base) surrounding a given vector (\(e_1\) above), we move from superbase (vertex) to superbase (vertex), and form a face. Starting from a base \(e_1, e_2\), traveling along each of the new faces encountered we begin to form the full (labeled) topograph below:
Notice the values of \(f\) on the combinations of \(e_1\) and \(e_2\) is immaterial to the above discussion, hence the shape of the topograph doesn't depend on \(f\).
If we know the values of \(f\) at some superbase, it is actually possibly to find the values of \(f\) at vectors (faces) we encounter on the topograph without actually knowing \(f\).
Claim: For vectors \(v_1, v_2\),
\[f(v_1 + v_2) + f(v_1 - v_2) = 2\left(f(v_1) + f(v_2)\right)\]
Proof: Exercise. (If you really can't get it, let me know in the comments.) \(\Box\)
This implies that if
\[a = f(v_1), \quad b = f(v_2), \quad c = f(v_1 + v_2), \quad d = f(v_1 - v_2)\]
then \(d\), \(a + b\), \(c\) form an arithmetic progression with common difference \(h\). This so--called Arithmetic Progression Rule allows us to mark each edge with a direction based on the value of \(h\). Hence if \(d < a + b < c\), we have \(h > 0\) and the following directed edge:
Proof: First \(c\) is positive because \(h = c - (a + b)\), hence \(c = a + b + h > 0\). The two other edges at \(Q\) have common differences \((a + c) - b\) and \((b + c) - a\). Since \(c = a + b + h\) is greater than both \(a\) and \(b\), these differences are positive. \(\Box\)
Notice also that this establishes two new triples \((a, a + b + h, 2 a + h)\) and \((b, a + b + h, 2 b + h)\) that continue to point away from each successive superbase and hence climb the topograph. We can use this lemma (along with a specific form) to show that there are no cycles in the topograph, i.e. the topograph doesn't loop back on itself.
Consider the form which takes the following values at a given superbase:
Due to the symmetry, we may consider traveling along an edge in any direction from this superbase identically. Picking an arbitrary direction, we reach the following superbase:
Since the values must increase indefinitely as laid out by the climbing lemma, the form can't loop back on itself; if it were to, it would need to loop back to a smaller value. Since this holds in all directions from the original well, there are no cycles.
Follow along to Part 3.
Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.
Update: All images were created with the tikz LaTeX library and can be compiled with native LaTeX if pgf is installed.
In the following, as mentioned in Part 1, "when referring to a base/superbase, we are referring to the lax equivalent of these notions."
To begin to form the topograph, note each superbase \(\left\{e_1, e_2, e_3\right\}\) contains only three bases
\[\left\{e_1, e_2\right\}, \left\{e_2, e_3\right\}, \left\{e_3, e_1\right\}\]
as subsets. Going the other direction, a base \(\left\{e_1, e_2\right\}\) can only possibly be contained as a subset of two superbases:
\[\langle e_1, e_2, (e_1 + e_2)\rangle, \langle e_1, e_2, (e_1 - e_2)\rangle.\]
With these two facts in hand, we can begin to form the geometric structure of the topograph. The interactions between bases and superbases (as well as the individual vectors themselves) give us the form. In the graph, we join each superbase (\(\bigcirc\)) to the three bases (\(\square\)) in it.
If we know the values of \(f\) at some superbase, it is actually possibly to find the values of \(f\) at vectors (faces) we encounter on the topograph without actually knowing \(f\).
Claim: For vectors \(v_1, v_2\),
\[f(v_1 + v_2) + f(v_1 - v_2) = 2\left(f(v_1) + f(v_2)\right)\]
Proof: Exercise. (If you really can't get it, let me know in the comments.) \(\Box\)
This implies that if
\[a = f(v_1), \quad b = f(v_2), \quad c = f(v_1 + v_2), \quad d = f(v_1 - v_2)\]
then \(d\), \(a + b\), \(c\) form an arithmetic progression with common difference \(h\). This so--called Arithmetic Progression Rule allows us to mark each edge with a direction based on the value of \(h\). Hence if \(d < a + b < c\), we have \(h > 0\) and the following directed edge:
Obviously starting from a base \(e_1, e_2\), one wonders if it is possible to move to any pair \((x, y)\) with \(x\) and \(y\) coprime along the topograph. It turns out that we can; the topograph forms a structure called a tree, and all nodes are connected.
Lemma: (Climbing Lemma) Given a superbase \(Q\) with the surrounding faces taking values \(a\), \(b\), and \(c\) as below, if the \(a\), \(b\) and the common difference \(h\) are all positive, then \(c\) is positive and the other two edges at \(Q\) point away from \(Q\).
Notice also that this establishes two new triples \((a, a + b + h, 2 a + h)\) and \((b, a + b + h, 2 b + h)\) that continue to point away from each successive superbase and hence climb the topograph. We can use this lemma (along with a specific form) to show that there are no cycles in the topograph, i.e. the topograph doesn't loop back on itself.
Consider the form which takes the following values at a given superbase:
Follow along to Part 3.
Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.
Update: All images were created with the tikz LaTeX library and can be compiled with native LaTeX if pgf is installed.
Conway's Topograph Part 1
This is the first in a series of three blog posts. In the following we'll investigate a few properties of an object called Conway’s topograph. John Conway conjured up a way to understand a binary quadratic form – a very important algebraic object – in a geometric context. This is by no means original work, just my interpretation of some key points from his The Sensual (Quadratic) Form that I'll need for some other posts.
Definition: A binary quadratic form \(f\) is an equation of the form:
\[f(x, y) = A x^2 + H x y + B y^2.\]
That is, a function of two variables which is homogeneous of degree two. The coefficients \(A\), \(H\), and \(B\) and variables \(x\) and \(y\) are often real numbers, rational numbers or integers. \(\Box\)
When we require the coefficients \(A\), \(H\), and \(B\) as well as the variables \(x, y\) to be integers, we get an integer--valued form. In his Disquisitiones Arithmeticae, Gauss asked (and largely answered) the fundamental question: what integer values can each form take? For example, you may have seen the form
\[f(x, y) = x^2 + y^2,\]
where it was determined that the only primes (Gaussian primes) occuring were \(2\) and those odd primes congruent to 1 modulo 4.
As each form \(f\) is homogenous degree two, \(f(\lambda x, \lambda y) = \lambda^2 f(x, y)\). As a result, if we can understand the values of \(f\) for pairs \((x, y)\) which don't share any factors, we can understand the entire set of values that \(f\) takes. Also, letting \(\lambda = -1\), there is no change in the value of \(f\) since \(\lambda^2 = 1\), hence it suffices to think of \(v = (x, y)\) as \(\pm v\), i.e. \(\left\{(x, y), (-x, -y)\right\}\).
For integers \(x\) and \(y\), any point \((x, y)\) can be expressed as an integral linear combination of the vectors \(e_1 = (1, 0)\) and \(e_2 = (0, 1)\). So if we like, we can express all relevant inputs for \(f\) in terms of two vectors. However, instead considering \(e_2 = (1, 1)\), we have
\[(x - y) \cdot e_1 + y \cdot e_2 = (x, y)\]
and realize a different pair \(e_1, e_2\) which again yield all possible integer valued vectors as integral linear combinations.
Definition: A strict base is an ordered pair \((e_1, e_2)\) whose integral linear combinations are exactly all vectors with integer coordinates. A lax base is a set \(\left\{\pm e_1, \pm e_2\right\}\) obtained from a strict base. \(\Box\)
Definition: A strict superbase is an ordered triple \((e_1, e_2, e_3)\), for which \(e_1 + e_2 + e_3 = (0, 0)\) and \((e_1, e_2)\) is a strict base (i.e., with strict vectors), and a lax superbase is a set \(\langle\pm e_1, \pm e_2, \pm e_3\rangle\) where \((e_1, e_2, e_3)\) is a strict superbase. \(\Box\)
For our (and Conway's) purposes, it is useful to consider the lax notions and leave the strict notions as an afterthought since a binary quadratic form is unchanged given a sign change. From here forward, for a vector \(v\), we use the notation \(v\) interchangeably with \(\pm v\) and when referring to a base/superbase, we are referring to the lax equivalent of these notions.
Follow along to Part 2.
Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.
Follow along to Part 2.
Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.
Monday, July 18, 2011
Continued fraction expansions of irrational square roots
I had no idea (until this Thursday, July 16) that I had never seen a proof of the fact that the continued fraction expansion of \(\sqrt{D}\) is periodic whenever \(D\) is not a perfect square. But have no fear, I found out about something called a reduced quadratic irrational and now have a proof. Here we go.
Definition: An irrational root \(\alpha\) of a quadratic equation with integer coefficients is called reduced if \(\alpha > 1\) and its conjugate \(\tilde{\alpha}\) satisfies \(-1 < \tilde{\alpha} < 0\). \(\Box\)
Solutions (since assumed real) of such quadratics can be written as $$\alpha = \frac{\sqrt{D} + P}{Q}$$ where \(D, P, Q \in \mathbf{Z}\) and \(D, Q > 0\). It is also possible (though not required) to ensure that \(Q\) divides \(D - P^2\). This is actually a necessary assumption for some of the stuff I do, is mentioned here and generally frustrated the heck out of me, so that. As an example for some enlightenment, notice $$\alpha = \frac{2 + \sqrt{7}}{4}$$ is reduced but \(4\) does not divide \(7 - 2^2\). However, if we write this as \(\frac{8 + \sqrt{112}}{16}\), we have our desired condition.
Definition: We say a reduced quadratic irrational \(\alpha\) is associated to \(D\) if we can write $$\alpha = \frac{P + \sqrt{D}}{Q}$$ and \(Q\) divides \(D - P^2\). \(\Box\)
Lemma 1: Transforming a reduced irrational root \(\alpha\) associated to \(D\) into its integer part and fractional part via $$\alpha = \lfloor \alpha \rfloor + \frac{1}{\alpha'},$$ the resulting quadratic irrational \(\alpha'\) is reduced and associated to \(D\) as well. (This is what one does during continued fraction expansion, and as I did with \(\sqrt{2}\) during my last post.)
Proof: Letting $$\alpha = \frac{\sqrt{D} + P}{Q}$$ and \(X = \lfloor \alpha \rfloor\), we have $$\frac{1}{\alpha'} = \frac{\sqrt{D} - (QX - P)}{Q}.$$
Thus \(\alpha'\) is both reduced and associated to \(D\). \(\Box\)
Lemma 2: There are finitely many reduced quadratic irrationals associated to a fixed \(D\).
Proof: As above write an arbitrary reduced irrational as \(\alpha = \frac{\sqrt{D} + P}{Q}\). Since \(\alpha > 1\) and \(\tilde{\alpha} > -1\), we know \(\alpha + \tilde{\alpha} = \frac{2P}{Q} > 0\) hence with the assumption \(Q > 0\) we have \(P > 0\). Since \(\tilde{\alpha} < 0\) we also have \(P < \sqrt{D}\). Also, since \(\alpha > 1\) by assumption we have \(Q < P + \sqrt{D} < 2\sqrt{D}\) thus there are finitely many choices for both \(P\) and \(Q\), forcing finitely many reduced quadratic irrationals associated to a fixed \(D\) (this amount is strictly bounded above by \(2D\)). \(\Box\)
Claim: The continued fraction expansion of \(\sqrt{D}\) is periodic whenever \(D\) is not a perfect square.
Proof: We'll use Lemma 1 to establish a series of reduced quadratic irrationals associated to \(D\) and then use Lemma 2 to assert this series must repeat (hence be periodic) due to the finite number of such irrationals.
Write \(a_0 = \lfloor \sqrt{D} \rfloor\) and \(\sqrt{D} = a_0 + \frac{1}{\alpha_0}\). From here, we will prove
Since \(\frac{1}{\alpha_0}\) is the fractional part of the irrational \(\sqrt{D}\), we have $$0 < \frac{1}{\alpha_0} < 1 \Rightarrow \alpha_0 > 1.$$ By simple algebra, we have $$\alpha_0 = \frac{a_0 + \sqrt{D}}{D - a_0^2}, \qquad \tilde{\alpha_0} = \frac{a_0 - \sqrt{D}}{D - a_0^2}.$$ Since \(a_0\) is the floor, we know \(a_0 - \sqrt{D} < 0 \Rightarrow \tilde{\alpha_0} < 0\). Since \(D \in \mathbf{Z} \Rightarrow \sqrt{D} > 1\) and \(\sqrt{D} > a_0\), we have $$1 < \sqrt{D} + a_0 \Rightarrow \sqrt{D} - a_0 < D - a_0^2 \Rightarrow a_0 - \sqrt{D} > -(D - a_0^2) \Rightarrow \tilde{\alpha_0} > -1.$$ Thus \(\alpha_0\) is a reduced quadratic irrational. Since \(P_0 = a_0\) and \(Q_0 = D - a_0^2 = D - P_0^2\), \(Q_0\) clearly divides \(D - P_0^2\) so \(\alpha_0\) is associated to \(D\) as well.
Following the recurrence defined, since each \(\alpha_i\) is a reduced quadratic irrational, each \(a_i \geq 1\). Also, by Lemma 1, each \(\alpha_{i + 1}\) is reduced and associated to \(D\) since \(\alpha_0\) is. By Lemma 2, we only have finitely many choices for these, hence there must be some smallest \(k\) for which \(\alpha_k = \alpha_0\). Since \(\alpha_{i + 1}\) is determined completely by \(\alpha_i\) we will then have \(\alpha_{k + j} = \alpha_j\) for all \(j > 0\), hence the \(\alpha_i\) are periodic. Similarly, as the \(a_i\) for \(i > 0\) are determined completely by \(\alpha_{i - 1}\), the \(a_i\) must be periodic as well, forcing the continued fraction expansion $$\sqrt{D} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}$$ to be periodic.\(\Box\)
Update: I posted this on
Definition: An irrational root \(\alpha\) of a quadratic equation with integer coefficients is called reduced if \(\alpha > 1\) and its conjugate \(\tilde{\alpha}\) satisfies \(-1 < \tilde{\alpha} < 0\). \(\Box\)
Solutions (since assumed real) of such quadratics can be written as $$\alpha = \frac{\sqrt{D} + P}{Q}$$ where \(D, P, Q \in \mathbf{Z}\) and \(D, Q > 0\). It is also possible (though not required) to ensure that \(Q\) divides \(D - P^2\). This is actually a necessary assumption for some of the stuff I do, is mentioned here and generally frustrated the heck out of me, so that. As an example for some enlightenment, notice $$\alpha = \frac{2 + \sqrt{7}}{4}$$ is reduced but \(4\) does not divide \(7 - 2^2\). However, if we write this as \(\frac{8 + \sqrt{112}}{16}\), we have our desired condition.
Definition: We say a reduced quadratic irrational \(\alpha\) is associated to \(D\) if we can write $$\alpha = \frac{P + \sqrt{D}}{Q}$$ and \(Q\) divides \(D - P^2\). \(\Box\)
Lemma 1: Transforming a reduced irrational root \(\alpha\) associated to \(D\) into its integer part and fractional part via $$\alpha = \lfloor \alpha \rfloor + \frac{1}{\alpha'},$$ the resulting quadratic irrational \(\alpha'\) is reduced and associated to \(D\) as well. (This is what one does during continued fraction expansion, and as I did with \(\sqrt{2}\) during my last post.)
Proof: Letting $$\alpha = \frac{\sqrt{D} + P}{Q}$$ and \(X = \lfloor \alpha \rfloor\), we have $$\frac{1}{\alpha'} = \frac{\sqrt{D} - (QX - P)}{Q}.$$
- Since \(\sqrt{D}\) is irrational, we must have \(\frac{1}{\alpha'} > 0\) and since \(\frac{1}{\alpha'}\) is the fractional part we know $$0 < \frac{1}{\alpha'} < 1 \Rightarrow \alpha' > 1.$$
- Transforming $$\alpha' = \frac{Q}{\sqrt{D} - (QX - P)} \cdot \frac{\sqrt{D} + (QX - P)}{\sqrt{D} + (QX - P)} = \frac{\sqrt{D} + (QX - P)}{\frac{1}{Q}\left(D - (QX - P)^2\right)},$$ we have \(P' = QX - P\) and \(Q' = \frac{1}{Q}\left(D - (QX - P)^2\right)\) and need to show \(Q' \in \mathbf{Z}\). But \(D - (QX - P)^2 \equiv D - P^2 \bmod{Q}\) and since \(\alpha\) is associated to \(D\), \(Q\) must divide this quantity, hence \(Q'\) is an integer.
- Since \(X = \lfloor\frac{\sqrt{D} + P}{Q}\rfloor\) is an integer and \(\alpha\) is irrational, we know \(X < \frac{\sqrt{D} + P}{Q}\) hence \(P' = QX - P < \sqrt{D}\) forcing \(\tilde{\alpha}' < 0\).
- Since \(\alpha > 1\) we know \(X \geq 1 \Leftrightarrow 0 \leq X - 1\). Thus \begin{align*}\tilde{\alpha} = \frac{P - \sqrt{D}}{Q} &< 0 \leq X - 1 \\ \Rightarrow Q &< \sqrt{D} + (QX - P) \\ \Rightarrow Q(\sqrt{D} - (QX - P)) &< D - (QX - P)^2 \\ \Rightarrow -\tilde{\alpha}' = \frac{\sqrt{D} - (QX - P)}{\frac{1}{Q}\left(D - (QX - P)^2\right)} &< 1 \end{align*} hence \(\tilde{\alpha}' > -1\) and \(\alpha'\) is reduced.
- Since \(Q' = \frac{1}{Q}\left(D - (P')^2\right)\), we know $$D - (P')^2 \equiv Q Q' \equiv 0 \bmod{Q'}$$ hence \(\alpha'\) is associated to \(D\).
Thus \(\alpha'\) is both reduced and associated to \(D\). \(\Box\)
Lemma 2: There are finitely many reduced quadratic irrationals associated to a fixed \(D\).
Proof: As above write an arbitrary reduced irrational as \(\alpha = \frac{\sqrt{D} + P}{Q}\). Since \(\alpha > 1\) and \(\tilde{\alpha} > -1\), we know \(\alpha + \tilde{\alpha} = \frac{2P}{Q} > 0\) hence with the assumption \(Q > 0\) we have \(P > 0\). Since \(\tilde{\alpha} < 0\) we also have \(P < \sqrt{D}\). Also, since \(\alpha > 1\) by assumption we have \(Q < P + \sqrt{D} < 2\sqrt{D}\) thus there are finitely many choices for both \(P\) and \(Q\), forcing finitely many reduced quadratic irrationals associated to a fixed \(D\) (this amount is strictly bounded above by \(2D\)). \(\Box\)
Claim: The continued fraction expansion of \(\sqrt{D}\) is periodic whenever \(D\) is not a perfect square.
Proof: We'll use Lemma 1 to establish a series of reduced quadratic irrationals associated to \(D\) and then use Lemma 2 to assert this series must repeat (hence be periodic) due to the finite number of such irrationals.
Write \(a_0 = \lfloor \sqrt{D} \rfloor\) and \(\sqrt{D} = a_0 + \frac{1}{\alpha_0}\). From here, we will prove
- \(\alpha_0\) is a reduced quadratic irrational associated to \(D\).
- By defining \(a_{i+1} = \lfloor \alpha_i \rfloor\) and \(\alpha_i = a_{i + 1} + \frac{1}{\alpha_{i + 1}}\), \(\alpha_{i + 1}\) is also a reduced quadratic irrational associated to \(D\) (assuming all \(\alpha\) up until \(i\) are as well).
Since \(\frac{1}{\alpha_0}\) is the fractional part of the irrational \(\sqrt{D}\), we have $$0 < \frac{1}{\alpha_0} < 1 \Rightarrow \alpha_0 > 1.$$ By simple algebra, we have $$\alpha_0 = \frac{a_0 + \sqrt{D}}{D - a_0^2}, \qquad \tilde{\alpha_0} = \frac{a_0 - \sqrt{D}}{D - a_0^2}.$$ Since \(a_0\) is the floor, we know \(a_0 - \sqrt{D} < 0 \Rightarrow \tilde{\alpha_0} < 0\). Since \(D \in \mathbf{Z} \Rightarrow \sqrt{D} > 1\) and \(\sqrt{D} > a_0\), we have $$1 < \sqrt{D} + a_0 \Rightarrow \sqrt{D} - a_0 < D - a_0^2 \Rightarrow a_0 - \sqrt{D} > -(D - a_0^2) \Rightarrow \tilde{\alpha_0} > -1.$$ Thus \(\alpha_0\) is a reduced quadratic irrational. Since \(P_0 = a_0\) and \(Q_0 = D - a_0^2 = D - P_0^2\), \(Q_0\) clearly divides \(D - P_0^2\) so \(\alpha_0\) is associated to \(D\) as well.
Following the recurrence defined, since each \(\alpha_i\) is a reduced quadratic irrational, each \(a_i \geq 1\). Also, by Lemma 1, each \(\alpha_{i + 1}\) is reduced and associated to \(D\) since \(\alpha_0\) is. By Lemma 2, we only have finitely many choices for these, hence there must be some smallest \(k\) for which \(\alpha_k = \alpha_0\). Since \(\alpha_{i + 1}\) is determined completely by \(\alpha_i\) we will then have \(\alpha_{k + j} = \alpha_j\) for all \(j > 0\), hence the \(\alpha_i\) are periodic. Similarly, as the \(a_i\) for \(i > 0\) are determined completely by \(\alpha_{i - 1}\), the \(a_i\) must be periodic as well, forcing the continued fraction expansion $$\sqrt{D} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}$$ to be periodic.\(\Box\)
Update: I posted this on
Sunday, July 10, 2011
Continued Fractions for the Greater Good part 1
OK, maybe not for the greater good, but still fun. This first post will be relatively short and sweet, intended to give an introduction for the posts that will follow.
Before the introduction, some motivation courtesy of Wikipedia:
The other motivation (the one I actually learned first in real life) for continued fractions comes from \(\sqrt{2}\) being represented by an infinite continued fraction. (Instead of saying a probability of \(0.01876\), people would rather say a \(1\) in \(53\) chance.) So we try to write \(\sqrt{2} = 1.41421356\ldots\) as \(1 + \frac{1}{2.414}\). But, instead, notice that $$\sqrt{2} = 1 + (\sqrt{2} - 1) = 1 + \frac{1}{\sqrt{2} + 1}.$$ Plugging this into itself, we have $$\sqrt{2} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}}}$$ and notice it can be represented by \((1; 2, 2, 2, \ldots)\).
Define the \(n\)th convergent to be \(\frac{h_n}{k_n}\), so above we have \(h_0 = a_0, k_0 = 1\) and \(h_1 = a_0 a_1 + 1, k_0 = a_1\).
Claim: \(h_n\) and \(k_n\) satisfy \begin{align*}h_n &= a_n h_{n - 1} + h_{n - 2} \\ k_n &= a_n k_{n - 1} + k_{n - 2} \end{align*} along with \(h_{-1} = 1, h_{-2} = 0\) and \(k_{-1} = 0, k_{-2} = 1\).
Proof: The fraction \(\frac{h_n}{k_n}\) is converted into \(\frac{h_{n + 1}}{k_{n + 1}}\) simply by changing \(a_n\) to \(a_n + \frac{1}{a_{n + 1}}\) in the final denominator. Since $$\frac{h_n}{k_n} = \frac{a_n h_{n - 1} + h_{n - 2}}{a_n k_{n - 1} + k_{n - 2}}$$ we similarly have \begin{align*} \frac{h_{n + 1}}{k_{n + 1}} &= \frac{\left(a_n + \frac{1}{a_{n + 1}}\right) h_{n - 1} + h_{n - 2}}{\left(a_n + \frac{1}{a_{n + 1}}\right) k_{n - 1} + k_{n - 2}} \\ &= \frac{a_{n + 1}(a_n h_{n - 1} + h_{n - 2}) + h_{n - 1}}{a_{n + 1}(a_n k_{n - 1} + k_{n - 2}) + k_{n - 1}} \\ &= \frac{a_{n + 1} h_n + h_{n - 1}}{a_{n + 1} k_n + k_{n - 1}}\end{align*}
Thus \(h_{n + 1}\) and \(k_{n + 1}\) satisfy the same recurrence.
It remains to check the initial conditions work, but note \begin{align*}h_0 &= a_0 h_{-1} + h_{-2} = a_0 \cdot 1 + 0 = a_0 \\ k_0 &= a_0 k_{-1} + k_{-2} = a_0 \cdot 0 + 1 = 1\end{align*} and \begin{align*}h_1 &= a_1 h_{0} + h_{-1} = a_0 a_1 + 1 \\ k_1 &= a_1 k_{0} + k_{-1} = a_1 \cdot 1 + 0 = a_1\end{align*} as we checked above. \(\Box\)
Check out my next post, where I actually accomplish something with fractions (or at least prepare to accomplish something).
Before the introduction, some motivation courtesy of Wikipedia:
“...decimal representation has some problems. One problem is that many rational numbers lack finite representations in this system. For example, the number \(\frac{1}{3}\) is represented by the infinite sequence \((0, 3, 3, 3, 3, \ldots )\). Another problem is that the constant \(10\) is an essentially arbitrary choice, and one which biases the resulting representation toward numbers that have some relation to the integer \(10\). For example, \(\frac{137}{1600}\) has a finite decimal representation, while \(\frac{1}{3}\) does not, not because \(\frac{137}{1600}\) is simpler than \(\frac{1}{3}\), but because \(1600\) happens to divide a power of \(10\) (\(10^6 = 1600 \times 625\)). Continued fraction notation is a representation of the real numbers that avoids both these problems. Let us consider how we might describe a number like \(\frac{415}{93}\), which is around \(4.4624\). This is approximately \(4\). Actually it is a little bit more than \(4\), about \(4 + \frac{1}{2}\). But the \(2\) in the denominator is not correct; the correct denominator is a little bit more than \(2\) about \(2 + \frac{1}{6}\), so \(\frac{415}{93}\) is approximately $$4 + \cfrac{1}{2+\cfrac{1}{6}}.$$ But the \(6\) in the denominator is not correct; the correct denominator is a little bit more than \(6\), actually \(6+\frac{1}{7}\). So \(\frac{415}{93}\) is actually $$4 + \cfrac{1}{2+\cfrac{1}{6 + \cfrac{1}{7}}}.$$ This is exact...”With this in mind, one can define an infinite continued fraction to be $$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}.$$ With the denominators \(a_0, a_1, a_2, \ldots\), we can define a recurrence for the finite approximations (convergents) of this value. For example, the zeroth is \(a_0\) and the first is \(a_0 + \frac{1}{a_1} = \frac{a_0 a_1 + 1}{a_1}\).
The other motivation (the one I actually learned first in real life) for continued fractions comes from \(\sqrt{2}\) being represented by an infinite continued fraction. (Instead of saying a probability of \(0.01876\), people would rather say a \(1\) in \(53\) chance.) So we try to write \(\sqrt{2} = 1.41421356\ldots\) as \(1 + \frac{1}{2.414}\). But, instead, notice that $$\sqrt{2} = 1 + (\sqrt{2} - 1) = 1 + \frac{1}{\sqrt{2} + 1}.$$ Plugging this into itself, we have $$\sqrt{2} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}}}$$ and notice it can be represented by \((1; 2, 2, 2, \ldots)\).
Define the \(n\)th convergent to be \(\frac{h_n}{k_n}\), so above we have \(h_0 = a_0, k_0 = 1\) and \(h_1 = a_0 a_1 + 1, k_0 = a_1\).
Claim: \(h_n\) and \(k_n\) satisfy \begin{align*}h_n &= a_n h_{n - 1} + h_{n - 2} \\ k_n &= a_n k_{n - 1} + k_{n - 2} \end{align*} along with \(h_{-1} = 1, h_{-2} = 0\) and \(k_{-1} = 0, k_{-2} = 1\).
Proof: The fraction \(\frac{h_n}{k_n}\) is converted into \(\frac{h_{n + 1}}{k_{n + 1}}\) simply by changing \(a_n\) to \(a_n + \frac{1}{a_{n + 1}}\) in the final denominator. Since $$\frac{h_n}{k_n} = \frac{a_n h_{n - 1} + h_{n - 2}}{a_n k_{n - 1} + k_{n - 2}}$$ we similarly have \begin{align*} \frac{h_{n + 1}}{k_{n + 1}} &= \frac{\left(a_n + \frac{1}{a_{n + 1}}\right) h_{n - 1} + h_{n - 2}}{\left(a_n + \frac{1}{a_{n + 1}}\right) k_{n - 1} + k_{n - 2}} \\ &= \frac{a_{n + 1}(a_n h_{n - 1} + h_{n - 2}) + h_{n - 1}}{a_{n + 1}(a_n k_{n - 1} + k_{n - 2}) + k_{n - 1}} \\ &= \frac{a_{n + 1} h_n + h_{n - 1}}{a_{n + 1} k_n + k_{n - 1}}\end{align*}
Thus \(h_{n + 1}\) and \(k_{n + 1}\) satisfy the same recurrence.
It remains to check the initial conditions work, but note \begin{align*}h_0 &= a_0 h_{-1} + h_{-2} = a_0 \cdot 1 + 0 = a_0 \\ k_0 &= a_0 k_{-1} + k_{-2} = a_0 \cdot 0 + 1 = 1\end{align*} and \begin{align*}h_1 &= a_1 h_{0} + h_{-1} = a_0 a_1 + 1 \\ k_1 &= a_1 k_{0} + k_{-1} = a_1 \cdot 1 + 0 = a_1\end{align*} as we checked above. \(\Box\)
Check out my next post, where I actually accomplish something with fractions (or at least prepare to accomplish something).
Subscribe to:
Posts (Atom)