I just started college classes this Thursday. Since I had already taken Calculus III in high school, I was allowed to skip ahead to real analysis. The first day’s assignment had some pretty interesting problems, so I thought I’d share them here.


Rational numbers are numbers that can be represented as ratio of two integers. Numbers like 1/2, 3/4, 87, and -43/6 and so on. Irrational numbers, then, are numbers which cannot be represented as the ratio between two integers. For a long time it was thought that all things could be measured through rational numbers, and there was no such thing as irrational numbers. To the Pythagoreans, a cult led by the famous mathematician Pythagoras, this belief was sacred. It was so sacred, in fact, that it is rumored that when one of the Pythagoreans, Hippasus, proved that the length of the diagonal of unit square (or the \sqrt{2}) was irrational, they bound him up and threw him into the sea. I do not know what methord Hipassus used to prove this, or even whether or not this story is true, but I thought I’d start off by sharing one of my favorite ways I’ve seen this theorem proved.

Proof 1: The Square Root of 2 is irrational

First, assume that the square root of 2 really is rational. That is, it can be written as the ratio of two integers. Thus, we can write

Now comes the interesting part. Remember the fact that all numbers can be represented with a unique prime factorization. So let’s say you know the prime factorization of a, to figure out the prime factorization of a^2 you merely multiply all the exponents in a’s prime factorization by two. For example if a = 2^3*5^2*7 then a^2 = 2^6*5^4*7^2. But since you are multiplying all the exponents by two, they must all end up being even. The same thing goes for the factorization of b^2. That means the exponent of “2” in the prime factorization of b^2 must be even, but that means that the exponent of 2 in 2b^2 must be odd. But that means that 2b^2 can’t possibly be equal to $a^2$ since $a^2$’s factorization has only even exponents. This is a contradiction, and thus we can conclude that \sqrt{2} is indeed irrational.

The great thing about this proof is that it easily extends to any value \sqrt{n} where n  is not a perfect square. Because if n is not a perfect square, it must have an odd exponent in it’s prime factorization, which would mean that nb^2 must also have an odd exponent somewhere, which would mean it can’t possibly be equal to a^2 as it only has even exponents. Thus, this proof shows that any square root of a number which isn’t a perfect square will result in an in irrational number!


Now for the problems on my homework assignment. The two problems I want to address are

Prove that \sqrt{2} + \sqrt{3} is irrational
Prove that \sqrt{2} + \sqrt{3} + \sqrt{5} is irrational

If you’d like to, try to prove these on your own before moving on.

The first one is pretty easy if you consider one some pretty obvious facts. If the numbers x and y are rational, then

  1. x+y is rational
  2. x-y is rational
  3. xy is rational

Now, look back at statement 3 . If we let y = x this statement says that if x is rational, then x^2 is rational. Which means that if \sqrt{2} + \sqrt{3} is rational, then so is \left(\sqrt{2} + \sqrt{3}\right)^2 = 5 + 2\sqrt{6}. Now, statement 2  says that I can subtract two rationals and I’ll get a rational. Thus, if I can drop the five from 5 + 2\sqrt{6} and conclude that 2\sqrt{6} is rational. Using statement 3 again, we can see that multiplying by \frac{1}{2} would allow us to conclude tthat \sqrt{6} is rational. This is false, as we proved before, and thus a contradiction, thus proving that \sqrt{2} + \sqrt{3} is irrational.

The next one is a bit more tricky. If you just square it you get 10 + 2\left( \sqrt{6} + \sqrt{10} + \sqrt{15}\right). Even if you drop the 10 and the 2 there’s still three radicals left, and we’ve only proven that one radical on its own is irrational, so there’s no contradiction with stating that \sqrt{6} + \sqrt{10} + \sqrt{15} is rational so far as we know. But let’s go ahead and drop the 10 and the 2 and conclude that \sqrt{6} + \sqrt{10} + \sqrt{15} is rational, and square it again. This time you get

31 + 2\left(\sqrt{60} + \sqrt{90} + \sqrt{150}\right)

Still not much better it seems. Dropping the 31 and the factor of 2 still leaves us with three radicals. However factorizing these numbers reveals something special.

