A minimally configured Windows laptop

November 22, 2020 Windows No comments , , , , , ,

I’ve now installed enough that my new Windows machine is minimally functional (LaTex, Linux, and Mathematica), with enough installed that I can compile any of my latex based books, or standalone content for blog posts.  My list of installed extras includes:

  • Brother HL-2170W (printer driver)
  • Windows Terminal
  • GPL Ghostscript (for MaTeX, latex labels in Mathematica figures.)
  • Wolfram Mathematica
  • Firefox
  • Chrome
  • Visual Studio
  • Python
  • Julia
  • Adobe Acrobat Reader
  • Discord
  • OBS Studio
  • MikTeX
  • SumatraPDF
  • GVim
  • Git
  • PowerShell (7)
  • Ubuntu
  • Dropbox

Some notes:

  • On Windows, for my LaTeX work, I used to use MikTex + cygwin.  The cygwin dependency was for my makefile dependencies (gnu-make+perl).  With this new machine, I tried WSL2.  I’m running my bash shells within the new Windows Terminal, which is far superior to the old cmd.
  • Putty is no longer required.  Windows Terminal does the job very nicely.  It does terminal emulation well enough that I can even ssh into a Linux machine and use screen within my Linux session, and my .screenrc just works.  Very nice.
  • SumatraPDF is for latex reverse tex lookup.  i.e. I can double click on pdf content, and up pops the editor with the latex file.  Last time I used Sumatra, I had to configure it to use GVim (notepad used to be the default I think.)  Now it seems to be the default (to my suprise.)
  • I will probably uninstall Git, as it seems superfluous given all the repos I want to access are cloned within my bash file system.
  • I used to use GVim extensively on Windows, but most of my editing has been in vim in the bash shell.  I expect I’ll now only use it for reverse tex (–synctex) lookup editing.

WSL2 has very impressive integration.  A really nice demo of that was access of synctex lookup.  Here’s a screenshot that shows it in action:

I invoked the windows pdf viewer within a bash shell in the Ubuntu VM, using the following:

 
pjoot@DESKTOP-6J7L1NS:~/project/blogit$ alias pdfview
alias pdfview='/mnt/c/Users/peete/AppData/Local/SumatraPDF/SumatraPDF.exe'
pjoot@DESKTOP-6J7L1NS:~/project/blogit$ pdfview fibonacci.pdf

The Ubuntu filesystem directory has the fibonacci.synctex.gz reverse lookup index that Summatra is able to read. Note that this file, after unzipping, has only Linux paths (/home/pjoot/…), but Summatra is able to use those without any trouble, and pops up the (Windows executable) editor on the files after I double click on the file. This sequence is pretty convoluted:

  • Linux bash ->
  • invoke Windows pdf viewer ->
  • that program reading Linux files ->
  • it invokes a windows editor (presumably using the Linux path), and that editor magically knows the path to the Linux file that it has to edit.

Check out the very upper corner of that GVim window, where it shows the \\wsl$\Ubuntu\home\pjoot\project\blogit\fibonacci.tex path

As well as full Linux access to the Windows filesystem, we have full Windows access to the Linux filesystem.

Not all applications know how to access files with UNC paths (for example, the old crappy cmd.exe cannot), but so far all the ones I have cared about have been able to do so.

Public service announcement graffiti?

November 21, 2020 Incoherent ramblings No comments , , ,

On Wednesday night’s Tessa walk, I encountered a very large piece of public service announcement graffiti:

This is on a very wide pedestrian bridge, spanning the DVP in Riverdale.  I assume that bitchute is one of the uncensorable platforms like Dtube (a blockchain based video platform), but I haven’t actually checked it out.  I guess I’m not the only one that is annoyed that the big social media platforms have made it their policy to regulate the set of allowed opinions.  I wouldn’t have expressed myself with graffiti, but I guess that I’m not alone in my distaste for being told what I am allowed to think, or that some information is too dangerous for me to be allowed to look at it.

Deriving the nth Fibonacci number formula.

November 20, 2020 math and physics play No comments , , , ,

[If mathjax doesn’t display properly for you, click here for a PDF of this post]

My last three posts:

  1. The nth term of a Fibonacci series.
  2. More on that cool Fibonacci formula.
  3. Guessing the nth Fibonacci number formula.

were all about a cool formula for the n-th term of the Fibonacci series.  Here’s the final chapter of the story of that play.  A recap:

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

Deriving the nth Fibonacci formula.

There was a particularly unsatisfactory aspect of the guess that we made in the last post. In particular, we didn’t have any reason to guess the form of that solution, except for the fact that we already knew the answer. Now we will attempt to attack this in a more systematic fashion, so that each step along the way seems logical. First, we need to put a couple goodies in our toolbox.

