I was working on a Project Euler problem a few years back. The problem is essentially asking for you to find all double digit fractions under $1$ where you cancel the same number on the top and bottom. Such as
$$\frac{49}{98}=\frac{4\cancel{9}}{\cancel{9}8}=\frac{4}{8}$$
Of course this is an incorrect method, but curiously, the equality remains. I was able to easily solve the problem with brute force. It's not a particularly computationally intensive problem. But when I shared the fun problem and results with a roommate of mine, he posed an interesting follow-up question. Can we extend this cancellation any further? And basically, we found that
$$\frac{4}{8}=\frac{49}{98}=\frac{499}{998}=\frac{4999}{9998}=\cdots$$
And it turns out that this worked for any number of $9$'s in that location and for any of the two digit fractions that were found. So, we generalize the problem:
For $a,b,c\in\mathbb{N}$ such that $0\leq a,b,c\leq 9$
$$\frac{a}{b}=\frac{10\cdot a+c}{10\cdot c + b} \implies \frac{a}{b}=\frac{10^n\cdot a + 10^{n-1}\cdot c + \cdots + 10 \cdot c +c}{10^n \cdot c + 10^{n-1}\cdot c + \cdots + 10\cdot c + b}$$
Or, in sigma notation
$$\frac{a}{b}=\frac{10^n\cdot a + c\cdot \sum_{i=0}^{n-1}{10^i}}{c\cdot \sum_{i=1}^{n}{10^i} + b}$$
Through algebra (cross multiply, group and divide), our premise implies that
$$c=\frac{9ab}{10a-b}$$
So, consider the right hand side of the conclusion and substitute the above equality for $c$.
$$\frac{10^n\cdot a + c\cdot \sum_{i=0}^{n-1}{10^i}}{c\cdot \sum_{i=1}^{n}{10^i} + b}=\frac{10^n\cdot a + \frac{9ab}{10a-b}\cdot\sum_{i=0}^{n-1}{10^i}}{\frac{9ab}{10a-b}\cdot \sum_{i=1}^{n}{10^i} + b}$$
Multiply top and bottom by $10a-b$ and get
$$\frac{\left(10a-b\right)10^n\cdot a + 9ab\cdot\sum_{i=0}^{n-1}{10^i}}{9ab\cdot \sum_{i=1}^{n}{10^i} + \left(10a-b\right)b}$$
Distribute into the parenthesis
$$\frac{10^{n+1}\cdot a^2 - 10^n\cdot a b + 9ab\cdot \sum_{i=0}^{n-1}{10^i}}{9ab\cdot\sum_{i=1}^{n}{10^i}+10ab-b^2}$$
Factor out $-ab$ from two terms on the top and $ab$ from two terms on the bottom.
$$\frac{10^{n+1}\cdot a^2 - ab\left[10^n - 9\cdot \sum_{i=0}^{n-1}{\left(10^i\right)}\right]}{ab\left[9\cdot\sum_{i=1}^{n}{\left(10^i\right)}+10\right]-b^2}$$
Looking at the top brace, we have $n$ nines subtracted from the number $1$ followed by $n$ zeros, which is just $1$. For example
$$\begin{array}{c}
10-9=1\\
100-99=1\\
1000-999=1\\
\vdots
\end{array}$$
Then looking at the bottom brace, we have
$$9\cdot\sum_{i=1}^{n}{\left(10^i\right)}+10=9\cdot\sum_{i=1}^{n}{\left(10^i\right)}+9+1=9\cdot\sum_{i=0}^{n}{\left(10^i\right)}+1$$
which is now $n+1$ nines added to $1$ which will be a $1$ followed by $n+1$ zeros or $10^{n+1}$. For example
$$\begin{array}{c}
9+1=10\\
99+1=100\\
999+1=1000\\
\vdots
\end{array}$$
Substituting these in we get
$$\frac{10^{n+1}\cdot a^2 -ab}{ab\cdot 10^{n+1} - b^2}$$
Finally, factor out $a$ on top and $b$ on the bottom and cancel the rest to get
$$\frac{a\left(10^{n+1}\cdot a - b\right)}{b\left(10^{n+1}\cdot a - b\right)}=\frac{a}{b}$$
Therefore, if we can cancel the digits in the (incorrect) manner we did, we can add as many of this number as we'd like and still maintain equality.
Showing posts with label Fractions. Show all posts
Showing posts with label Fractions. Show all posts
Friday, May 30, 2014
Saturday, May 3, 2014
Converging Sequence of Unusually Summed Fractions
While reading Measurement by Paul Lockhart, I came across his explanation for the length of the diagonal in the unit square. He first takes some "guesses" for the number $d$ that squares to $2$:
$$\frac{3}{2}, \frac{7}{5}, \frac{10}{7}, \frac{17}{12}$$
Of course these are incorrect, but the sequence intrigued me. I was wondering why he picked these particular guesses. I noticed a pattern; the numerator of each term is the sum of the numerators of the previous two terms and the denominator of each term is the sum of the denominators of the previous two terms. I thought that maybe if we followed the same pattern we may converge to $\sqrt{2}$.
$$
\begin{array}{|c|c|}
\hline
\mathrm{\mathbf{Fraction}} & \mathrm{\mathbf{Approx.}} \\
\hline
3/2 & 1.50000\\
7/5 & 1.40000\\
10/7 & 1.42857\\
17/12 & 1.41667\\
27/19 & 1.42105\\
44/31 & 1.41935\\
71/50 & 1.42000\\
115/81 & 1.41975\\
186/131 & 1.41985\\
301/212 & 1.41981\\
487/343 & 1.41983\\
788/555 & 1.41982\\
\hline
\end{array}
$$
Clearly, this is not approaching $\sqrt{2}$. But it does appear to be converging to something close to $1.41982$. What exactly is going on here?
Let's generalize the problem a little bit more: Define the sequences $\{a_n\}$ and $\{b_n\}$ such that $a_n = a_{n-1} + a_{n-2}$ and $b_n = b_{n-1} + b_{n-2}$, with $a_1 \geq a_0 > 0$ and $b_1 \geq b_0>0$ given. Define another sequence $\{c_n\}$ such that $c_n = a_n/b_n$.
Some questions of particular interest include: Does $\{c_n\}$ always converge? If it converges, what is $\lim_{n\to\infty}c_n$? Can we find a closed form solution for $c_n$?
The first thing I noticed is that $c_n$ is between $c_{n-1}$ and $c_{n-2}$. To show this, assume, without loss of generality, that $c_{n-2}\leq c_{n-1}$. This means that $$ \frac{a_{n-2}}{b_{n-2}} \leq \frac{a_{n-1}}{b_{n-1}} \implies a_{n-2}b_{n-1} \leq a_{n-1}b_{n-2} $$ Consider $a_{n-2}(b_{n-2}+b_{n-1})$. $$ \begin{array}{r l} a_{n-2}(b_{n-2}+b_{n-1}) & = a_{n-2}b_{n-2}+a_{n-2}b_{n-1} \\ & \leq a_{n-2}b_{n-2} + b_{n-2}a_{n-1} \\ & = b_{n-2}(a_{n-2}+a_{n-1}) \end{array}$$ And from here it's clear to see the following inequality $$\frac{a_{n-2}}{b_{n-2}} \leq \frac{a_{n-2}+a_{n-1}}{b_{n-2}+b_{n-2}} \implies c_{n-2} \leq c_{n}$$ Following similarly, we can look at $b_{n-1}(a_{n-2}+a_{n-1})$ to show $c_{n} \leq c_{n-1}$. Therefore we have $$ c_{n-2} \leq c_{n} \leq c_{n-1} $$ and we can conclude that $c_n$ is always between $c_{n-1}$ and $c_{n-2}$ (the other direction of "between" comes from the opposite assumption that $c_{n-2}\geq c_{n-1}$).
While an interesting result, this doesn't necessarily put us any closer to showing convergence. I attempted to bound the sequence between the subsequence of even indices (which is decreasing) and the subsequence of odd indices (which is increasing) and squeeze out a limit. I was able to prove the bound existed, but I was not able to prove convergence for either of the two subsequences. I may share some of this work in a later post, but this direction wasn't leading anywhere. So, I temporarily gave up on showing convergence and moved onto coming up with a closed form for $c_n$. And in searching for a closed form solution, I found the following proof for both a closed form solution and the convergence.
For notational purposes, I will index the Fibonacci sequence, $\{0,1,1,2,3,5,\ldots\}$, as follows: $$F_0 =0, \; F_1 = 1, \; F_2 = 1, \; F_3 = 2, \; F_4 = 3, \; F_5 = 5, \ldots$$ I will first show that $a_n = F_n a_1 + F_{n-1} a_0$ for all $n\geq 2$. Proceeding by induction, the base case of $n=2$ works out: $$a_2 = a_1 + a_0 = 1 \cdot a_1 + 1 \cdot a_0 = F_2 a_1 + F_1 a_0$$ Now, assume that $a_k = F_k a_1 + F_{k-1}a_0$ for all $2\leq k\leq n$. And we want to show that $a_{n+1} = F_{n+1}a_1 + F_n a_0$. $$ \begin{array}{rl} a_{n+1}& = a_n + a_{n-1} \\ &= \left(F_na_1 + F_{n-1}a_0\right) + \left(F_{n-1}a_1 + F_{n-2}a_0\right) \\ &= \left(F_n + F_{n-1}\right)a_1+\left(F_{n-1}+F_{n-2}\right)a_0 \\ &= F_{n+1}a_1 + F_n a_0 \end{array} $$ In the same manner we can show that $b_n = F_n b_1 + F_{n-1} b_0$. Based on this, we can show that $$c_n = \frac{a_n}{b_n} = \frac{F_n a_1 + F_{n-1} a_0}{F_n b_1 + F_{n-1} b_0}\cdot\frac{1/F_{n-1}}{1/F_{n-1}}=\frac{\left(F_n/F_{n-1}\right)a_1+a_0}{\left(F_n/F_{n-1}\right)b_1+b_0}$$ Based on the well known result that the ratio between adjacent Fibonacci numbers approaches the golden ratio, $\phi$, we can conclude that $$\lim_{n\to\infty}c_n = \frac{\phi a_1 + a_0}{\phi b_1 + b_0}$$ We have shown convergence!
Let's reconsider the original problem. Recall that $a_0 = 3, a_1 = 7, b_0 = 2, $ and $b_1 = 5$. Our convergence theorem shows that $$\lim_{n\to\infty}c_n = \frac{7\phi +3}{5\phi+2} \approx 1.41982$$ Exactly what we saw happening! One more interesting result that I found along the way is that $$\lim_{n\to\infty}\frac{a_n}{a_{n-1}}= \lim_{n\to\infty}\frac{b_n}{b_{n-1}}=\phi$$ Basically, any two positive starting numbers in a Fibonacci-esque sequence will always have an adjacent term ratio of $\phi$, just like the Fibonacci sequence.
Let's generalize the problem a little bit more: Define the sequences $\{a_n\}$ and $\{b_n\}$ such that $a_n = a_{n-1} + a_{n-2}$ and $b_n = b_{n-1} + b_{n-2}$, with $a_1 \geq a_0 > 0$ and $b_1 \geq b_0>0$ given. Define another sequence $\{c_n\}$ such that $c_n = a_n/b_n$.
Some questions of particular interest include: Does $\{c_n\}$ always converge? If it converges, what is $\lim_{n\to\infty}c_n$? Can we find a closed form solution for $c_n$?
The first thing I noticed is that $c_n$ is between $c_{n-1}$ and $c_{n-2}$. To show this, assume, without loss of generality, that $c_{n-2}\leq c_{n-1}$. This means that $$ \frac{a_{n-2}}{b_{n-2}} \leq \frac{a_{n-1}}{b_{n-1}} \implies a_{n-2}b_{n-1} \leq a_{n-1}b_{n-2} $$ Consider $a_{n-2}(b_{n-2}+b_{n-1})$. $$ \begin{array}{r l} a_{n-2}(b_{n-2}+b_{n-1}) & = a_{n-2}b_{n-2}+a_{n-2}b_{n-1} \\ & \leq a_{n-2}b_{n-2} + b_{n-2}a_{n-1} \\ & = b_{n-2}(a_{n-2}+a_{n-1}) \end{array}$$ And from here it's clear to see the following inequality $$\frac{a_{n-2}}{b_{n-2}} \leq \frac{a_{n-2}+a_{n-1}}{b_{n-2}+b_{n-2}} \implies c_{n-2} \leq c_{n}$$ Following similarly, we can look at $b_{n-1}(a_{n-2}+a_{n-1})$ to show $c_{n} \leq c_{n-1}$. Therefore we have $$ c_{n-2} \leq c_{n} \leq c_{n-1} $$ and we can conclude that $c_n$ is always between $c_{n-1}$ and $c_{n-2}$ (the other direction of "between" comes from the opposite assumption that $c_{n-2}\geq c_{n-1}$).
While an interesting result, this doesn't necessarily put us any closer to showing convergence. I attempted to bound the sequence between the subsequence of even indices (which is decreasing) and the subsequence of odd indices (which is increasing) and squeeze out a limit. I was able to prove the bound existed, but I was not able to prove convergence for either of the two subsequences. I may share some of this work in a later post, but this direction wasn't leading anywhere. So, I temporarily gave up on showing convergence and moved onto coming up with a closed form for $c_n$. And in searching for a closed form solution, I found the following proof for both a closed form solution and the convergence.
For notational purposes, I will index the Fibonacci sequence, $\{0,1,1,2,3,5,\ldots\}$, as follows: $$F_0 =0, \; F_1 = 1, \; F_2 = 1, \; F_3 = 2, \; F_4 = 3, \; F_5 = 5, \ldots$$ I will first show that $a_n = F_n a_1 + F_{n-1} a_0$ for all $n\geq 2$. Proceeding by induction, the base case of $n=2$ works out: $$a_2 = a_1 + a_0 = 1 \cdot a_1 + 1 \cdot a_0 = F_2 a_1 + F_1 a_0$$ Now, assume that $a_k = F_k a_1 + F_{k-1}a_0$ for all $2\leq k\leq n$. And we want to show that $a_{n+1} = F_{n+1}a_1 + F_n a_0$. $$ \begin{array}{rl} a_{n+1}& = a_n + a_{n-1} \\ &= \left(F_na_1 + F_{n-1}a_0\right) + \left(F_{n-1}a_1 + F_{n-2}a_0\right) \\ &= \left(F_n + F_{n-1}\right)a_1+\left(F_{n-1}+F_{n-2}\right)a_0 \\ &= F_{n+1}a_1 + F_n a_0 \end{array} $$ In the same manner we can show that $b_n = F_n b_1 + F_{n-1} b_0$. Based on this, we can show that $$c_n = \frac{a_n}{b_n} = \frac{F_n a_1 + F_{n-1} a_0}{F_n b_1 + F_{n-1} b_0}\cdot\frac{1/F_{n-1}}{1/F_{n-1}}=\frac{\left(F_n/F_{n-1}\right)a_1+a_0}{\left(F_n/F_{n-1}\right)b_1+b_0}$$ Based on the well known result that the ratio between adjacent Fibonacci numbers approaches the golden ratio, $\phi$, we can conclude that $$\lim_{n\to\infty}c_n = \frac{\phi a_1 + a_0}{\phi b_1 + b_0}$$ We have shown convergence!
Let's reconsider the original problem. Recall that $a_0 = 3, a_1 = 7, b_0 = 2, $ and $b_1 = 5$. Our convergence theorem shows that $$\lim_{n\to\infty}c_n = \frac{7\phi +3}{5\phi+2} \approx 1.41982$$ Exactly what we saw happening! One more interesting result that I found along the way is that $$\lim_{n\to\infty}\frac{a_n}{a_{n-1}}= \lim_{n\to\infty}\frac{b_n}{b_{n-1}}=\phi$$ Basically, any two positive starting numbers in a Fibonacci-esque sequence will always have an adjacent term ratio of $\phi$, just like the Fibonacci sequence.
Subscribe to:
Posts (Atom)