So, by assuming \sqrt{2} + \sqrt{3} + \sqrt{5} was rational, we concluded \sqrt{60} + \sqrt{90} + \sqrt{150} is rational. And that final line allows us to combine these conclusions and declare that is also rational, which is a contradiction as   is obviously not a perfect square.

For some more challenges, try proving the above these statements for general natural numbers a, b, and c. And you could also try proving the irrationality of sums of more than three radicals but I can say from experience that this won’t be as easy as either of these.

Posted in Uncategorized | Leave a comment

Fun With Omegle

If you haven’t heard, Omegle is a text based chatting site that connects you with random people around the world. It’s basically like Chatroullete except without the penises.  The interesting thing about Omegle is that it’s an incredible simple set up. Now, I’m not very knowledgeable with HTML/AJAX/JavaScript/All that webby stuff, so take what I say with a grain of salt. But it Omegle basically has a bunch of different which follow the pattern “”.

The possible values of “???” are

“start” gives you a six digit id composed of numbers, letters, sometimes underscores and then finds you a partner. An example of an id number is “4WWFZh”

“typing” is used to inform your partner you are typing. It’s sent automatically when you begin typing. This script takes your omegle id as input, with variable name id. The id is sent with the HTML GET method.

Sends a message. Takes the id and the message, with variable name msg, as input. Once again, uses GET

Disconnects you. Takes the id as input. Uses GET.

“events” is a list of occurrences that happened since you last checked them. That is, it is cleared after you load it each time. The different possible events are “waiting”, “connected”, “gotMessage”, “strangerDisconnected”, “stoppedTyping”, “recaptchaRequired”, “recaptchaRejected”.  Takes id as input. GET.

Using all this information, it is very easy to create a program that interfaces with omegle. So I did. I chose to do it in python because of all the languages I program in, it has the easiest to use web library. Thus, I created this.

It’s a nice simple interface to omegle. You can use it to create any kind of omegle program you want. I thought of two things which I’ll post here. Note that to use them you must create a folder called OmeglePython and place “” in it. Then create a new file “”, which you can leave empty, in that same folder.

Anyways, first I created a program that connected unsuspecting omeglers to a chatbot. In this case, I connected them to Oliverbot. It’s actually not a very good chatbot, so I’m currently working on one for Cleverbot, which I find models human speech much better.

Secondly, I created a program for all you creepers out there. It creates to omegle clients to connect to two different people, and pass the messages received from each person along so it’s as though each person is talking to the other. That is, if A and B are actual people, and X and Y are the clients made by the program then messages go A-> X -> Y -> B and B -> Y -> X -> A.  You can see the messages as they’re being sent along. If you’re in the mood to troll, you can send a message yourself, impersonating either person. This can lead to rather humorous conversations if you’re lucky.

Posted in Uncategorized | Leave a comment

The Monkey and The Coconut

I was reading through Martin Gardner’s Colossal Book of Mathematics recently, and thought I’d share an antriguing puzzle he gave and also, what I think to be an interesting way to solve it. The puzzle goes a little something like this

” Five men and a monkey were shipwrecked on a dessert island and they spent the first day gathering cooconuts for food, piled them all up together and then went to sleep for the night.

But during the night, one man wakes up while the others are sleeping. He becomes suspicious of his friends and fears that come morning he won’t get his proper share. So he sneaks off and divides the coconuts into 5 even groups, but finds one left over, so he gives that to the monkey. He takes one of the groups and hides it, puts all the rest of the coconuts back together and goes to sleep. A second man wakes up, also becomes suspicious, and repeats the same procedure, and also having a remainder of one coconut. This happens again with the third, fourth, and fifth men. The next morning they gather round to split the remaining cocounts into five groups, and once again they have a coconut left over, which they give to the monkey. How many coconuts did they start off with?”*

*Actually, Gardner’s version had the last division come out even. The above is the original version of the riddle. 

Now, one can use this information to generate a system of equations. Let N be the total number of coconuts, and A, B, C, D, E represent how much each person took as the others slept and let F represent the number distributed to each person at the very end. Using the fact that each was a division of 5 with remainder 1, we can see that.

Using the above equations, one can obtain the following

1024N = 15,625F + 11,529

Which, is actually a very simple Diophantine equation with a well known method of solving which involves utilizing the Euclidean Algorithm

