Fi & Lu Area Algebra Trigonometry Functions Complex Numbers Calculus
Fi had just learned to add. Her parents wouldn’t let her have any more screen time, so she was really, really bored. She mindlessly decided to do some addition problems…
| 0 | + | 1 | = | 1 | ||||||||||||
| 1 | + | 1 | = | 2 | ||||||||||||
| 1 | + | 2 | = | 3 | ||||||||||||
| 2 | + | 3 | = | 5 | ||||||||||||
| 3 | + | 5 | = | 8 | ||||||||||||
| 5 | + | 8 | = | 13 | ||||||||||||
| 8 | + | 13 | = | 21 |
The numbers seemed to get bigger faster and faster. She knew a little about ratios, and wondered how the ratios between successive numbers changed. She asked her big sister Lu to help her.
Lu knew about fractions and the number line, so she helped Fi plot the ratios. They all seemed to be between 1 and 2, so this is what she drew:
The ratios seemed to be getting closer and closer to some particular number between 1 and 2, with each successive ratio somewhere between the last two. Grandpa showed them this zoom-in…
But what was the exact ratio? Their mom Goldie showed them a little algebra to figure it out…
Goldie said, “Let’s name the ratio after Fi, and use the Greek letter \(\phi\). If some number well into the sequence is \(n\), then the next number is pretty much \(n \times \phi\), and the number after that is about \(n \times \phi \times \phi\). But we know that the sum of those first two is the third: \(n + n\phi = n\phi^2\). We can divide by \(n\) and get \(1+\phi = \phi^2\). This gives the quadratic equation \(\phi^2-\phi-1 = 0\), and, since we know \(\phi > 1\), the solution, using the quadratic formula, is \(\phi = \frac{1+\sqrt{5}}{2}\).”
Fi and Lu decided to name \(\phi\) after their mom, so they called it the Golden ratio. It turns out that \(\phi\) is the most irrational number in the sense that the sequence of “best” nearby fractions approaches it as slowly as possible. (A nearby fraction is “best” if no fraction with an equal or smaller denominator is closer.)
We can use \(\phi\)’s quadratic equation to see that \(\phi = \frac{\phi^2}{\phi} = \frac{\phi+1}{\phi} = 1+\frac{1}{\phi}\), or \(\frac{1}{\phi} = \phi-1\). So if you have a rectangle whose sides have a ratio of \(\phi\), and remove a square, the remaining rectangle is similar to the original one!
Lu wondered what would happen if she started with different numbers, and decided to try 2 and 1. (This was the first pair that didn’t just produce Fi’s sequence.)
| 2 | + | 1 | = | 3 | ||||||||||
| 1 | + | 3 | = | 4 | ||||||||||
| 3 | + | 4 | = | 7 | ||||||||||
| 4 | + | 7 | = | 11 | ||||||||||
| 7 | + | 11 | = | 18 | ||||||||||
| 11 | + | 18 | = | 29 |
Goldie suggested writing the nth number in Fi’s sequence as \(f_n\) and the nth number in Lu’s sequence as \(l_n\). With that notation, \(f_{n+1} = f_n + f_{n-1}\) and \(l_{n+1} = l_n + l_{n-1}\), and this addition property determines the sequences when combined with their initial values (\(f_0 = 0\), \(f_1=1\), \(l_0 = 2\), \(l_1=1\)). She pointed out that \(\phi\) and \(1-\phi = (-\phi)^{-1}\) are the two solutions to the quadratic equation \(x^2=x+1\) and so the geometric sequences \(\phi^n\) and \((-\phi)^{-n}\) each have the same addition property: \(\phi^{n+1} = \phi^n + \phi^{n-1}\) and \((-\phi)^{-(n+1)} = (-\phi)^{-n} + (-\phi)^{-(n-1)}\). It is easy to see that any linear combination of \(\phi^n\) and \((-\phi)^{-n}\) will also have that property. In particular, \(f_n = \frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}\) and \(l_n = \phi^n+(-\phi)^{-n}\). All we need to verify those formulas is to check that they’re true for \(n=0\) and \(n=1\). We can then conclude that they’re true for all integers (both positive and negative). This is called bidirectional induction.
Bidirectional induction on \(n\) can verify that \(l_n = f_{n-1}+f_{n+1}\) and bidirectional induction on \(k\) can verify that \(f_{n+k} = l_kf_n-(-1)^kf_{n-k}\) and \(l_{n+k} = l_kl_n-(-1)^kl_{n-k}\). When \(n=k\) we get \(f_{2n} = l_nf_n\) since \(f_0=0\) and \(l_{2n} = l_n^2-2(-1)^n\) since \(l_0=2\).
Some formulas are ridiculously easy to verify. For example \(2f_n = f_n + f_n = f_n + f_{n-1} + f_{n-2} = f_{n+1} + f_{n-2}\), and similarly \(2l_n = l_{n+1}+l_{n-2}\). Meanwhile, \(3f_n = f_n + 2f_n = f_n + f_{n+1} + f_{n-2} = f_{n+2} + f_{n-2}\), and similarly \(3l_n = l_{n+2}+l_{n-2}\). Slightly harder are \(\sum_{n=a}^b f_n = f_{b+2}-f_{a+1}\) and \(\sum_{n=a}^b l_n = l_{b+2}-l_{a+1}\).
Other formulas can be derived directly from those that express \(f_n\) and \(l_n\) in terms of \(\phi\): \(l_n^2 = l_{2n} + 2(-1)^n\) (didn’t we just see this one?) and \(5f_n^2 = l_{2n} - 2(-1)^n\). Also \(|f_n| = |f_{-n}|\) and \(|l_n| = |l_{-n}|\) (the surrounding vertical bars mean absolute value).
As long as Goldie was showing the girls quadratic equations, she decided that she might as well show them something simpler: matrix arithmetic. After all, a matrix is just a rectangular array of numbers, with special methods for matrix addition and multiplication. While a matrix can be any size, \(2\times 2\) matrices are sufficient for investigating the girls’ sequences.
If we have a pair of matrices \(\boldsymbol{A}=\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}\) and \(\boldsymbol{B}=\begin{bmatrix}b_{11}&b_{12}\\b_{21}&b_{22}\end{bmatrix}\), then addition is element by element: \(\boldsymbol{A}+\boldsymbol{B}=\begin{bmatrix}a_{11}+b_{11}&a_{12}+b_{12}\\a_{21}+b_{21}&a_{22}+b_{22}\end{bmatrix}\).
Multiplication is more complicated, with each element in the product combining a row of the first matrix with a column of the second: \(\boldsymbol{A}\boldsymbol{B}=\begin{bmatrix}a_{11}b_{11}+a_{12}b_{21}&a_{11}b_{12}+a_{12}b_{22}\\a_{21}b_{11}+a_{22}b_{21}&a_{21}b_{12}+a_{22}b_{22}\end{bmatrix}\).
With those methods, most of the usual properties of addition and multiplication hold. One notable exception is that \(\boldsymbol{A}\boldsymbol{B}\) is not necessarily equal to \(\boldsymbol{B}\boldsymbol{A}\).
It’s not hard to see that \(\begin{bmatrix}f_n&f_{n+1}\\f_{n+1}&f_{n+2}\end{bmatrix}=\begin{bmatrix}0&1\\1&1\end{bmatrix}\begin{bmatrix}f_{n-1}&f_n\\f_n&f_{n+1}\end{bmatrix}\), and \(\begin{bmatrix}l_n&l_{n+1}\\l_{n+1}&l_{n+2}\end{bmatrix}=\begin{bmatrix}0&1\\1&1\end{bmatrix}\begin{bmatrix}l_{n-1}&l_n\\l_n&l_{n+1}\end{bmatrix}\). This is just a complicated way to express that the next element of either sequence is the sum of the previous two elements.
If we define \(\mathbf{F}=\begin{bmatrix}f_0&f_1\\f_1&f_2\end{bmatrix}=\begin{bmatrix}0&1\\1&1\end{bmatrix}\), and \(\mathbf{L}=\begin{bmatrix}l_{-1}&l_0\\l_0&l_1\end{bmatrix}=\begin{bmatrix}-1&2\\2&1\end{bmatrix}\), then \(\begin{bmatrix}f_{n-1}&f_n\\f_n&f_{n+1}\end{bmatrix}=\mathbf{F}^n\) and \(\begin{bmatrix}l_{n-1}&l_n\\l_n&l_{n+1}\end{bmatrix}=\mathbf{F}^n\mathbf{L}\).
These last two equations actually suggest a fast way to compute large members of the sequences, because there is a trick for doing exponentiation quickly. And, together with the observation that \(\mathbf{F}\mathbf{L} = \mathbf{L}\mathbf{F}\), they will help to discover several formulas for the sequences.
For example, since \(\mathbf{F}^{m+n} = \mathbf{F}^m \mathbf{F}^n\), we can see that \(f_{m+n} = f_m f_{n-1} + f_{m+1} f_n\). And since \(\mathbf{F}^{m+n}\mathbf{L} = \mathbf{F}^m \mathbf{L} \mathbf{F}^n\) we also have \(l_{m+n} = l_m f_{n-1}+l_{m+1}f_n\).
By replacing \(m\) with \(-m\) in \(f_{m+n} = f_m f_{n-1} + f_{m+1} f_n\), we get \(f_{n-m} = f_{-m} f_{n-1} + f_{1-m} f_n\). An interesting consequence is that if we have a divisor of both \(f_m\) and \(f_n\), it is also a divisor of \(f_{n-m}\). Conversely, by replacing \(n\) with \(n-m\), we get \(f_n = f_m f_{n-m-1} + f_{m+1} f_{n-m}\), so if we have a divisor of both \(f_m\) and \(f_{n-m}\), it is also a divisor of \(f_n\). These two observations mean that \(\{ f_n,f_m\}\) have the same common divisors as \(\{ f_{n-m},f_m\}\). The Euclidean algorithm for finding the greatest common divisor of two numbers uses the observation that \(\{a,b\}\) and \(\{a-b,b\}\) have the same common divisors to find smaller and smaller pairs with those common divisors until one element of the pair is zero, at which point the other element is clearly the greatest common divisor of the original two numbers. So, noting that \(f_0 = 0\), we can parallel the Euclidean algorithm on \(\{a,b\}\) and start with \(\{f_a,f_b\}\) and arrive at \(\{f_{\gcd(a,b)},f_0\}\) to conclude that \(\gcd(f_a,f_b) = f_{\gcd(a,b)}\).
By the way, Fi’s sequence is actually called the Fibonacci sequence, and Lu’s sequence is named the Lucas sequence. Meanwhile, the Golden ratio is, in fact, called the Golden ratio, and written as \(\phi\).
Algebra is a way to describe relationships between numbers.
We use letters so that we can describe many relationships at the same time. For example, to say that zero added to any number is that same number, we can write \(\forall n\; 0+n=n\). Note that \(\forall\) means “for all”.
If the three sides of a triangle are \(a\), \(b\), and \(c\), then we know that \(a>b+c\), \(b>c+a\), and \(c>a+b\). Note that \(>\) means “is greater than” and \(<\) means “is less than”.
We sometimes use parentheses to specify the order we do operations. Operations inside parentheses are always done before other operations.
There are some properties of addition and multiplication that we can describe:
Associativity of addition: \(\forall a\forall b\forall c\;(a+b)+c = a+(b+c)\).
Associativity of multiplication: \(\forall a\forall b\forall c\;(ab)c = a(bc)\). Note that we don’t often use \(\times\) for multiplication; instead we just concatenate.
Because addition and multiplication are associative, we don’t need to use parentheses when we write \(a+b+c\) or \(abc\).
Commutativity of addition: \(\forall a\forall b\;a+b\) = \(b+a\).
Commutativity of multiplication: \(\forall a\forall b\;ab\) = \(ba\).
Distributivity of multiplication over addition: \(\forall a\forall b\forall c\;a(b+c) = ab+ac\). Note that without parentheses, multiplication is always done before addition.
One of the basic principles of algebra is that if we have an equation (something = something else) and we perform the same operation to each side of the equation, the new equation will still be true.
We’re given \(ax^2+bx+c=0\).
Divide both sides by \(a\): \(x^2+\frac{b}{a}+\frac{c}{a}=0\).
Add \(\frac{b^2}{4a^2}-\frac{c}{a}\) to both sides: \(x^2+\frac{b}{a}+\frac{b^2}{4a^2}=\frac{b^2}{4a^2}-\frac{c}{a}\).
Left side is a perfect square: \((x+\frac{b}{2a})^2 = \frac{b^2-4ac}{4a^2}\).
Take square root of both sides: \(x+\frac{b}{2a} = \pm\frac{\sqrt{b^2-4ac}}{2a}\).
So \(x = \frac{-b\pm\sqrt{b^2-4ac}}{2a}\).
A geometric sequence is a sequence of numbers with a fixed ratio between successive numbers. For example, if the first number in the sequence is \(1\), and the second is \(r\), then the nth term is \(r^n\). We can calculate the sum of the first \(k\) terms, \(s = \sum_{n=0}^{k-1}r^n\), by noticing that \(1+rs = s+r^k\) so \(s = \frac{r^k-1}{r-1}\); except that if \(r=1\), the sum is just \(k\). You might note that if \(r<1\), we’d probably write this as \(s = \frac{1-r^k}{1-r}\). If \(|r|<1\), the infinite sum \(\sum_{n=0}^\infty r^n = \frac{1}{1-r}\); if \(|r|\ge 1\), the infinite sum diverges.
If we want to prove something for all nonnegative integers, it’s sufficient to prove it for 0 and then prove that if it’s true for \(n\) then it’s true for \(n+1\). If we want to prove it for all integers, then we also need to show that if it’s true for \(n\) then it’s true for \(n-1\).
In the case of proving something about a sequence \(s_n\) with the property that \(s_{n+1}=s_n+s_{n-1}\), if we can prove it for \(s_0\) and \(s_1\), then we can prove it for all integers by showing it’s true for \(s_{n+1}=s_n+s_{n-1}\) and for \(s_{n-2}=s_n-s_{n-1}\) whenever it’s true for \(s_n\) and \(s_{n-1}\).
The idea is to write the exponent in binary.
You start by setting the result to the multiplicative identity, which is 1 if the base is a number, and the identity matrix I if the base is a matrix.
Then, for each bit of the exponent, starting at the left, square the result, and if the bit is a 1, multiply the result by the base. This works because \(x^{2a+b} = (x^a)^2 x^b\).
When you’ve exhausted the exponent, the result is your answer.
You’ve done one or two multiplications for each bit of the exponent, which is exponentially faster than doing exponent-many multiplications.
Associativity: \(\boldsymbol{A}+(\boldsymbol{B}+\boldsymbol{C}) = (\boldsymbol{A}+\boldsymbol{B})+\boldsymbol{C}\) and \(\boldsymbol{A}(\boldsymbol{B}\boldsymbol{C}) = (\boldsymbol{A}\boldsymbol{B})\boldsymbol{C}\).
Commutativity of addition: \(\boldsymbol{A}+\boldsymbol{B}=\boldsymbol{B}+\boldsymbol{A}\).
Distributivity: \(\boldsymbol{A}(\boldsymbol{B}+\boldsymbol{C}) = \boldsymbol{A}\boldsymbol{B}+\boldsymbol{A}\boldsymbol{C}\) and \((\boldsymbol{A}+\boldsymbol{B})\boldsymbol{C}=\boldsymbol{A}\boldsymbol{C}+\boldsymbol{B}\boldsymbol{C}\).
The Euclidean algorithm is a method for computing the greatest common divisor of two numbers. It repeatedly replaces the larger of two numbers with a smaller number so that the pair still has the same common divisors. Eventually, one of the numbers is zero, so that the other is clearly the greatest common divisor. In its simplest form, if \(a\) and \(b\) are two numbers with \(a\) not less than \(b\), \(a\) is replaced by \(a-b\). A more efficient version immediately replaces \(a\) with the remainder when \(a\) is divided by \(b\).