Definition 1.1: Discrete sum.

Given a set of discrete values \( \setlr{G_a, G_{a+1}, \cdots, G_n } \) we define a discrete sum of \( n – a + 1 \) of these terms as \( F_n \)
\begin{equation}\label{eqn:fibonacciblog:1540}
F_n = \sum_{k = a}^n G_k + C,
\end{equation}
where \( C \) is an arbitrary boundary value constant.

Definition 1.2: Difference operators.

Define a backwards difference operator \( \Delta \), operating on \( X_n \) as
\begin{equation}\label{eqn:fibonacciblog:1560}
\Delta X_n = X_n – X_{n-1}.
\end{equation}

The difference operator is a discrete analogue of a differential operator. It is also possible to define a (forward) difference operator as \( \Delta X_n = X_{n+1} – X_{n} \), but the choice is arbitary, and we can find the same results either way.

Lemma 1.1: Antidifference of discrete sum.

Given a sum \( F_n \) of the form \ref{eqn:fibonacciblog:1540}, the difference operation is just the highest \( n \) term of the sum
\begin{equation}\label{eqn:fibonacciblog:1580}
\Delta F_n = G_n.
\end{equation}

Start proof:

\begin{equation}\label{eqn:fibonacci:960}
\Delta F_n =
\sum_{k = a}^n G_k + C
– \lr{ \sum_{k = a}^{n-1} G_k + C }
= G_n.
\end{equation}

End proof.

Computing differences is pretty easy. What we want to do is the inverse operation (analogous to integration), where we find a closed form representation of \( F_n \) given a difference equation \( \Delta F_n = G_n \). Just as we can compute antiderivatives for \( x^n \), we may do the same for \( n^k \) antidifferences, but the results are messier. The first few such antidifferences are

Theorem 1.1: Antidifferences for powers of \(n\).

\begin{equation}\label{eqn:fibonacciblog:1600}
\begin{aligned}
1 &= \Delta n \\
n &= \Delta \lr{ \frac{n}{2}\lr{ n + 1} } \\
n^2 &= \Delta \lr{ \frac{n}{6}\lr{2 n + 1}\lr{n + 1} } \\
n^3 &= \Delta \lr{ \frac{n^2}{4}\lr{n + 1}^2 }.
\end{aligned}
\end{equation}

Start proof:

The \( \Delta n \) identity is easily verified
\begin{equation}\label{eqn:fibonacci:1000}
\Delta n = n – (n-1) = 1.
\end{equation}
For higher orders it is a bit tedious to verify directly, but we can iteratively build up those results by evaluating the difference operator on each of the powers of \( n \).
\begin{equation}\label{eqn:fibonacci:660}
\begin{aligned}
\Delta n^2
&= n^2 – (n-1)^2 \\
&= n^2 – (n^2 – 2 n + 1) \\
&= 2 n – 1, \\
&= 2 n – \Delta n.
\end{aligned}
\end{equation}
Because the difference operator is linear, we can rearrange to find
\begin{equation}\label{eqn:fibonacci:1020}
\Delta \lr{ n^2 + n } = 2 n.
\end{equation}
Dividing through by \( 2 \) and factoring out an \( n \), recovers the desired result.

For the next power, we have
\begin{equation}\label{eqn:fibonacci:680}
\begin{aligned}
\Delta n^3
&= n^3 – (n-1)^3 \\
&= n^3 – (n^3 – 3 n^2 + 3 n – 1) \\
&= 3 n^2 – 3 n + 1 \\
&= 3 n^2 – 3 \Delta \frac{n}{2}\lr{ n + 1 } + \Delta n,
\end{aligned}
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:1040}
\begin{aligned}
3 n^2
&=
\Delta \lr{n} \lr{ n^2 + \frac{3}{2}\lr{ n + 1} – 1 } \\
&=
\Delta \frac{n}{2} \lr{ 2 n^2 + 3\lr{ n + 1} – 2} \\
&=
\Delta \frac{n}{2} \lr{ 2 n^2 + 3 n + 1 } \\
&=
\Delta \frac{n}{2} \lr{ 2 n + 1}\lr{ n + 1 }
\end{aligned}
\end{equation}
Dividing through by \( 3 \) recovers the desired result.

The final result is left to the reader. It can be derived or verified easily with a couple lines of Mathematica code.

End proof.

Problem: Sum some series.

Find the sums \( \sum_{k = 1}^n k^m \), for \( m = 1, 2, 3 \).