However, I noticed that for this particular problem a much simpler and far less computationally intensive approach exists. I thought to myself, what if I had written the number of coconuts in base 5, and performed all division and subtraction in base 5. So, what can you  get from this view point?

Well, firstly, since the first division by 5 leaves a remainder of 1,the number written in base 5 must end with a 1. Yes, that’s all well and good, but that’s not telling us a whole lot. The real advantage of writing in base 5 comes when you go to subtract the first set of numbers the first man hides. First, remember that he gave one coconut to the monkey, changing the last digit 1 into a 0. And then note that dividing by 5 in base 5 simply shifts the digits. Finally, since the second man also gets a remainder of one when trying to divide the coconuts, when one subtracts the number the first man took for himself from the number, the final digit must be 1. Putting all this together, one can determine the second base 5 digit of the solution.

Above is a visual representation of the subtraction. Dashes represent unknown digits involved in the computation. Now, I’m not saying the answer will be 5 digits long. It doesn’t really matter how many dashes you put as the reasoning will be the same. Anyways, what we’re really interested in is the “?”. Now,the question is simple, what can you take from 0 and get 1? Keep in mind that this subtraction is taking place in base 5. If you try 1 you’ll borrow 5 from the next highest digit and subtract to get 4.Similarly, if you try 2 you’ll get 3. Obviously, the only proper value of “?” is 4. Thus,the last two digits of the solution in base 5 are 41.

Now, take a step back and see what we have just concluded. What we have a assumed so far is that two men, one after the other, tried to divide the coconuts into groups of 5, but they each got a remainder of 1 before they took their share. Therefore, what we have just said is that for two men to go through this process and get a remainder of 1,the initial number of coconuts must end in 41 in base 5.

Now, let’s add the third guy in the mix. We know that he too received a remainder of 1. Note that this is the same as saying after the first guy took his share, the next two attempts to divide the coconuts also had a remainder of one. From our conclusion from before, this means that after the first guy takes his coconuts, the remaining number of coconuts must end in 41 base 5.  This information allows us to figure out the the third digit of the answer. Keep in mind that the original number of coconuts must also end in 41, and the the first man removed one coconut before taking his share.

So, what replaces the question mark? One might be tempted to answer “0”, but remember that one must be borrowed from 4 to perform the subtraction. Thus the right replacement for “?” is once again”4″.

By now you should see a pattern cropping up in the base 5 representation of the answer. After the last digit is 1, the following digits are 4 for each attempt to divide the coconut resulting in a remainder of 1. Since there were in total 6 attempts to divide the coconuts, we can conclude that the base 5 representation of the answer is 444441, which is 15,621 in base 10. And that’s that.

Posted in Uncategorized | 2 Comments

A bit o’ Number Theory

I recently took a trip to Virginia to visit the university I shall be attending for accepted students day. It was everything I was expecting. A beautiful campus, cool teachers, fantastic opportunities, a wonderful library (they even had a library dedicated solely to science. 🙂 ), etc. Anyways, while I was visiting, I took walk down to the Math department. While their, I walked in on a group of students working on their math homework. They mentioned they were stuck on number 6. So, I decided to help them out.

The problem was to prove that the set \{12a + 25b | a, b \in Z\} is equivalent to the set of integers. The way to show two sets A and B are equivalent is to show that A is a subset of B and B is a subset of A. That is, if an item is in set A then it is also in set B, and if it is in set B it is also in set A.

It’s obvious that for any integral a and b, 12a + 25b, is an integer. But now we have to show that we can write any integer in the form of 12a + 25b. This becomes pretty obvious when one notes that 12(-2) + 25(1) = 1, and thus 12(-2N) + 25(N) = (12(-2) + 25)N = N. And, thus, all integers can be represented in this way.

Anyone who likes to play study number theory would have instantly seen that proof. Why?  There is a well known theorem stating that given two integers, x and y, you can write their greatest common divisor as a sum, ax + by, where a and b are integers. A proof of this can be found on wikipedia. It might, however, be a fun exercise to try and prove it yourself.

If you manage to prove it yourself, another similar problem would be to try to find what numbers can be produced when a and b are restricted to being positive or 0. Take for instance 10 and 13. You obviously can’t make the number 12, and can make 26. But can you make 98? 112? 589?. Just something to think about.

