Provin’ 2: Elegant Boogaloo

‘Completing the square’ really isn’t that hard.


So we’ve got this generating function for Fibonacci numbers:

12Definitely nicer looking than it was, but we can go further, by using a technique called ‘partial fraction decomposition’. We split this expression into the sum of two other fractions.


‘Why the heck is that simpler?’ you ask. Because by doing this, you reduce the degree/power of the numerator (A/B) or denominator (something/else). In this case, we wanna simplify that bottom part by factoring. Well, where do you start?

There’s a handy little theorem called ‘the factor theorem’. All it says is: for an equation in x, if ‘r’ is a root, then (x-r) is a factor. So if we find the roots of

2then we can find factors for it. It probably sounds like I’m jumping from point to point, so:

  • Want to simplify the fraction at the top. So use partial fractions.
  • If we want to use partial fractions, we need factors for them.
  • If we want factors, we need to find roots.

What the hell is a root of an equation anyway? Well, for an equation in x, the roots are the values of x which give the equation a value of 0. By plotting2for a range of x, you can kinda get a ballpark idea of what the roots are. They’re where the line crosses the x-axis (or, where ‘y’ = 0). But rather than use trial and error, there’s a general formula that involves a nifty little trick called ‘completing the square’.

Quadratic equation (geometric method)

‘Quad’ is Latin for square, so quadratic equations are just equations which have x² as the highest power. And it turns out that quite a few solutions to equations have clear geometric interpretations.

History digression: there was a fellow named Al-Khwārizmī, who came up with a lot of these geometric solutions. His name is also where ‘algorithm’ comes from, and ‘algebra’ comes from the word al-ğabr in the title of one of his books. It’s Arabic for ‘restoration/balance’, which is kinda nice.

Aaaaanyhoo, this is how to find the root of any quadratic which has the form x²+bx = a. Essentially, getting x on its own on one side of the equation. For example, x²+bx = a is the same as:

Cool, huh? So, for a quadratic equation of the form x²+bx=a, the root (in this case, x) is:

3But! The equation we have is 1-x-x²=0. Which means x² has a coefficient of -1.  Since x² has a coefficient, the form of the equation is actually: ax²+bx+c=0, a.k.a the:

General quadratic equation (algebraic method)

Thankfully though, most of the work is already done. To get this into the form of x²+bx=a (so we can just complete the square for it), we move c over to the other side, and then divide the whole equation by a:

4Now it turns out that this is the same form as x²+bx=a. Why?

  • x² is just x² (or, the coefficient is just 1).
  • x has a coefficient.
  • The right-hand side of the equation has a constant (a number, not a variable).

So now, you just do the same thing you did for the geometric method. You add (half of the coefficient of x) squared, to both sides. Top is what you get when you do this to the general quadratic equation, below is what we got when did it to the regular quadratic equation. Exactly the same form:

5And since they’re the same form, it means the quadratic can be factorized similarly (the bit in the .gif where you stop thinking of it as four separate shapes and just consider it as a square with a particular length side). Like so:

6And then the rest is just tidying this shit up:

7Getting back to our roots

Plug the coefficients a,b and the constant c into that formula, and we’ll get our roots of 1-x-x²!


Since it’s a root, it has two values (the root of 5 can be positive or negative). So the two roots of our equation are:

9which I’m gonna call ‘a’ and ‘b’ just to keep things tidy.

These values are phi / the golden ratio, in flavour, but not exactly. The two values of phi are 1.61… and -0.61… our values ‘a’ and ‘b’ are the inverse (1/phi) of these! Which reminds me: phi has some interesting properties. 1/phi = phi-1. That shit is weird. But neat.

Next step is to put these roots into factors, and put those factors into a partial fraction. And also to come up with another sequel-based title for the next post. Stay tuned.

This entry was posted in Problem 2 and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s