Answer

  • \( m = 1 \). This is the (probably apocryphal) sum of Gauss’s grade school classroom:
    \begin{equation}\label{eqn:fibonacci:1060}
    F_n = \sum_{k = 1}^n k = 1 + 2 + \cdots n,
    \end{equation}
    satisfying
    \begin{equation}\label{eqn:fibonacci:1080}
    \begin{aligned}
    \Delta F_n
    &= F_n – F_{n-1} \\
    &=
    (n + (n-1) + \cdots + 1)

    ((n-1) + \cdots + 1) \\
    &= n \\
    &= \Delta \frac{n}{2}(n + 1).
    \end{aligned}
    \end{equation}
    We must have
    \begin{equation}\label{eqn:fibonacci:1100}
    F_n = \frac{n}{2}\lr{ n + 1} + C.
    \end{equation}
    To fix \( C \) consider \( F_1 \)
    \begin{equation}\label{eqn:fibonacci:1180}
    F_1 = \inv{2}(1 + 1) + C = 1,
    \end{equation}
    so \( C = 0 \), so we find Gauss’s summation formula
    \begin{equation}\label{eqn:fibonacci:1200}
    \sum_{k = 1}^n k = \frac{n}{2}\lr{ n + 1},
    \end{equation}
    as expected.
  • \( m = 2 \). Now let’s do the sum of squares
    \begin{equation}\label{eqn:fibonacci:1120}
    F_n = \sum_{k = 1}^n k^2,
    \end{equation}
    for which we have
    \begin{equation}\label{eqn:fibonacci:1140}
    \Delta F_n = n^2 = \Delta \frac{n}{6}( 2 n + 1 )(n+1),
    \end{equation}
    so
    \begin{equation}\label{eqn:fibonacci:1160}
    F_n = \frac{n}{6}( 2 n + 1 )(n+1) + C.
    \end{equation}
    Clearly \( C = 0 \) satisfies the boundary condition, leaving
    \begin{equation}\label{eqn:fibonacci:1220}
    \sum_{k = 1}^n k^2 =
    \frac{n}{6}( 2 n + 1 )(n+1).
    \end{equation}
  • \( m = 3 \). We see the pattern, so for the sum of cubes, we can just write down the answer
    \begin{equation}\label{eqn:fibonacci:1240}
    \sum_{k = 1}^n k^3 =
    \frac{n^2}{4}\lr{n + 1}^2
    .
    \end{equation}

Now that we have some basic comfort with the ideas of difference equations, and their solutions,
let’s get back to the Fibonacci problem. In that case, we have
\begin{equation}\label{eqn:fibonacci:1260}
F_n = F_{n-1} + F_{n-2}.
\end{equation}
Stated as a difference equation, this is
\begin{equation}\label{eqn:fibonacci:1280}
\Delta F_n = F_{n-2}.
\end{equation}
Before tackling the Fibonacci problem, let’s try one that slightly simpler.

Problem: A simpler problem.

Solve \( \Delta F_n = F_{n-1} \), where \( F_0 = 0, F_1 = 1 \).

Answer

The problem to solve is just
\begin{equation}\label{eqn:fibonacci:1300}
F_n = 2 F_{n-1}.
\end{equation}
This sequence is \( \setlr{ 1, 2, 4, 8, \cdots } \), so we can solve it by inspection, and the answer is just \( F_n = 2^{n-1} \). We want inspiration for the Fibonacci problem, so let’s pretend that we can’t see the answer, but that we can guess something close, and see if it works. Namely, let’s guess:
\begin{equation}\label{eqn:fibonacci:1320}
F_n = \alpha a^n + C.
\end{equation}
If we plug this trial solution into our difference equation, we get
\begin{equation}\label{eqn:fibonacci:1340}
\begin{aligned}
\alpha a^{n-1} + C
&=
\Delta F_n \\
&= \alpha \lr{ a^n – a^{n-1} } \\
&= \alpha a^{n-1} \lr{ a – 1 }
\end{aligned}
\end{equation}
This can be satisfied by setting \( C = 0 \) and \( a – 1 = 1 \), or \( a = 2 \), as we already knew. To fix the constant \( \alpha \) we utilize our boundary constraints, namely
\begin{equation}\label{eqn:fibonacci:1400}
F_1 = 1 = \alpha 2
\end{equation}
so \(\alpha = 1/2 \).

Compared to just seeing the answer, the procedure above was a lot of work. However, a side effect of this work is discovery of a guessing strategy that is somewhat like using \( f(t) = e^{s t} \) to generate a characteristic equation when solving a differential equation. For a difference equation of this form, it appears we can substitute \( F_n = \alpha a^n + C \) and use the differences to determine the values of \( \alpha, a, C \). Now let’s try this with the Fibonacci difference equation.

Problem: Find a solution to the Fibonacci difference equation.

Without worrying about boundary constraints, find the solutions to \( \Delta F_n = F_{n-2} \), using a trial solution of \( F_n = \alpha a^n \).

Answer

