Mathematical Induction

The principle of mathematical induction is a simple but powerful technique for proving mathematical results. In its most basic form, it says the following:

If something’s true for an integer , and if it being true for the number implies it is true for the number , then it is true for all integers .

This is a more-or-less “obvious” statement. It has two components: the base case and the inductive step. The base case establishes truth for one number. The inductive step does not actually establish truth of the statement for any particular value. Instead, it establishes the truth of a logical implication. In formal terms, the above box reads:

If is a proposition for the integer , then if is true and , then is true for all integers .

Think of induction as a string of dominos. Establishing the base case is like knocking down the first domino. Establishing the inductive step is like setting up the dominos so that if the -th domino falls, it knocks over the -th domino. Thinking of it this way, it should be obvious that once these two things are established, then all the dominos will fall. This is one of the concepts that is best learned through examples.

Intro Post: Chris

Hi everyone, my name is Chris.  I graduated from San Francisco State University with a double major in Math and Computer Science, and I am currently a Ph.D student in the Duke Mathematics department.  I am most interested in studying Algebra and Combinatorics, but I have always enjoyed programming as a hobby, and I spend much of my free time doing various programming projects.

I look forward to contributing programming articles to this blog, as well as occasional math related topics.

The difference between “impossible” and “zero probability”

Consider the following game: I write down a random real number between 0 and 1, and ask you to guess it. What’s the probability that you guess it correctly? The answer is zero. You might wonder: “But it’s possible for me to guess the correct answer! That means that the probability has to be more than zero!” and you would be justified in wondering, but you’d be wrong. It’s true that events that are impossible have zero probability, but the converse is not true in general. In the rest of this post, we show why the answer above was in fact zero, and why this doesn’t need to do irreparable damage to your current worldview.

Concrete Nonsense

Hi all! If you’re really interested in math and science and feel like digging a little deeper, there are various blogs out there maintained by college students, grad students and professors on technical subjects. Most recently, I joined a group blog called Concrete Nonsense, which is maintained by grad students and focuses primarily on math. My contribution (hopefully) to the blog will be posts connecting mathematics and computer science by discussing topics in algorithms, complexity theory, artificial intelligence, and quantum computing. The posts on there are considerably more technical and precise. A lot of topics that I find really interesting but feel are too advanced for this blog I will end up posting about on there, until I figure out how to explain them without using too much technical jargon.

Error correcting codes: Why your texts don’t end up as gibberish

Digital information is transfered in the form of electric currents through wires that may contain impurities that alter the currents, or electromagnetic waves through space with ambient radiation that alter the waves, yet digital information is so dependent on precision. Unlike analog information, digital information gets ruined when there is any noise involved. For example, say I shouted “Hello!” to you from far away during a windy day. The sound waves in the air constitute analog information, but the wind along the way can alter the waves and therefore perturb the information. You might hear something distorted but it would probably still resemble the original “Hello!” message. Now suppose I sent the text message “Hello!” to you via instant messaging. In decimal, the ASCII string “Hello!” (excluding the quotation marks) is 072 101 108 108 111 033, which is actually sent in bytes (blocks of 8 bits) in binary as 01001000 01100101 01101100 01101100 01101111 00100001. Now, imagine if there was some noise (perhaps radiation) in the air which altered even one of the bits. Suppose in the byte containing the letter “o”, the bits changed from 01101111 to 00101111 (the first 1 was changed to a 0). Then the message received would be “Hell/!”, a completely different message! And that’s just from one altered bit! If billions of messages are transfered every day, shouldn’t there be an overwhelming number of confusing messages all the time? And that’s just the tip of the iceberg. The messages transmitted could be in machine language telling some server to do a specific thing, and an altered bit could change its actions entirely. How come our computer-controlled devices all work properly most of the time? Maybe the radiation in the air and the imperfections in the wires that we use to transmit digital information actually don’t molest the messages we send. This is not at all true. Instead, we use error correcting codes to ensure that our messages are received as intended.