Posted in Uncategorized | Leave a comment

A Storm is brewing

Recently came across this video. I ❤ Tim Minchin.

Posted in Uncategorized | Leave a comment

Some Fun Puzzles

Just a few really fun puzzles that I’ve come across at one point or another. I really like these ones in particular because they each require some clever thinking to solve effectively.

Puzzle 1: Checkerboard Dominoes

Imagine a checkerboard. It’s easy to see that if you are given 32 1×2 dominoes, you can cover the entire board. However, if I remove two corner pieces as shown, is it possible to cover the remaining board with 31 pieces?

Puzzle 2: Prisoners on Death Row

10 straight-jacketed prisoners are on death row. Tomorrow they will be arranged in single file, all facing one direction. The guy in the front of the line (he can’t see anything in front of him) will be called the 1st guy, and the guy in the back of the line (he can see the heads of the other nine people) will be called the 10th guy. An executioner will then put a hat on everyone’s head; the hat will either be black or white, totally random. Prisoners cannot see the color of their own hat. The executioner then goes to the 10th guy and asks him what color hat he is wearing; the prisoner can respond with either “black” or “white”. If what he says matches the color of the hat he’s wearing, he will live. Else, he dies. The executioner then proceeds to the 9th guy, and asks the same question, then asks the 8th guy … this continues until all of the prisoners have been queried.

This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What should they do to save the most lives?
After you have solved the above problem, generalize. There are N prisoners and K different colors of hats.
Puzzle 3: Guess the Number

Two friends are abducted by a gigantic, horned, fire-breathing, man-eating monster named Fred. Now, Fred doesn’t like to eat his victims without giving them a fear fight, so he decides to play a game. In his dungeon he has two rooms, one black and one white. Tomorrow, he will take his stamp maker, and place either a black stamp or a white stamp on each prisoner’s head. The prisoner cannot see the color of the stamp on his own head, but his friend’s. They will be asked to go from their cell into the rooms, one person in each. Now, if either enters the room with the same color as their stamp, they can both go free. But if they both enter the wrong rooms they die. The night before Fred gives them their stamps they are allowed to make a strategy. What strategy should they use to guarantee their life?

And once again, can you generalize to N rooms with N colors?

Posted in Uncategorized | Leave a comment

Differential Equations


Even though I’m only a senior in high school, I’m taking a course in differential equations. We came to the section where we learn to solve high order linear differential equations with constant coefficients. We went over the characteristic polynomial, and the case where it has a repeated root. We learned that if r is a repeated root then, e^{rt} and te^{rt} are both solutions to the differential equation. There was a proof of this using reduction of order. Our teacher also told us that if r is repeated more times, then we can keep multiplying our previous solutions by t for every time r was repeated. This, he said without proof. So, I decided to prove it myself.

Trial 1

So, let’s say you have a differential equation with constant coefficients, second order to make it easy, as shown below:
y'' + ay' + by = 0

This is completely general, as, if there was a coefficient in front of the y'' term, I could merely divide it out. I haven’t worked with differential operators very much, but I did notice that this could be written as the product of differential operators like this:
\left(\frac{d}{dt} - c_1\right)\left(\frac{d}{dt} - c_2\right)y = 0

because, if you multiply that out you get
\left(\frac{d^2}{dt^2} - (c_1 + c_2)\frac{d}{dt} + c_1c_2\right) y = 0

which obviously simplifies to the above equation of -(c_1 + c_2) = a and c_1c_2 = b.

The advantage of putting it in this form, is that it’s obvious that the solutions to the resulting characteristic equation are c_1 and c_2. It’s also obvious that higher order equations can be made easily by multiplying by \left(\frac{d}{dt} - c\right) where c will be another solution to the characteristic equation. It’s also worth noting that the order that they’re multiplied in doesn’t matter. You get the same thing.

Now, I considered what happened when \left(\frac{d}{dt} - c\right) is applied to t^ne^{ct}. Doing this you get
\left(\frac{d}{dt} -c\right) t^ne^{ct} = \left(nt^{n-1}e^{ct} + ct^ne^{ct} - ct^ne^{ct}\right) = nt^{n-1}e^{ct}