Inserting our trial solution, we have
\begin{equation}\label{eqn:fibonacci:1420}
\begin{aligned}
\alpha a^n
&=
F_n \\
&= F_{n-1} + F_{n-2} \\
&= \alpha \lr{ a^{n-1} + a^{n-2} } \\
&= \alpha a^{n-2} \lr{ a + 1 },
\end{aligned}
\end{equation}
so our “characteristic equation” is
\begin{equation}\label{eqn:fibonacci:1440}
a + 1 = a^2.
\end{equation}
Completing the square yields
\begin{equation}\label{eqn:fibonacci:1460}
\lr{ a – \inv{2} }^2 = 1 + \inv{4},
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:1480}
a = \inv{2} \pm \frac{\sqrt{5}}{2}.
\end{equation}
Bamn. There’s our golden ratio, and it’s buddy!
We find that
\begin{equation}\label{eqn:fibonacci:1500}
F_n = \alpha \lr{\frac{1 \pm \sqrt{5}}{2} }^n,
\end{equation}
are solutions to the difference equation \ref{eqn:fibonacci:1280}.

Since we have a second order difference equation, we need a superposition of both solutions to try to satisfy the boundary conditions. In particular, we want to find the constants
\begin{equation}\label{eqn:fibonacci:1520}
F_n =
\alpha_{+} \lr{\frac{1 + \sqrt{5}}{2} }^n
+
\alpha_{-} \lr{\frac{1 – \sqrt{5}}{2} }^n + C.
\end{equation}
However, we already did this when we guessed used \( F_n = \alpha a^n + \beta b^n \) as a trial solution. When we did that, it was just to see if we could find the end result, knowing only the structure of the solution, but none of the specific constants. Now we have justified why that was a reasonable trial solution, since exactly this structure follows naturally from the difference equation itself.

This train of thought, makes me want to dig out my little Dover book on difference equations [1] that I’ve had since I was a kid. I think I only worked through the first chapter of that book. I have a lot of little sad neglected Dover books on mathematics and physics that I bought super cheap at the World’s Biggest Bookstore when I was back in school. It will be interesting to see how to tackle problems such as this, in a still more systematic fashion.

References

[1] Hyman Levy and Freda Lessman. Finite difference equations. Courier Corporation, 1992.

Pronunciation and origin of my name.

November 19, 2020 Incoherent ramblings 3 comments , , , , , ,

The question of how to pronounce my names is frequently asked.

Joot isn’t Dutch, but is Estonian.  I’m not sure what sort of linguistic crossover there is between the two languages, if any(**).

Dad was Estonian, and he wanted us all to have Estonian spellings of our names (Peeter, Krista, Erik, Karin.)  Dad pronounced my name with the standard North American pronunciation for Peter.  However, my Vanaema (grandmother) pronounced Peeter with enunciation of all the e’s in a way that I can’t actually vocalize myself.  Estonian words have lots of doubled vowels (google finds me Kuulilennuteetunneliluuk as an example (a nice long palindrome (*))).  Unlike doubled vowels in English, if they are there, it’s because they should all be pronounced.

If somebody named Peter says that I spell my name wrong, I rebut by calling them pet-er, since the long e requires vowel doubling per English spelling conventions (i.e. my name is spelled correctly, but their spelling is wrong.)

My last name Joot is pronounced as like “Yoat”, like oat. I can’t recall the subtleties of how Vanaema pronounced Joot, but I’m sure she also somehow enunciated both o’s.  When I was a kid, I was very inflexible about the pronunciation of my name, and insisted on “Yoat”, not “Jewt”.  That inflexibility was too much work, and I mellowed out considerably over time.  I now flexible and respond to anything that approximates any possible pronunciation that I can recognize, and no longer correct anybody.

People correct the spelling of names for me all the time, as they couldn’t possibly be spelled right as is.

 

(*)

Originally I thought I saw an article that said that kuulilennuteetunneliluuk also meant palindrome, but cannot find that anymore.  Instead, googling this word, I find it translated as “the hatch a bullet flies out of when exiting a tunnel“.  If kuulilennuteetunneliluuk actually meant palindrome, that would be the most amazing word for palindrome in any language!  I’m very sad that I appear to have gotten the meaning wrong.  My hope for the future of linguistics, is that Estonians will start using kuulilennuteetunneliluuk as a word for palindrome, giving it a second meaning through popular use.  If that trend can be started, eventually the Estonian language has the best word for palindrome in any language.

 

(**)

