Where to learn how numbers work?

Question

I have known very very basic math (basic arithmetic, fractions and exponents). I have never properly learned math in high school because my math teachers aren't use to teaching blind students.

But now I am reading a programming book (Structure and interpretation of computer programs) that provide many mathematical programs. Some formulas are:

Note: I wrote them like pseudocode the way I understand them in the programs. Both functions are recursive.

Finding the Fibonacci Sequence: real mathematical formula here https://mitpress.mit.edu/sicp/chapter1/node13.html

fib(n) = fib(n-1)+fib(n-2)

Exponentiation with successive squaring: Real mathematical formula here https://mitpress.mit.edu/sicp/chapter1/node15.html

if n is 0, return 1
if n is even, find exponents of (b^(n / 2))^2
if n is odd,          (b * (find exponents of  b^(n - 1)))

Now, I fully understand what they do and how they do. I can write them in any programming language I know, I can memorise the algorithm in my head to quickly find the next fib or what is 2^1000 quickly just by knowing the formula. But I absolutely don't know how those solutions are created (E.G. I think multiplications are repeated addition and division is repeated subtraction). That is, I really don't know why the algorithms above are correct. What branch of mathematics do I need to find how the solutions above is found?

Answer 1

I don't think this is the answer you are looking for, but it might still be helpful. I will give you some comments on some general aspects and I will give you one recommendation. I will let other people focus on the Fibonacci sequence that you specifically ask about.

You say (in the comments) that you want to know how formulas are derived. You don't just want to know what the formula is, but why it looks the way it does. For this specifically I would point out two things.

1. Some formulas are a matter of definition. With the Fibonacci sequence the "formula" is defined that way. There are all kinds of relations to the real world that make it clear that this sequence of numbers is "interesting". And that is how it often is. A formula can be a matter of definition, but it can be motivated be the world around us. How this happens in general is probably to broad to get into here.

2. Other formulas are a matter of relating things that have already been defined. Here the formula will have a proof justifying that the formula is true. The proof will, of course, depend on what you are trying to prove. So, if you come across a formula you can ask what the proof for the formula is.

One helpful branch of mathematics that you might find interesting is the area of (abstract) algebra. Here we study sets with operations. We study, for example, groups which are sets with one operation and we study rings which are sets with two operations. I believe it is in algebra that you true find the precise definition of how things work. You can, for example, here prove that $(-1)$ times $(-1)$ is equal to $1$ simply from the axioms of a ring. But first one makes sense of what exactly minus a number is. One makes this more general so that the integers can be seen as an example of a more general concept. So, my recommendation would be to study group theory and ring theory a bit.

Answer 2

You have two specific questions here, one about exponentiation by repeated squares, and one about what branch of mathematics to do this in.

First, you want a proof that exponentiation can be performed by repeated squaring. You of course realize that exponentiation $a^b$ can be computed by multiplying $b$ copies of $a$. Another way to say this a la Sussman's SICP, is that:

$$a^b = a \times a^{b-1}, a^0 = 1$$

(this is just a recursive way of string on a list of $a$'s of length $b$).

The repeated squaring algorithm gets you exponentiation because (and I think this is the single important thing you're curious about) it also gets you a list of $a$'s of length $b$, just in a slightly more complicated way. The explanation is this: $b$ is either even or odd (pretty obvious right?). Let's take those two cases separately.

• If $b$ is even, then $a^b = a^{b/2} \times a^{b/2}$, right? (because $b$ is even you can divide it by 2, and also, $a^x \times a^y = a^{x+y}$ a basic property of exponentials. (note that $b/2$ might be even or odd, we don't know).And this is the same as $a^{b/2}$ squared. That's where the repeated squaring comes from.

• if $b$ is odd, then $a^b = a \times a^{b-1}$ (the usual formula). (note that $b-1$ must be even now).

Because $b$ is either even or odd (and never both) this covers all cases (there are no other possibilities than even or odd) and we can always get $a^b$ using some smaller exponents.

And since we are always getting smaller exponents, we always get down to an exponent of 1, no matter what the exponent is.

And we're done!

(why would we want to complicate matters this way? Well, we're (often) dividing by 2 so the number of multiplications is like the log of $b$ rather than $b-1$, which is a lot less.)

Now to your second question, what branch of mathematics is needed for this? The facts that we used were some properties of exponentiation, some number theory (properties of odd and even) and some arithmetic. These all tend to be taught, at least in the US education system in a first or second year of high school algebra.

There's one step of the proof that is more or less the glue logic that holds it all together and puts the last tiny jigsaw piece in to solve the puzzle and that was the last step, that you always get a smaller exponent and reach 1. The mathematics for that is induction, which is exactly what Sussman is teaching by this example. Induction is often taught in high school in various classes, maybe in algebra, maybe in precalculus.

A side note: if you know about binary, consider $b$ in binary. The repeated square algorithm is then following the binary digits backwards. If $b$ ends in a 0 (is even) then divide $b$ by 2 and square the result. If $b$ ends in 1 then change the 1 to a 0 (subtract 1) and multiply be one $a$. Then recursively work on the remaining digits.