Notice that this is very similar to what the normal differentiation operator does to polynomials. It’s exactly the same except that t^n is replaced by t^ne^{ct}. Now, it’s obvious why t^ne^{ct} are also solutions. If we take the nth derivative of t^k, we get 0 if n >= k. In the same way, if we take \left(\frac{d}{dt} - c\right)^n t^ke^{ct}, we get 0 if n>= k.

I was satisfied with this result at the time, and didn’t think to take this any further. But recently we started going over Euler Equations. That is,  differential equations of the form:
x^2y'' + \alpha xy' + \beta y = 0

Basic solutions are of the form x^r, and by substituting that for y you can find the characteristic polynomial and solve it like you would the differential equations with constant coefficients. Repeated roots are treated the same way, except you multiply by \ln x instead.

This diff eq. can also be written as a product of differential operators, but this time of the form
(x\frac{d}{dx} - c)

What if one could derive that the natural log was the appropriate choice using  this fact? That is find a function g(x) that causes the above differentiation operator to act on g(x)^nx^c like the regular differentiation operator does on t^n. Actually, this is pretty easy to do. Merely solve the equation (x\frac{d}{dx} - c)g(x)^nx^c = ng(x)^{n-1}x^c for g(x).

(x\frac{d}{dx} - c)g(x)^nx^c = ng(x)^{n-1}x^c
\left[x\left(ng(x)^{n-1}g'(x)x^c + cg(x)^nx^{c-1}\right) - cg(x)^nx^c\right] = ng(x)^{n-1}x^c
ng(x)^{n-1}g'(x)x^{c+1} = ng(x)^{n-1}x^c
g'(x) = 1/x

Obviously g(x) = \ln x is an appropriate function. To generalize even further if you have any differential equation that can be produced by products of

(h(x)\frac{d}{dx} - c),

and the solutions are of the form f(x,c), solutions to equations with repeated roots can be found by repeatedly multiplying the base solution, f(x,c) by any g(x) that satisfies:
f(x,c) = e^{c\cdot g(x)}

For example, with linear differential equations with constant coefficients f(x,c) = e^{cx} and g(x) = x. In the case of Euler equations f(x,c) = x^c and g(x) = \ln x.

Knowing this probably isn’t very useful but finding connections in mathematics is always interesting. I do wonder, though, if there is a name for this. But whether or not there is, I think this is a fun way to see things.

Posted in Uncategorized | Leave a comment

Futurama Body Switcher

I was watching episodes of the new season of Futurama recently. In one particular episode Professor Farnsworth invented a device to switch minds of two people. But as anyone who has ever watched the show might guess, there was a little problem. Once two people went through the body switcheroo, they could not go through the switching process again. There are many body switches and peoples minds end up all over the place, and no obvious way of putting everyone back in their own bodies. Luckily, the Globetrotter Scientists figure out that no matter how scrambled people’s minds and bodies get, they can always be placed correctly as long as you introduce two extra, untouched, people. My aim here is to explain why.

This is going to be a pretty short post for me as this is actually a pretty easy thing to prove, once you look at it the right way. Basically what it comes down to is two extra people give you a way to switch any two people, even two people who have switched before, but only one time. To see why, just look at the following diagram.

A Diagram

So, you see, A and B can be switched, and since no switch involves a swith between A and B directly, it can be done on two people that have already been switched. You’ll notice that S1 and S2 are also switched. This doesn’t really matter since this switching process never involves a trade between S1 and S2 they can always switch back after fixing everyone.

But during the process, the bodies of A and B are involved in switches with both the bodies of S1 and S2, meaning this sort of switch can only be done once on two people. Still, since the original body switches were done in a way that no bodies could have their minds switched twice, they can be reversed without having to switch the minds of the same pair of bodies twice.

There are still, however, other interesting questions to answer about this scenario. For example, what if you didn’t have any two extra people? When is it still possible to put people back to normal? And come to think of it, what’s the most efficient way of doing it? These are questions for another time, so that will be all for now.

Posted in Uncategorized | Leave a comment

Serieus Business


Everybody knows the Fibonacci series. It begins with a 0 and a 1 and the next element is generated by summing the previous two. You can find the first few elements of the sequence easily, even by hand. They go 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. But what if you wanted the 100th element?  Easy, write a computer program to do it for you. But then what of the thousandth element? Or the ten thousandth element? Using this basic recursive definition, computing elements of the series way down the line becomes impossibly computationally intensive, even for computers. There must be a better way of finding elements to this, and other similar series.

The Process

Consider the following matrix

A = \left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]

Not a very interesting matrix, on its own, but let’s pretend we have a column matrix, \mathbf{x}, composed of two consecutive members of the Fibonacci sequence, and then compute A\mathbf{x}.

A\mathbf{x} = \left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right] \left[\begin{array}{c} F_{i+1} \\ F_{i} \end{array} \right] = \left[\begin{array}{c} F_{i+1} + F_{i} \\ F_{i+1} \end{array} \right] = \left[\begin{array}{c} F_{i+2} \\ F_{i+1} \end{array}\right]