On the other hand, Dad said he could understand most of Finnish when spoken (but said that Finns couldn’t understand him.)  I’m guessing that this means Finnish was probably a root of Estonian, but dialect could also be a factor, as I’ve since met Finns that said they could understand some Estonian.  Dad talked about the dialect variation from Estonian town to town at the beginning of the 1900’s, which was apparently so bad that understanding somebody from a few towns away could be difficult.  By the time he was born, radio was starting to obliterate that dialect variation.  He also wouldn’t have heard that dialect variation first hand, since he escaped the Soviet invasion of Estonia with my grandmother when he was only 3.  His refugee journey started in Finland (who had a pact with the Soviets to kick out refugees after some fixed time (i.e.: the Soviet’s said “kick out refugees, or else we’ll invade you too!”)   After a few years in Sweden, Dad and Vanaema eventually landed in Canada.

EBCDIC, thou art evil.

November 18, 2020 Mainframe No comments , , ,

Here’s a bit of innocuous code. It was being compiled with gcc -fexec-charset=1047, so all the characters and strings were being treated as EBCDIC. For example ‘0’ = ‘\xF0’.

    if (c >= '0' && c <= '9')                                                                                                         
         c -= '0';                                                                                                                    
    else if (c >= 'A' && c <= 'Z')                                                                                                    
         c -= 'A' - 10;                                                                                                               
    else if (c >= 'a' && c <= 'z')                                                                                                    
         c -= 'a' - 10;                                                                                                               
    else                                                                                                                              
         break;         

Specifying the charset is not enough to port this code to the mainframe.  The problem is that EDCDIC is completely braindead, and DOESN’T PUT THE FRIGGEN LETTERS TOGETHER!

The letters are clustered in groups:

  • a-i
  • j-r
  • s-z
  • A-I
  • J-R
  • S-Z

with whole piles of crap between each range of characters, so comparisons like c >= ‘A’ && c <= ‘Z’ are useless, as are constructions like (c-‘A’-10) since c in J-R or S-Z will break that.

Now I have a big hunt and destroy task ahead of me.  I can fix this code, but where else are problems like this lurking!

Guessing the nth Fibonacci number formula

November 17, 2020 math and physics play No comments , , , ,

[If mathjax doesn’t display properly for you, click here for a PDF of this post]

My last two posts:

  1. The nth term of a Fibonacci series.
  2. More on that cool Fibonacci formula.

were both about a cool formula for the n-th term of the Fibonacci series.  Looks like I’m not done playing with this beastie.  A recap:

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

 

The guess.

We can rearrange the formula for the nth Fibonacci number as a difference equation
\begin{equation}\label{eqn:fibonacci:260}
F_n – F_{n-1} = F_{n-2}.
\end{equation}
This is a second order difference equation, so my naive expectation is that there are two particular solutions involved. We know the answer, so it’s not too hard to guess that the particular form of the solution has the following form
\begin{equation}\label{eqn:fibonacci:280}
F_n = \alpha a^n + \beta b^n.
\end{equation}
Given this guess, can we take some of the magic out of the formula, by just solving for \( \alpha, \beta, a, b \)? Let’s try that
\begin{equation}\label{eqn:fibonacci:300}
F_0 = \alpha + \beta = 0,
\end{equation}
\begin{equation}\label{eqn:fibonacci:320}
\begin{aligned}
F_1 &= \alpha a + \beta b \\
&= \alpha \lr{ a – b } \\
&= 1,
\end{aligned}
\end{equation}
and
\begin{equation}\label{eqn:fibonacci:340}
\begin{aligned}
F_n
&= F_{n-1} + F_{n-2} \\
&=
\alpha \lr{ a^{n-1} + a^{n-2} }
-\alpha \lr{ b^{n-1} + b^{n-2} } \\
&=
\alpha a^{n-2} \lr{ 1 + a }
-\alpha b^{n-2} \lr{ 1 + b },
\end{aligned}
\end{equation}
so
\begin{equation}\label{eqn:fibonacci:360}
\begin{aligned}
a^2 &= a + 1 \\
b^2 &= b + 1.
\end{aligned}
\end{equation}
If we complete the square we find
\begin{equation}\label{eqn:fibonacci:380}
\lr{ a – \inv{2} }^2 = 1 + \inv{4} = \frac{5}{4},
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:400}
a, b = \inv{2} \pm \frac{\sqrt{5}}{2}.
\end{equation}
Out pop the golden ratio and it’s complement. Clearly we need to pick alternate roots for \( a \) and \( b \) or else we’d have zero for every value of \( n > 0 \). Suppose we pick the positive root for \( a \), then to find the scaling constant \( \alpha \), we just compute
\begin{equation}\label{eqn:fibonacci:420}
\begin{aligned}
1
&=
\alpha \lr{ \frac{ 1 + \sqrt{5}}{2} – \frac{ 1 – \sqrt{5} }{2} } \\
&= \alpha \sqrt{5},
\end{aligned}
\end{equation}
so our system \ref{eqn:fibonacci:280} has the solution:
\begin{equation}\label{eqn:fibonacci:520}
\begin{aligned}
a &= \frac{1 + \sqrt{5}}{2} \\
b &= \frac{1 – \sqrt{5}}{2} \\
\alpha &= \inv{\sqrt{5}} \\
\beta &= -\inv{\sqrt{5}}.
\end{aligned}
\end{equation}