Calculus: Asymptotic growth

In mathematics and science, it’s often too difficult to get precise formulas for things, so often researchers just estimate the growth. For example, in a previous post on the Fibonacci sequence, we found that the Fibonacci numbers grow roughly exponentially; that is, they are close to an exponential function, but there is a tiny error term. Often, we don’t actually care about the exact formula but we just want an idea of how quickly something grows. In order to capture this vague notion precisely, we use asymptotic notation, which captures all the long-run information contained in the original function.

Intro Post: Eugene

Hi everyone, my name is Eugene. I completed my undergraduate degree at Duke University with a double major in Mathematics and Physics, as well as a minor in Chemistry. My main interests are in applications of mathematics and physics towards understanding and manipulating biological systems. My prior research experience has been in the areas of mathematical biology, biochemistry, and biophysics. As such, my posts will generally concern topics in these fields with particular emphasis on their relation to medicine and physiology. I will also write occasionally about concepts from theoretical physics. Happy reading!

Algorithms: What are they?

Algorithms lie at the heart of computing. When you surf the web, you open up a web browser. When you view a website, your web browser takes the HTML file, which contains code, and then the browser uses an algorithm to convert the code into a page that actually makes sense to humans. When you listen to music on iTunes, the music player takes the MP3 file, which encodes the sound as 0′s and 1′s, and it uses an algorithm read the 0′s and 1′s and tell your computer speakers to output sound. When you’re looking for a particular song in your music library, you might want to search alphabetically, so you click on the Name column to sort your songs alphabetically. Your computer doesn’t magically know how to sort your library. It follows a precise set of instructions every time it’s told to sort something. That set of instructions is an algorithm!

Combinatorics: Power of generating functions

Sometimes sequences of numbers are defined recursively, so that given the previous terms of the sequence we can find the next term. A classic example of this is the sequence of Fibonacci numbers, where every two consecutive terms determine the next term, and so if we are given the first two terms, we can calculate the whole sequence. However, if we wanted to, say, calculated the 1000th Fibonacci number, we’d have to start out with the first two, add them to compute the 3rd, add the second and third to compute the 4th, and so on, to slowly build up every single Fibonacci number before the 1000th in order to get there. It’d be much nicer if we had a formula for the Fibonacci sequence. That way, if we wanted the 1000th Fibonacci number, all we’d have to do is plug 1000 into the formula to compute it. Of course, the formula is only useful if it takes less time to crunch it out than it does to do it the brute-force way. A method of finding closed formulas for sequences defined by recurrences is the use of generating functions. Generating functions are functions which “encapsulate” all the information about a sequence, except you can define it without knowing the actual terms of the sequence. The power of generating functions comes from the fact that you can do things like add and multiply them together to create generating functions of other sequences, or write them in terms of themselves to find an explicit formula. Once you have an explicit form for a generating function, you can use some algebra to “extract” the information from the function, which usually means you can find a formula for the sequence in question.

Linear Algebra: What matrices actually are

Most high school students in the United States learn about matrices and matrix multiplication, but they often are not taught why matrix multiplication works the way it does. Adding matrices is easy: you just add the corresponding entries. However, matrix multiplication does not work this way, and for someone who doesn’t understand the theory behind matrices, this way of multiplying matrices may seem extremely contrived and strange. To truly understand matrices, we view them as representations of part of a bigger picture. Matrices represent functions between spaces, called vector spaces, and not just any functions either, but linear functions. This is in fact why linear algebra focuses on matrices. The two fundamental facts about matrices is that every matrix represents some linear function, and every linear function is represented by a matrix. Therefore, there is in fact a one-to-one correspondence between matrices and linear functions. We’ll show that multiplying matrices corresponds to composing the functions that they represent. Along the way, we’ll examine what matrices are good for and why linear algebra sprang up in the first place.