# Recursive functions and the Fibonacci numbers

My son asked me about recursive functions yesterday morning and I showed him Dan Anderson’s online tutorial:

Even though Dan’s resource covers just about everything ( ha ha ) I thought maybe there was still something we could discuss this morning. So, I talked about the Fibonacci numbers.

First we did a quick introduction:

Next I had both boys pick their own recursively defined functions – and I got pretty lucky with the choices!

Now I showed them one approach you can use to solve these recursive equations. For the purposes of showing this idea to kids I’m not worried about the background details, but rather using the idea for some basic exponent review. (and, sorry, I’m a little careless around 1:30, but luckily catch my error fairly quickly before the whole video is derailed):

Now that we found the neat relationship between Fibonacci numbers and the golden ratio, we finished the calculation and found an explicit formula for the Fibonacci numbers:

We finished up with by checking our new formula on Mathematica. I also showed them a lucky coincidence from twitter yesterday that relates to this project. That coincidence involved this problem posted by Alexander Bogonmlny:

And this portion of the solution posted by Nassim Taleb:

(unfortunately as I tried to zoom in on Taleb’s solution while filming the camera got way out of focus, so close your eyes for the last few minutes of this video ðŸ˜¦ ).

Even if the ideas for finding the explicit solution to these recursive equations is a bit advanced, I still think this is a neat topic for kids to see. It certainly is a fun way to get some nice algebra review.

# A Robert Talbert inspired conversation about Fibonacci numbers

Saw this interesting tweet from Robert Talbert yesterday:

The whole lesson is really interesting read. I decided to try out one small piece of it with the boys today – which Fibonacci numbers are even. The idea was to hear how they would approach “proving” that every third number in the list was even.

Here’s what my older son had to say – one interesting thing in this discussion was his thoughts about the proportion of the even and odd Fibonacci numbers. The confusing idea here is that both sets are infinite. I put off the details of that discussion for another day:

And here’s my younger son – he picks up on the two odds, one even pattern and has a pretty good explanation of why the pattern continues:

So, a fun little exercise. It is always interesting to me to hear the language that kids use to describe advanced mathematical ideas.

# Another really neat problem from James Tanton

Last week James Tanton posted this interesting problem on Twitter:

It was especially interesting to me because it is closely related to one of my earliest experiences with “advanced” math.

My high school in Omaha had an incredible math department led by an amazingly gifted math teacher, Mr. Waterman. He taught a special class over the lunch hour – Enrichment Math – where kids from ranging from freshmen to seniors would study math that is normally not part of high school curriculum. The year before I came to high school the unquestioned leader of that class, Anita Barnes, had graduated and became the 3rd student from our school in 5 years to receive a full ride math scholarship to Washington University.

During one of the college breaks she came back to give a lecture on recurrence relations in which she showed how to write down an formula for the nth Fibonacci number. It may as well have been magic, but that was one of the first times I saw the incredible power of math first hand.

Tanton’s problem was a happy reminder of the lecture that Anita all those years ago (1987 if you must know!), and I thought it would be really fun to walk through the problem with the boys.

We started by just talking through the problem to make sure that they both understood what was being asked. They both recognized that $(1 + \sqrt{2})$ was irrational and thought that the irrationality of the number would come into play somehow in this problem.

The next step was to head to the computer to see what powers of $(1 + \sqrt{2})$ look like when you write them as decimals. It takes a little while for the pattern to emerge, but the boys are able to pick up on the pattern after looking at the first 10 powers.

After getting an idea that we may indeed eventually run into one million 9’s after the decimal point, we go back to the board to talk about why. In this video I introduce the boys to the surprising role that the number $(1 - \sqrt{2})$ plays in our problem. This video has a little unexpected detour where we talk about multiplying two negative numbers, so that’s why it is a little long.

Now that we’ve understood a little bit about $(1 - \sqrt{2})$ we head back to the computer to first understand this number a little better and then to see an amazing pattern formed by combining powers of $(1 + \sqrt{2})$ and $(1 - \sqrt{2})$. Understanding this pattern provides a neat way to solve Tanton’s problem:

Now that we’ve calculated the first few numbers in the list of $(1 + \sqrt{2})^n + (1 - \sqrt{2})^n$ we head back to the board to see if we can see any patterns at all in this new list. It was fun to see that they did manage to find the pattern by working together.

Having found the pattern, I show them how to write a formula that describes that pattern. If we can prove that our formula is correct (which we do not do, btw) we can understand why our list will only ever have integers, and then why powers of $(1 + \sqrt{2}$ will eventually get as close to an integer as we like. This is the math that Anita explained to our Enrichment Math class in her 1987 guest lecture:

Finally, it would be a shame to have gone through all of this math without mentioning the Fibonacci numbers. We take a few moments to calculate the first few Fibonacci numbers and then I show the boys the formula involving $\sqrt{5}$ that describes this sequence.

All in all a fun way for the boys to see (and participate in) some neat math. Also a nice walk down memory lane for me.