We now see a path that will systematically lead us from the Fibonacci difference equation to the final result, and have only to fill in a few missing steps to understand how this could be discovered from scratch.

Motivating the root-fives.

I showed this to Sofia, and she came up with a neat very direct way to motivate the \( \sqrt{5} \). It follows naturally (again knowing the answer), by assuming the Fibonacci formula has the following form:
\begin{equation}\label{eqn:fibonacci:440}
F_n = \inv{x} \lr{
\lr{ \frac{1 + x}{2}}^n

\lr{ \frac{1 – x}{2}}^n
}.
\end{equation}
We have only to plug in \( n = 3 \) to find
\begin{equation}\label{eqn:fibonacci:460}
\begin{aligned}
2 x
&= \inv{4} \lr{ 1 + 3 x + 3 x^2 + x^3 – \lr{ 1 – 3 x + 3 x^2 – x^3 } } \\
&= \inv{2} \lr{ 3 x + x^3 },
\end{aligned}
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:480}
8 = 3 + x^2,
\end{equation}
so
\begin{equation}\label{eqn:fibonacci:500}
x = \pm \sqrt{5}.
\end{equation}
Again the \( \sqrt{5} \)’s pop out naturally, taking away some of the mystery of the cool formula.

More on that cool Fibonacci formula

November 15, 2020 math and physics play No comments

[If mathjax doesn’t display properly for you, click here for a PDF of this post]

In my previous post, I explored the following cool formula for the nth term of the Fibonacci series. In this post, I’ll show why there are no square root fives after evaluation. A recap:

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

How the square root fives cancel out.

One of the interesting things in this Fibonacci formula, is the \( \sqrt{5} \)’s that are all over the place, while the formula represents only integer values. Expanding the formula in binomial series shows us exactly why those terms all vanish. Consider the first few values of \( n \) explicitly.
\begin{equation}\label{eqn:fibonacci:160}
\begin{aligned}
F_1
&= \frac{ 1 + \sqrt{5} – \lr{ 1 – \sqrt{5} } }{ 2^1 \sqrt{5} } \\
&= \frac{ 2 \sqrt{5} }{ 2^1 \sqrt{5} } \\
&= 1,
\end{aligned}
\end{equation}
\begin{equation}\label{eqn:fibonacci:180}
\begin{aligned}
F_2
&= \frac{ 1 + 2 \sqrt{5} + 5 – \lr{ 1 – 2 \sqrt{5} + 5 } }{ 2^2 \sqrt{5} } \\
&= \frac{ 4 \sqrt{5} }{ 2^2 \sqrt{5} } \\
&= 1,
\end{aligned}
\end{equation}
\begin{equation}\label{eqn:fibonacci:200}
\begin{aligned}
F_3
&= \frac{ 1 + 3 \sqrt{5} + 3 (5) + \sqrt{5} 5 – \lr{ 1 – 3 \sqrt{5} + 3(5) – \sqrt{5} 5 } }{ 2^3 \sqrt{5} } \\
&= \frac{ 2 \lr{ 3 \sqrt{5} + \sqrt{5} 5 } }{ 2^3 \sqrt{5} } \\
&= \frac{ 3 + 5 }{ 2^2 } \\
&= 2.
\end{aligned}
\end{equation}
In the general case, we have
\begin{equation}\label{eqn:fibonacci:220}
\begin{aligned}
2^n \sqrt{5} F_n
&=
\sum_{k = 0}^n
\binom{n}{k}
{\sqrt{5}}^k

\sum_{k = 0}^n \binom{n}{k} (-\sqrt{5})^k \\
&=
2 \sum_{1 \le k \le n, \mbox{$k$ is odd}} \binom{n}{k} (\sqrt{5})^k \\
&=
2 \sqrt{5} \sum_{m = 0}^{\lfloor (n-1)/2 \rfloor} \binom{n}{2 m + 1} 5^m,
\end{aligned}
\end{equation}

so (for any \( n > 0 \)),
\begin{equation}\label{eqn:fibonacci:240}
F_n =
\inv{2^{n-1}} \sum_{m = 0}^{\lfloor (n-1)/2 \rfloor } \binom{n}{2 m + 1} 5^m.
\end{equation}
Since only the odd powers of \( \sqrt{5} \) in the binomial expansions survive, the root in the basement is obliterated every time, leaving only integers upstairs, and a power of two factor downstairs. It is still somewhat remarkable seeming that there is always a perfect cancellation of all the factors of two in the basement.