Interesting. Apparently, multiplying x by the matrix A discards the earlier Fibonacci number and adds a new one. It’s like being presented with an infinite tape of Fibonacci numbers, but only having a small window through which you can see only two numbers at a time. Multiplying by A shifts the tape over one place. You could multiply by A as many times as you wish to shift it over to any position you desire. You know what would be great? A simple formula for the k-th power of A, that is, the matrix that does the same thing as multiplying by A k times. Luckily, we can do this if we remember that if A is a diagonalizable, P is the diagonalizing matrix and D is the corresponding diagonal matrix, then:

A^k = PD^kP^{-1}

If we want a formula for A^k all we need to do is diagonalize it. So, let’s solve the characteristic polynomial.

\begin{array}{lcl}\left|\lambda I - A \right| & = & 0 \\ \left| \begin{array}{cc} \lambda - 1 & -1 \\ -1 & \lambda \end{array} \right| & = & 0 \\ \lambda^2 - \lambda - 1 & = & 0 \end{array}

The solutions two the characteristic equation are \frac{1 \pm \sqrt{5}}{2}. The positive root I shall denote \phi, because it happens to be the golden ratio, and I shall denote the negative root \sigma because I like using Greek letters.

When you solve for corresponding eigenvectors, you’ll see that \left[\begin{array}{c} \phi \\ 1 \end{array}\right] is an eigenvector for \phi and \left[\begin{array}{c} \sigma \\ 1 \end{array}\right] is an eigenvector for \sigma . So, if we let P = \left[\begin{array}{cc} \phi & \sigma \\ 1 & 1 \end{array}\right] then we know that D = \left[\begin{array}{cc} \phi & 0 \\ 0 & \sigma \end{array} \right]

Now, let’s go back to the equation from before. We know that A^k = PD^kP^{-1}. So if \mathbf{x} represents the first two elements (the 0-th and the 1-th) of the Fibonacci sequence then we can shift run through our infinite tape to find the k-th and (k+1)-th element by computing A^k \mathbf{x} which equals PD^k P^{-1}\mathbf{x}

After finding P^{-1} and simplifying the expression, you’ll find that
A^k \mathbf{x} = \left[\begin{array}{c} \frac{\phi^{k+1} - \sigma^{k+1}}{\phi - \sigma} \\ \frac{\phi^{k} - \sigma^{k}}{\phi - \sigma} \end{array}\right]

You can confirm this formula works on a calculator yourself. Now, it’s not hard to see that this expression is a bit superfluous. We don’t need to calculate two Fibonacci numbers at once; we only need one. Note that if we pay attention to only the bottom element of the matrix, we’ll have an expression for the k-th element of the Fibonacci series. So we really only need that part and we have a simple, easy to calculate expression for Fibonacci numbers. Computers do exponentiation with ease so someone could easily compute nearly any Fibonacci number he wanted.

But now, one is left to ask, what if it’s not Fibonacci numbers you want, but a different sequence? Is there a way to generalize this result? Well of course. This wouldn’t be nearly as fun if there wasn’t.


Consider a series defined like so:
s_n = a_1 s_{n-1} + a_2 s_{n-2} ... + a_m s_{n-m} = \displaystyle \sum_{i=1}^{m} a_i s_{n-i}

The resulting series obviously depends on what the initial values from 0 to k – 1 are set to.  Let \mathbf{x} be the column matrix composed of these values and we lets make a matrix A such that:

A = \left[\begin{array}{cccc} a_1 & a_2 & \cdots & a_m \\ 1 & \cdots & 0 & 0 \\ \vdots & \ddots & \vdots & \vdots \\ 0 & \cdots & 1 & 0 \end{array} \right] = \left[\begin{array}{c|c} \multicolumn{2}{c}{\mathbf{a}} \\ \hline \ I & \mathbf{0} \end{array}\right]

That is, make it so A has a top row of all the coefficients, in order, used to calculate the next element of the series, has an (m-1) x (m – 1) identity matrix in the bottom left and whose other elements are all 0. If you multiply \mathbf{x} by this matrix the result will have the next element of the sequence on the top and all other elements will be shifted down and the very bottom element will be discarded. Just like before, we are running through an infinite tape containing the elements of the series. Only this time, the window allows us to see not only 2 elements at a time but m elements at once.

Now, we have to diagonalize this general matrix. The characteristic equation for A is:

\begin{array}{rcl} \lambda^m - a_1\lambda^{m-1} - a_2\lambda^{m-2} ... - a_m & = & 0 \\ \lambda^m & = & \displaystyle \sum_{i=1}^{m} a_i \lambda^{m-i} \end{array}

Although I won’t prove it here, the proof is easy can be done with induction. Now we need to do is find the corresponding eigenvectors to the eigenvalues. Let’s take an eigenvalue of A, \lambda  and  make a column matrix \mathbf{u} ,

\mathbf{u} = \left[\begin{array}{c} \lambda^{m-1} \\ \lambda^{m-2} \\ \vdots \\ 1 \end{array} \right]

It is easy to see that
A \mathbf{u} = \left[ \begin{array}{c} a_1 \lambda^{m-1} + a_2 \lambda^{m-2} + \cdots a_m \\ \lambda^{m-1} \\ \vdots \\ \lambda \end{array} \right] = \left[ \begin{array}{c} \lambda^{m} \\ \lambda^{m-1} \\ \vdots \\ \lambda \end{array} \right] = \lambda \mathbf{u}

which means that \mathbf{u} is an eigenvector corresponding to \lambda. Using this fact, if lambda_i represents an eigenvalue, we can create a diagonalizing matrix P,

P = \left[\begin{array}{cccc} \lambda_1^{m-1} & \lambda_2^{m-1} & \cdots & \lambda_m^{m-1} \\ \lambda_1^{m-2} & \lambda_2^{m-2} & \cdots & \lambda_m^{m-2} \\ \vdots & \vdots & \vdots & \vdots \\ 1 & 1 & 1 & 1 \end{array}\right]

And the the diagonalized matrix D becomes
D = \left[ \begin{array}{ccc} \lambda_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda_m \end{array} \right]

Alright, we’re almost done. We just look back on the equation A^k \mathbf{x} = PD^k P^{-1} \mathbf{x}. Now, as before, this expression is superfluous. We only need the bottom row of the resulting matrix. But the bottom row of PD^k P^{-1} \mathbf{x} is the same as the bottom row of PD^k times the result of P^{-1} x. And to find the bottom row of PD^k we just multiply the bottom row of P with D^k which evaluates to
\left[ \begin{array} {cccc} \lambda_1^{k} & \lambda_2^{k} & \cdots & \lambda_m^{k} \end{array} \right]

which I’ll call \mathbf{\Lambda}^{\mathbf{T}}. Finally if I \mathbf{S} = P^{-1}\mathbf{x} then the k-th element of the series S can be found with
\mathbf{\Lambda}^{\mathbf{T}} \mathbf{S} = \mathbf{S} \cdot \mathbf{\Lambda}

And that’s it. Simply compute \mathbf{S} from the initial values and the matrix P, and you’ll have an easy expression for the k-th element of the series.

One more thing

I’m sure some of you have been wondering, “What happens if A isn’t diagonalizeable?” Well, then you’re pretty much screwed. Really, I’m not sure what to do when your matrix isn’t diagonalizeable. If anyone thinks of anything, let me know.

Posted in Uncategorized | Leave a comment

Hello world!

Welcome to This is your first post. Edit or delete it and start blogging!

Posted in Uncategorized | 1 Comment