The nth term of a Fibonacci series.

November 13, 2020 math and physics play 3 comments , , , ,

[If mathjax doesn’t display properly for you, click here for a PDF of this post.]

I’ve just started reading [1], but already got distracted from the plot by a fun math fact. Namely, a cute formula for the nth term of a Fibonacci series. Recall

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

We can quickly find that the series has values \( 0, 1, 1, 2, 3, 5, 8, 13, \cdots \). What’s really cool, is that there’s a closed form expression for the nth term in the series that doesn’t require calculation of all the previous terms.

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

This is a rather miraculous and interesting looking equation. Other than the \(\sqrt{5}\) scale factor, this is exactly the difference of the nth powers of the golden ratio \( \phi = (1+\sqrt{5})/2 \), and \( 1 – \phi = (1-\sqrt{5})/2 \). That is:
\begin{equation}\label{eqn:fibonacci:60}
F_n = \frac{\phi^n – (1 -\phi)^n}{\sqrt{5}}.
\end{equation}

How on Earth would somebody figure this out? According to Tattersal [2], this relationship was discovered by Kepler.

Understanding this from the ground up looks like it’s a pretty deep rabbit hole to dive into. Let’s save that game for another day, but try the more pedestrian task of proving that this formula works.

Start proof:

\begin{equation}\label{eqn:fibonacci:80}
\begin{aligned}
\sqrt{5} F_n
&=
\sqrt{5} \lr{ F_{n-2} + F_{n-1} } \\
&=
\phi^{n-2} – \lr{ 1 – \phi}^{n-2}
+ \phi^{n-1} – \lr{ 1 – \phi}^{n-1} \\
&=
\phi^{n-2} \lr{ 1 + \phi }
-\lr{1 – \phi}^{n-2} \lr{ 1 + 1 – \phi } \\
&=
\phi^{n-2}
\frac{ 3 + \sqrt{5} }{2}
-\lr{1 – \phi}^{n-2}
\frac{ 3 – \sqrt{5} }{2}.
\end{aligned}
\end{equation}
However,
\begin{equation}\label{eqn:fibonacci:100}
\begin{aligned}
\phi^2
&= \lr{ \frac{ 1 + \sqrt{5} }{2} }^2 \\
&= \frac{ 1 + 2 \sqrt{5} + 5 }{4} \\
&= \frac{ 3 + \sqrt{5} }{2},
\end{aligned}
\end{equation}
and
\begin{equation}\label{eqn:fibonacci:120}
\begin{aligned}
(1-\phi)^2
&= \lr{ \frac{ 1 – \sqrt{5} }{2} }^2 \\
&= \frac{ 1 – 2 \sqrt{5} + 5 }{4} \\
&= \frac{ 3 – \sqrt{5} }{2},
\end{aligned}
\end{equation}
so
\begin{equation}\label{eqn:fibonacci:140}
\sqrt{5} F_n = \phi^n – (1-\phi)^n.
\end{equation}

End proof.

References

[1] Steven Strogatz and Don Joffray. The calculus of friendship: What a teacher and a student learned about life while corresponding about math. Princeton University Press, 2009.

[2] James J Tattersall. Elementary number theory in nine chapters. Cambridge University Press, 2005.

Building my new “garage”

November 12, 2020 Home renos No comments , , , , , , , ,

I managed to sneak in a day off of work (split over two days), and built a space for all the tools that I used to keep in my double car garage. We’ve been in the new downtown house now for a year, and had most of the old house cleared out except for the garage. You can accumulate a lot of stuff in 20 years of home ownership, and moving from a house with a double car garage to a no-garage house, was quite a challenge. After many panic-demic induced delays, we eventually finished the renos on the old house, and sold it.  I’m really enjoying the new neighbourhood, where I can walk to just about everything I need, but there’s a few things that I miss from the old house:

  1. The garage!
  2. Parking spaces (6 not including the garage — I won’t miss shovelling that driveway!)
  3. The pool.
  4. The hottub.

However, number 1 — the garage, has been the most challenging.  We’ve had stuff from the garage all over the house, in the sheds in the back yard, and a whole lot of it on the back deck under a tarp.  We replaced our washer and dryer with a stacking unit to maximize the space, and I’ve now built some heavy duty shelves next to it for all the tools and toolboxes:

I’ve drilled three rows of holes, each 2″ apart, so that I can adjust the height of the shelves.  I’ve fixed the middle and the top shelf for stability.  I also tacked in the shelf on the bottom with a couple screws and should put some sort of fixed back brace, or a bottom piece so that the side supports cannot spread.  That will have to be later, since I’m out of wood (I had to scrounge a bit and my top most adjustable shelf is not big enough — so that one is temporary too.)

We may redo the plumbing on the other side of the washer dryer too. We have some long multiple hose runs, one of which leaked at one point, because of a degraded washer.   It would be better to put one of those tidy washer/dryer plumbing boxes right in the wall near the washer dryer instead of the current leak ready to happen system.  That would allow for eliminating all the too-long hoses, and give us a chance to fully optimize the long laundry closet for storage.  That and the opposite storage unit is the closest that we will get to a “garage” in the new house.

In the 2o year accumulation of stuff, I have a whole lot of tools that actually need to go.  Some of these were dad’s, and I didn’t have the heart to toss them, but it would be better to find them homes with people that will actively use them.  At the bare minimum, some of these excess tools should go to people who actually have storage space to be hoarders, something that we can no longer do.  Now that I have things arrayed in an accessible fashion, it’s time for the big sort, and then the purge after the sort.

A new computer for me this time.

November 5, 2020 Incoherent ramblings 2 comments , , , , , , , , , ,

It’s been a long long time, since I bought myself a computer.  My old laptop is a DELL XPS, was purchased around 2009:

Since purchasing the XPS lapcrusher, I think that I’ve bought my wife and all the kids a couple machines each, but I’ve always had a work computer that was new enough that I was able to let my personal machine slide.

Old system specs

Specs on the old lapcrusher:

  • 19″ screen
  • stands over 2″ tall at the back
  • Intel Core I3, 64-bit, 4 cores
  • 6G Ram
  • 500G hard drive, no SSD.

My current work machine is a 4yr old mac (16Mb RAM) and works great, especially since I mainly use it for email and as a dumb terminal to access my Linux NUC consoles using ssh.  I have some personal software on the mac that I’d like to uninstall, leaving the work machine for work, and the other for play (Mathematica, LaTex, Julia, …).

I’ll still install the vpn software for work on the new personal machine so that I can use it as a back up system just in case.  Last time I needed a backup system (when the mac was in the shop for battery replacement), I used my wife’s computer.  Since Sofia is now mostly working from home (soon to be always working from home), that wouldn’t be an option. Here’s the new system:

New system specs

This splurge is a pretty nicely configured, not top of the line, but it should do nicely for quite a while:

  • Display: 15.6″ Full HD IPS | 144HZ | 16:9 | Operating System: Win 10
  • Processor: Intel Core i7-9750H Processor (6 core)
  • RAM Memory: XPG 32GB 2666MHz DDR4 SO-DIMM (64GB Max)
  • Storage: XPG SX8200 1TB NVMe SSD
  • Graphics: NVIDIA GeForce GTX 1660Ti 6GB
  • USB3.2 Gen 2 x 1 | USB3.2 Gen 2 x 2 | Thunderbolt 3.0 x 1 (REAR)| HDMI x 1 (REAR)
  • 4.08lbs

The new machine has a smaller screen size than my old laptop, but the 19″ screen on the old machine was really too big, and with modern screens going so close to the edge, this new one is pretty nice (and has much higher resolution.)  If I want a bigger screen, then I’ll hook it up to an external monitor.

On lots of RAM

It doesn’t seem that long ago when I’d just started porting DB2 LUW to 64bit, and most of the “big iron” machines that we got for the testing work barely had more than 4G of ram each.  The Solaris kernel guys we worked with at the time told me about the NUMA contortions that they had to use to build machines with large amounts of RAM, because they couldn’t get it close enough together because of heat dissipation issues.  Now you can get a personal machine for $1800 CAD with 32G of ram, and 6G of video ram to boot, all tossed into a tiny little form factor!  This new machine, not even counting the video ram, has 524288x the memory of my first computer, my old lowly C64 (I’m not counting the little Radio Shack computer that was really my first, as I don’t know how much memory it had — although I am sure it was a whole lot less than 64K.)

C64 Nostalgia.

Incidentally, does anybody else still have their 6402 assembly programming references?  I’ve kept mine all these years, moving them around house to house, and taking a peek in them every few years, but I really ought to toss them!  I’m sure I couldn’t even give them away.

Remember the zero page addressing of the C64?  It was faster to access because it only needed single byte addressing, whereas memory in any other “page” (256 bytes) required two whole bytes to address.  That was actually a system where little-endian addressing made a whole lot of sense.  If you wanted to change assembler code that did zero page access to “high memory”, then you just added the second byte of additional addressing and could leave your page layout as is.

Windows vs. MacOS

It’s been 4 years since I’ve actively used a Windows machine, and will have to relearn enough to get comfortable with it again (after suffering with the transition to MacOS and finally getting comfortable with it).  However, there are some new developments that I’m gung-ho to try, in particular, the new:

With WSL, I wonder if cygwin is even still a must have?  With windows terminal, I’m guessing that putty is a thing of the past (good riddance to cmd, that piece of crap.)