gtMath

Entropy is often considered a measure of "disorder" which, as you may recall from chemistry, is supposed to increase over time. A physical system tends to evolve in such a way that its useful energy dissipates. The value of entropy measures how far along the system is in that process. There are a few different formulations which each capture this idea; each is a formula that must be calculated as opposed to a physically observable property of the system (like temperature or pressure would be).

In this post, I'm going to show you Einstein's derivation of a formula for entropy, which will also shed some light on what exactly this quantity represents. This formula will be an ingredient in the forthcoming post on Einstein's Brownian motion paper, so pay attention!

Imagine a system, consisting of $n$ atoms of an ideal gas in a closed container ($n$ will be a big number, like on the order of $10^{23}$ big). Actually, it doesn't need to be a gas, but that just seems to be the easiest to picture. An ideal gas means that the molecules are monatomic, and we can ignore rotational energy of the atoms, as well as interactions between them. In order words, we are concerned only with their translational motion and assume all collisions are elastic. Finally, we assume the container of gas is surrounded by an ambient reservoir, with which it can exchange heat, so that the system's temperature $T$ remains pretty much constant.



Each atom has a position and a momentum, each a 3-dimensional vector, i.e. a vector with 3 components. At any given time, the $2 \times 3n = 6n$ components of position and momentum, denoted $q_1, q_2, ..., q_{3n}$ and $p_1, p_2, ..., p_{3n}$ respectively, for all the atoms determine the configuration of the system, and the set of all possible configurations is called configuration space, a subset of $\Bbb R ^ {6n}$. The $q_i$'s and $p_i$'s are called the state variables of the system.

The First Law of Thermodynamics states that energy can be converted into different forms but not created or destroyed, and thus as the system evolves, its change in energy is the work done on the system plus the heat supplied to the system: $$
dE = dW + dQ
$$ If the system is described by a set of parameters $\lambda_1, \lambda_2, ... , \lambda_m$ and the state variables mentioned above, then if it undergoes a small change over a time interval $dt$, the resulting change in energy is given by: $$
dE = \sum_{i=1}^{m}{\frac{\partial E}{\partial \lambda_i}\frac{d\lambda_i}{dt}dt}
+ \sum_{j=1}^{3n}{\left( \frac{\partial E}{\partial q_j}\frac{dq_j}{dt}dt + \frac{\partial E}{\partial p_j}\frac{dp_j}{dt}dt \right)} \tag{$\spadesuit$}
$$ To be a bit more concrete, the "parameters" above would be things like volume of the container, so the first sum is identified with the work done on the system (usually just $dW = P \ dV$), and the second sum is identified with the heat supplied to the system; more heat in the system (all else equal) means higher temperature, i.e. the atoms bounce around faster, and so the second sum is our $dQ$. In the example we're talking about, the energy is only due to translational kinetic energy of the atoms, and thus the energy would be $E=\sum_{j=1}^{3n}{\frac{p_i^2}{2m}}$. There would also be a term involving the $q_i$'s if we took into account gravitational potential energy, which depends on the particles' positions.

The above formula doesn't depend on which path the system takes through state space, so in particular, it holds for an adiabatic change, i.e. one in which the system does not gain/lose any heat so $dQ=0$. Before such a change occurs, the probability of finding the system in a state with energy $E$ is given by the volume of a little box in state space times its probability density: $$
d{\Bbb P} = Ce^{\frac{-E}{kT}}dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n}
$$ The probability density $Ce^{\frac{-E}{kT}}$ deserves a bit of attention. $T$ is the temperature of the system, considered to be constant as mentioned above, $k$ is the Boltzmann constant, $1.38 \times 10^{-23}$ Joules/Kelvin (units of energy per temperature), which makes the exponent dimensionless, and $C$ is a constant which makes all the probabilities add up to 1. We'll solve for $C$ in a moment, but why is the probability density given by an exponential?

If we have two pockets of gas in the container with energies $\epsilon_1$ and $\epsilon_2$, since the model is that they are independent, the probability of finding pocket 1 at energy $\epsilon_1$ and finding pocket 2 at energy $\epsilon_2$ should be the product of the individual probabilities of finding the respective pockets at those energy levels. Furthermore, the energies add, so that the total energy of the two pockets combined is $\epsilon_1 + \epsilon_2$. The exponential function has the desired property: $$
\exp \left( \frac{-(\epsilon_1 + \epsilon_2)}{kT} \right) = \exp \left( \frac{-\epsilon_1}{kT} \right) \exp \left( \frac{-\epsilon_2}{kT} \right)
$$ The fact that the "drop-off factor" in the denominator of the exponent is proportional to $T$ is a consequence of the fact that the average kinetic energy an atom in the gas is $\frac{3}{2}kT$, which in turn follows from the ideal gas law $PV = NkT$. For a simple and insightful derivation of the $e^{\frac{-E}{kT}}$ based on Maxwell's analysis, click here.

Back to the main line: in order to solve for $C$, we note that the probabilities of all possible configurations must equal 1. Probabilities are always non-negative, so we can assume that $C$ is of the form $e^c$, and thus: $$
\begin{align}
1 &= \int{d{\Bbb P}} \\[3mm]
&= \int e^c e^{\frac{-E}{kT}}dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n} \\[3mm]
&= e^c \int e^{\frac{-E}{kT}}dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n} \\[3mm]
& \Downarrow \\[3mm]
c &= - \ln \left[ \int e^{\frac{-E}{kT}}dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n} \right]
\end{align}
$$ The integrals above are taken over the entire range of possible values of the $q_i$'s and $p_i$'s, i.e. over all state space.

After our adiabatic change in the system, there will be a similar expression for $d{\Bbb P}$, except that $c$ now may have shifted a bit from $c$ to $c + dc$, as may have $\beta$ to $\beta + d\beta$ (where we are now defining $\beta := \frac{1}{2kT}$ for notational convenience). The energy $E$ will also shift to $E + dE = E + \sum_{i=1}^{m}{\frac{\partial E}{\partial \lambda_i}\frac{d\lambda_i}{dt}dt}$. Here, we've used equation $(\spadesuit)$ and the fact that $dQ$ = 0, so only the $dW$ term comes into play. To save on the symbols, I'll also start referring to the $\frac{d\lambda_i}{dt}dt$'s simply as $d \lambda$.

Now similar to the above, we have: $$
\begin{align}
1 = &\int{d{\Bbb P}} \\[3mm]

=  &\int \exp \left( (c+dc)-2(\beta+d\beta)\left(E + \sum{\frac{\partial E}{\partial \lambda} d\lambda}\right) \right) dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n} \\[3mm]

 = &\int \exp
\left(
dc - 2
\left(
E \, d\beta + \beta \sum{\frac{\partial E}{\partial \lambda} d\lambda} +d\beta \sum{\frac{\partial E}{\partial \lambda} d\lambda}
\right)
\right) \\[1mm]
&\times \exp \left( c-\frac{E}{kT} \right)
dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n}
\end{align}

$$ We can expand the first exponential into a Taylor series and then neglect the terms past first order: $$
\begin{align}
1 = \int
&\left[
1 + dc - 2
\left(
E \, d\beta + \beta \sum{\frac{\partial E}{\partial \lambda} d\lambda} +d\beta \sum{\frac{\partial E}{\partial \lambda} d\lambda}
\right)
+ \frac{1}{2} (dc - 2 (...))^2 + ... \right] \\[1mm]

& \times \exp \left( c-\frac{E}{kT} \right)
dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n}\\[3mm]

\approx \int
&\left[
1 + dc - 2
\left(
E \, d\beta + \beta \sum{\frac{\partial E}{\partial \lambda} d\lambda} +d\beta \sum{\frac{\partial E}{\partial \lambda} d\lambda}
\right) \right] \\[1mm]

& \times \exp \left( c-\frac{E}{kT} \right)
dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n}\\[3mm]

= \int &\exp \left( c-\frac{E}{kT} \right)
dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n}\\[1mm]

+ \int & \left[
dc - 2
\left(
E \, d\beta + \beta \sum{\frac{\partial E}{\partial \lambda} d\lambda} +d\beta \sum{\frac{\partial E}{\partial \lambda} d\lambda}
\right) \right] \\[1mm]

& \times \exp \left( c-\frac{E}{kT} \right)
dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n}\\[3mm]


= \ \ \ & 1 \\[1mm]

+ \int & \left[
dc - 2
\left(
E \, d\beta + \beta \sum{\frac{\partial E}{\partial \lambda} d\lambda} +d\beta \sum{\frac{\partial E}{\partial \lambda} d\lambda}
\right) \right] \\[1mm]

& \times \exp \left( c-\frac{E}{kT} \right)
dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n}\\[3mm]


\Downarrow \\[3mm]

0  \ \approx \int & \left[
dc - 2
\left(
E \, d\beta + \beta \sum{\frac{\partial E}{\partial \lambda} d\lambda}
\right) \right]  \exp \left( c-\frac{E}{kT} \right)
dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n}\\

\end{align}

$$ Note: in the line before the $\Downarrow$, the first integrand is the probability density, so its integral over all state space must equal 1. Also, after the $\Downarrow$, we dropped the last term in the square brackets because we ignored terms above first order, i.e. terms containing products of two or more differentials.

Since $\exp \left( c-\frac{E}{kT} \right)$ is never negative, the only way the integral in the last line above can equal 0 is if the expression in square brackets equals 0. Thus:$$
dc -2E \, d\beta - 2 \beta \sum{\frac{\partial E}{\partial \lambda} d\lambda} = 0 \tag{1}
$$ On the other hand, multiplying the equation $dE = \sum{\frac{\partial E}{\partial \lambda}d\lambda} + dQ$ by $2 \beta$ and rearranging gives: $$
-2 \beta \, dE + 2 \beta \sum{\frac{\partial E}{\partial \lambda} d \lambda} + 2 \beta \, dQ = 0 \tag{2}
$$ Adding $(1)$ and $(2)$ eliminates the $\lambda$'s and yields: $$
\begin{align}
0 &= dc - 2E \, d\beta - 2\beta \, dE + 2\beta \, dQ \\[2mm]
&= dc -2 (E \, d\beta + \beta \, dE) + 2 \beta \, dQ \\[2mm]
&= dc -2 \, d(\beta E) + 2 \beta \, dQ \\[2mm]
\implies 2 \beta \, dQ &= d(2 \beta E - c) \\[3mm]
\implies \frac{dQ}{T} &= d \left( \frac{E}{T}-kc \right) := dS
\end{align}
$$ In the last step, we plugged in $\beta = \frac{1}{2kT}$ and then multiplied through by the constant $k$.

We have shown that $\frac{dQ}{T}$ is the total differential of some quantity related to energy and temperature, which we call entropy and denote by $S$. Evidently, $S$ is given by: $$
S = \frac{E}{T} + k \ln \left[ \int e^{\frac{-E}{kT}}dp_1 \, dp_2 \, ... \, dp_{3n} \, dq_1 \, dq_2 \, ... \, dq_{3n} \right]
$$ where we have used the formula for $c$ which was derived above. This entropy equation will be used in the next post on Brownian motion- stay tuned.

Thanks for reading, and please post any questions in the comments section.

Karl and Richard are playing a series to 7 (no need to win by 2) in a two-player game, and their skill levels are such that Karl has a probability $p$ of winning any individual game in the series.

If we give Karl a handicap of 2 games so that he only needs to win 5 games to win the series, whereas Richard needs to win 7, what is the single-game probability $p$ that gives each player a 50% chance of winning the series?

I've tagged this post with "Billiards" since the question came from the director of my pool league (who I hear is an avid GTM reader). Actually, what he really wants to know is the best way to set up the scoring, tie-breakers, and handicaps in one of the leagues, but in order to answer these questions, I wanted to start by looking at just one series and then extend that to the more general questions. This analysis really has nothing to do with pool though, so it would work for any other game as well.

Binomial Coefficients

To start out, we'll need the binomial coefficients $\binom{n}{k}$, which are read as "$n$ choose $k$." $\binom{n}{k}$ is the number of ways to choose $k$ items from a set of $n$ distinct items, for example the number of $k$-person boards of directors that can be chosen from $n$ candidates. Note that choosing the $k$ candidates who are included in the board is the same as choosing the $n-k$ who are not included, which means that $\binom{n}{k} = \binom{n}{n-k}$. The formula for the binomial coefficients is $$\dbinom{n}{k} = \dfrac{n!}{k! (n-k)!}$$ from which the above-mentioned symmetry is obvious. Note that even though this is a fraction, it always comes out to be an integer.

The binomial coefficients got their name from the fact that they are the coefficients in the expansion of binomials: $$ (x+y)^n = \sum_{k=0}^{n}{\dbinom{n}{k} x^k y^{n-k}}
$$ This is because in the product $(x+y)(x+y)...(x+y)$ (with $n$ factors of $(x+y)$), each factor of $(x+y)$ contributes either an $x$ or a $y$ to a factor in the sum. If you have $k$ $x$'s in a term, the other $n-k$ factors of $(x+y)$ must have contributed a $y$. There are $\binom{n}{k}$ ways to get $k$ $x$'s and $n-k$ $y$'s, hence the formula. If anyone wants more detail on that, just ask in the comments, and I'll give a more detailed explanation.

Most identities about binomial coefficients can be proved either by using the formula with the factorials, or via a combinatorial argument. For example, for integers $n$, $m$, and $k$ with $0 \leq k \leq m \leq n$, we have the following identity, known as the subset of a subset identity: $$\dbinom{n}{m} \dbinom{m}{k} = \dbinom{n}{k} \dbinom{n-k}{m-k}
$$Algebraic proof: $$
\begin{align}
\dbinom{n}{m} \dbinom{m}{k} &= \dfrac{n!}{m! (n-m)!} \cdot \dfrac{m!}{k! (m-k)!} \\[3mm]
&= \dfrac{n!}{k!(n-m)!(m-k)!} \\[3mm]
&= \dfrac{n!}{k! (n-k)!} \cdot \dfrac{(n-k)!}{(n-m)! (m-k)!} \\[3mm]
&= \dbinom{n}{k} \dbinom{n-k}{m-k} \tag*{$\square$}
\end{align}
$$Combinatorial proof:
The left side of the identity is the number of ways to choose a board of directors with $m$ members from $n$ candidates, and then choose $k$ executive members from the $m$. The right side counts the number of ways to choose $k$ executive members from the $n$ candidates and then choose the $m-k$ non-executive board members from the $n-k$ remaining candidates. These count the same thing, so the two sides must be equal. $\tag*{$\square$}$

Winning a series to 7

In order to win a series to 7, without needing to win by 2, Karl needs to win 7 games, with Richard winning anywhere from 0 to 6 games in the series. If Karl wins 7 games, and Richard wins 3 games (for example), there will be a total of 10 games in the series. The 3 games that Richard does win can come anywhere in the 10 games, except for the 10th game- if it did, then Karl would have already won 7 and the series would not have made it to 10 in the first place. So we can choose from the first $10-1=9$ games where Richard's 3 wins go.

The probability that Karl wins a given game is $p$, which means the probability that Richard beats Karl is $1-p$. Combining all this, we can see that the probability that Karl beats Richard in a race to 7, with Richard winning 3 games, is $$ \binom{10-1}{3} p^7 (1-p)^3
$$Since Karl can win the series with Richard winning anywhere from 0 to 6 games, the total probability that Karl wins the series is the sum over the possible outcomes, with the summation index $k$ being the number of wins Richard gets in the series: $$
\begin{align}
{\Bbb P}(\text{Karl wins the series}) &= \sum_{k=0}^{7-1}{\binom{7+k-1}{k} p^7 (1-p)^k} \\[3mm]
&= \sum_{k=0}^{6}{\binom{6+k}{k} p^7 (1-p)^k}
\end{align}
$$ Here's a graph of the probability that Karl wins the series, for different values of $p$:


Not surprisingly, if there's a 50% chance that either player wins an individual game, then there's also a 50% chance that either player wins the series.

Now, let's say we give Karl a handicap of 2 games so that to win the series, Karl needs to win 5 games and Richard needs to win 7. More generally, if we call the handicap $H$, where $0 \leq H \leq 6$, then by the same reasoning as we used above, we get the modified formula: $$
{\Bbb P}(\text{Karl wins the series}) = \sum_{k=0}^{6}{\binom{6-H+k}{k} p^{7-H} (1-p)^k}
$$ Now Karl only needs to win $7-H$ games, and so the total number of games in the series for a given value of $k$ wins for Richard, is $7-H+k$, with the $k$ losses once again being placed anywhere but the last game.

Here are the graphs of Karl's probabilities of winning the series given different values of $p$ and $H$ (you can click to expand the picture):


Now, I'd love to be able say we're done here, but the fact is that for some real Karl and Richard, we have no idea what the value of $p$ is unless we are lucky enough to have a history of, say, 100 games between these two players. And even then, they could have improved over time or gotten rusty or whatever so that games they played a few months ago aren't so telling now as to the value of $p$.

We do know that every player in the league is assigned a ranking (which directly determines the handicap against an opponent) which is certainly partly subjective and determined based on observation by a few very experienced players who run, and possibly play in, the league. Instead of trying to guess $p$ and then assigning the rankings, which would be useless in the absence of a large history of games between each set of two players, we can use the handicaps to back out the value of $p$ that makes the match 50-50. For example, if Karl and Richard's rankings are such that Karl gets a handicap of 3, we can see from the graph above that the match will be 50-50 if Karl's probability $p$ of winning an individual game is about 35.5%.

Using Excel's Goal Seek functionality, I've backed out the values of $p$ that make a 7-game series 50-50 for different handicaps:


To test whether a player's handicap is appropriate, one could take all that player's games against opponents of different ranks and see what percentage of individual games he wins and how far off those percentages are from the table above (perhaps using a chi-square test for goodness of fit). If there are not enough games to do this analysis for individual players, then one could start by looking at the percentages for all games and then looking into the ranks furthest away from the table values and seeing if the stats of any particular player(s) are driving the difference. That's a bit of a manual exercise, but it's a start...

GTM Reader Challenge

"Backing out" $p$ basically means finding the inverse of the function $f(p) = \sum_{k=0}^{6}{\binom{6-H+k}{k} p^{7-H} (1-p)^k}$. We know the function has an inverse because if you look at the graphs, they all pass the horizontal line test. To be more rigorous, they are polynomials in $p$ and thus continuous, and $f(0)=0$ and $f(1)=1$, so the intermediate value theorem tells us that $f$ is surjective. Furthermore, $f$ is increasing on the interval $p \in [0,1]$, so it's also one-to-one, and thus has an inverse.

Now, while Excel Goal Seek will certainly work for this, it would be kind of nice to know the inverse function, so I worked for a few hours today trying to figure out how to invert $f$, but couldn't quite figure it out. Maybe one of my more nerdy readers wants to take a crack at it? Otherwise, maybe I'll go post the question on stack exchange...

[Update 7/29/2015: there's been some confusion on the question I'm asking, so just to clarify, for the purposes of finding the inverse of $f(p)$, assume that the $H$ in the formula above is a constant. So technically, there is a different function $f$ for each value of $H$, which I guess you could call $f_{H}(p)$ or something.]

What I was trying (and maybe this isn't the best way to go about it) was to find a not-too-awful formula for the coefficient of $p^n$ in the sum above and then try to use the Lagrange inversion formula, but it gets a bit messy with all the binomial coefficients. I tried to expand the $(1-p)^k$, turning the sum into a double sum, then switch the order of summation (making sure to adjust the summation limits- the Iverson bracket is helpful at this step), and finally simplify somehow using identities of the binomial coefficients such as the subset of a subset identity above, but said simplification proved elusive, so I didn't even bother with the inversion formula.

Anyone have any thoughts on that or maybe a different way to find the inverse of $f(p)$? Let me know in the comments or email me, and I can provide more details of the computation I tried.

Thanks for reading, and I will try to do a follow-up on this post soon. As always, feel free to ask questions in the comments section.

Prerequisites: Power Series, Recursions Part 1

Ok folks, it's been a long and relaxing vacation for me, which is why you haven't seen any new posts in the past 3 weeks. I had intended to do this one Live aus Berlin, but it turned out there was lots of better stuff to do there (including the literally 5 hours I spent at the absolutely fantastic Deutsches Historisches Museum; and I only left because they were closing. I started at Charlemagne at 1 PM and was only half-way through the WW2 section when they closed at 6- I still had the entire GDR and cold war to go...), so this one is coming to you Live aus London instead. Hope that's ok...who am I kidding? I'm pretty sure only like 5 people actually read this anyway, so of course it's ok! Also, those of you who know me won't be surprised to learn that I am writing this from the pub, so just a fair warning that the quality may well deteriorate towards the end...

In the last post, I did a brief overview of how we can use a power series to represent a function, and we wanted the series to converge (pointwise) to our function within a neighborhood of $x=0$, or some other central point. In the post before that, I showed you how to solve a simple recursion. In that post, the recursion we came up with was of degree 1, which means that the $n$-th term depended only on the $(n-1)$-th term, and so we could move them both to the same side of the equals sign to get an expression for the $n$-th difference $R(n)-R(n-1)$. We then summed up the differences to get a formula for $R(n)$ in terms of $n$.

That method was pretty fresh, but if the recursive definition of $R(n)$ includes terms before just $R(n-1)$, for example $R(n-2)$, then this method won't work anymore. What I'm going to show you in this post is one of the most clever things I've ever seen, and it is a very powerful method for dealing with higher-degree recursions (I will specify what this means soon if you haven't guessed it already). Basically, what we are going to do is find a function whose power series $\sum_{i=0}^{\infty}{c_n z^n}$ has coefficients $c_n$ which are the $n$-th terms of the recursion we want to solve. Once we back out the coefficients using Taylor's theorem, we will have solved the recursion. Whoever thought of this was wicked creative (and that's not a subtle self-call, because it definitely wasn't me).

What's interesting is that with generating functions, we just need the power series, but we really won't care when it converges, because we are just using it to back out the coefficients. I'll go into more detail on this point below, but it's a big departure from how we looked at power series before, where we pretty much only cared about if, when, and how (i.e. pointwise, uniformly, etc.) the series converged to our function.

Without further ado, let's get crackin'.

Types of Recursions

I started a bit on this above, but a recursion of degree $d$ is one in which the $n$-th term $R(n)$ depends on only some or all of the terms $R(n-1)$ through $R(n-d)$. So $R(n) = R(n-1) + 4nR(n-3)$ is a recursion of degree 3, for example. Note that for a recursion of degree $d$, we need to be given the values of the first $d$ terms in order to solve it.

A recursion equation is linear if the formula for $R(n)$ is a linear combination of the previous terms, i.e. (for some degree $d$) $$
R(n) = a_{n-1} R(n-1) + a_{n-2} R(n-2) + ... + a_{n-d} R(n-d) + \alpha (n)
$$ where the $a_i$'s can either be numbers or depend on $n$, but can't contain any earlier terms, and $\alpha (n)$ is some fixed function of $n$ called the particularity function. If the latter is just 0, then the recursion (or recurrence, not sure if I'm using the word 100% correctly, but whatever, it's the same thing in my mind) is called homogeneous. If the recursion formula has, for example, products of earlier terms it in, then it isn't linear.

Here are some examples of recursions:

Tower of Hanoi
This one arises when we analyze that game with the 3 rods on which we have discs of varying diameter- you know, this one:
The object of the game is to move all the discs from rod 1 to rod 3 by moving only one at a time from the top of a stack, and with the proviso that we may never place a larger one on top of a smaller one. If there are $n$ discs, then the number of moves $h_n$ it takes to accomplish this is given by the recursion formula $$
h_n = 2h_{n-1} + 1 \\
h_1 = 1
$$See if you can derive this formula on your own by assuming the number of moves for $n-1$ discs is given and then solving the game for $n$ discs. This is a linear, non-homogeneous recursion of degree 1.

Fibonacci Numbers
The Fibonacci numbers are ubiquitous, arising from the problem of reproducing pairs of rabbits, the golden ratio (where you have rectangles consisting of two squares- a curve through their corners is called a Fibonacci spiral), number of binary strings of length $n$ without consecutive 1's, etc. The recursion formula is $$
f_n = f_{n-1} + f_{n-2} \\
f_1 = 1, f_2 = 1
$$ which is linear (with constant coefficients, i.e. they don't depend on $n$ as the coefficients are both 1) of degree 2 and homogeneous.

Catalan Numbers
These are ubiquitous in the field of combinatorics, arising from all sorts of counting problems. The recursion formula is $$
C_n = C_0 C_{n-1} + C_1 C_{n-2} + ... + C_{n-1} C_0 \\
C_0 = 1
$$ which is non-linear, not of finite degree (because the number of previous terms in the formula depends on $n$), and homogeneous.

Generating Functions

Now that we've defined what types of "harder" recursions we can encounter, let's move on to the main topic, which is solving them using generating functions.

A generating function for a recurrence $R(n)$ is a formal power series $\sum_{i=0}^{\infty}{c_n z^n}$ where the $n$-th coefficient $c_n$ is equal to the $n$-th recurrence value $R(n)$ for every value of $n$. Technically, I have defined an ordinary generating function (OGF); there are other types such as exponential and Poisson generating functions which are easier to apply in different situations, but they all have the same idea of the $n$-th coefficient's coinciding with the $n$-th thing that we are looking for. I'm only going to talk about OGF's in this post.

In the definition above, I mentioned a formal power series. What this is is a power series where we don't care at all about whether it converges or, if so, for which values of $z$. Basically, we are just going to use the $z$'s as a tool to help keep track of our coefficients $c_n$ without any regard for the convergence properties of the series.

To add and subtract two formal power series, we just add/subtract the coefficients of the terms with the same power of $z$, and to multiply them, we use the distributive property- basically, all the same way that we would do it for a regular power series. The same applies to taking derivatives and integrals of the series.

To show how to use OGF's to solve a recursion, let's take as an example the following linear, homogeneous recursion of degree 2: $$
g_n = 5g_{n-1} - 6g_{n-2} \\
g_0 = 1, g_1 = 2
$$ What we need to do is find a function $G(z)$ which has a power series whose $n$-th coefficient is equal to $g_n$.

Here's how it's done. We'll multiply both sides of the recursion equation by $z_n$, sum them from $n = 2$ to $n = \infty$ (starting at 2 because the the recursion formula starts at $n=2$, with $g_0$ and $g_1$ given), and then get an algebraic expression in terms of $G(z)$. Heeeeeeeeeere we go:$$
\begin{align}
g_n &= 5g_{n-1} - 6g_{n-2} \\[3mm]

g_n z^n &= 5g_{n-1}z^n - 6g_{n-2}z^n \\[3mm]

\sum_{n=2}^{\infty}{g_n z^n} &=
\sum_{n=2}^{\infty}{5g_{n-1}z^n} - \sum_{n=2}^{\infty}{6g_{n-2}z^n} \\[3mm]

\sum_{n=2}^{\infty}{g_n z^n} &=
5z \left( \sum_{n=2}^{\infty}{g_{n-1}z^{n-1}} \right) -
6z^2 \left( \sum_{n=2}^{\infty}{g_{n-2}z^{n-2}} \right) \\[3mm]

\sum_{n=0}^{\infty}{g_n z^n} - g_1 z - g_0 &=
5z \left( \sum_{n=1}^{\infty}{g_{n-1}z^{n-1}} - g_0 \right) -
6z^2 \left( \sum_{n=2}^{\infty}{g_{n-2}z^{n-2}} \right) \\[3mm]

G(z) - g_1 z - g_0 &=
5z \left( G(z) - g_0 \right) -
6z^2 \left( G(z) \right) \\[3mm]

G(z) (1 - 5z + 6z^2) &= g_1z + g_0 - 5g_0 z \\[3mm]

G(z) &= \dfrac{(g_1 - 5g_0)z + g_0}{1- 5z + 6z^2}\\[3mm]

G(z) &= \dfrac{(1 - 3z)}{1- 5z + 6z^2} \\[3mm]

G(z) &= \dfrac{(1 - 3z)}{(1 - 3z)(1 - 2z)} \\[3mm]

G(z) &= \dfrac{1}{1 - 2z} \\[3mm]

G(z) &= \sum_{n=0}^{\infty}{2^n z^n}

\end{align}
$$ Note that in the last step, we used the known power series $$\dfrac{1}{1-x} = \sum_{n=0}^{\infty}{x^n}$$ and substituted in $2z$ for $x$.

Now, as discussed in the Power Series post, this series only converges when $|x| < 1$ or $|z| < \frac{1}{2}$. But guess what? WE DON'T CARE! Because this was just a way to get the coefficients, and we got them. Thus we have solved the recursion; the solution is $$
g_n = 2^n
$$ for all values of $n$. You can verify this by plugging the answer back into the recursion equation, and you'll see that both sides of the equals sign balance.

So that is pretty awesome and illustrates the idea behind OGF's. If you don't think that was wicked cool, then I would have to recommend more..."primitive" forms of entertainment for you, such as MTV's hit series Jersey Shore (which, I must admit, I am a big fan of myself...).

Now, the astute reader probably did think that was wicked cool, but is still just a tad bit bugged by the fact that this example was so obviously contrived so that $G(z)$ had a denominator which factored easily to give a really simple answer.

The astute reader is correct. If we look at the exact same recursion, except change one of the initial conditions from $g_0 = 1$ to $g_0 = 0$, we can repeat the exact same process to arrive at $$
G(z) = \dfrac{2z}{(1-3z)(1-2z)}
$$ which does not easily reduce to a known power series.

But not to worry; we can use a method called partial fraction decomposition to rewrite this quotient as $$
\begin{align}
G(z) &= \dfrac{2}{1-3z} + \dfrac{-2}{1-2z}\\[3mm]
G(z) &= \sum_{n=0}^{\infty}{2 \cdot 3^n z^n} + \sum_{n=0}^{\infty}{(-2) 2^n z^n} \\[3mm]
&\Downarrow \\[3mm]
g_n &= 2 \cdot 3^n - 2^{n+1}
\end{align}
$$ Now, I don't really want to go into detail about partial fraction decomposition, because it's not that exciting, and you can look it up really quickly on Google if you want to know more about it. But I did want to point it out as a useful method when you end up with $G(z)$'s for which you can't just factor the denominator and then use the known power series for $\dfrac{1}{1-x}$.

Another thing I want to point out here is that, although we just looked at an example of a homogeneous recursion, the OGF method also works for non-homogeneous recursions such as the Tower of Hanoi one above.

If you work out the same steps for that one, you'll get the generating function $$
H(z) = \dfrac{z}{(1-z)(1-2z)} = \dfrac{1}{1-2z} - \dfrac{1}{1-z}
$$ and thus $h_n = 2^n - 1$, once again by using the known series of $\dfrac{1}{1-x}$.

Just to sum up here, I'll show you the OGF's of the Fibonacci and Catalan numbers mentioned above.

For the Fibonacci's, the OGF is $$
F(z) = \dfrac{z}{1-z-z^2}
$$ You need to use a partial fraction decomposition to extract the coefficients, which turn out to be $$
f_n = \dfrac{1}{\sqrt 5} \cdot (\gamma^n - {\hat{\gamma}}^n)
$$ where $\gamma$ is the golden mean $\dfrac{1+\sqrt 5}{2}$, and $\hat \gamma$ is its conjugate $\dfrac{1-\sqrt 5}{2}$. This formula for $f_n$ is called the Binet formula for the Fibonacci numbers, named after Jacques Binet, who rediscovered it in 1843 after, you guessed it, our prolific friend Euler had published it in 1765.

I also used the Catalan numbers as an example, and you can click here to see the generating function and formula for these, from the very cool math blog of a guy named Mike Spivey. Who knew there was another math blog out there? Well, there you have it, there is! [Update: as I mention in the comments in response to Joe's question, I didn't do any research on the history of the Binet formula above when I first wrote this post, but now that I have looked into it, I found an interesting history of collaboration as well as independent discovery among famous mathematicians in various nations (frequently at war with each other during the period of European history in question) as they encountered these prolific number sequences and developed generating function and other methods in the 18th and 19th centuries. Here is a link to a good history of the Catalan numbers.]

And with that, there you have it- that's the end of this post. I hope you enjoyed it and thought that OGF's are as cool as I think they are. Just another example of how math and creativity are abolutely NOT mutually exclusive (in fact, quite the opposite, though I must admit that I myself have zero creativity and just copy most of this stuff from somewhere else that I've seen it...)!

Thanks for reading, and please post any questions in the comments section.

As the title suggests, this post is going to cover power series, and while I haven't listed any prerequisites at the top, this will probably be a bit "hand-wavy" for those who have not seen sequences/series or calculus before. Sorry, but I am not going to write a series of posts on these topics, because it will take a long time and is already covered all over the internet, but for a refresher on that, I would direct you to Paul's Online Math Notes, which is a great website written by a math professor at Lamar University and actually where I originally learned this post-calculus I stuff. He has a whole section on sequences and series as part of an entire online course on calculus I-III. I'll also address any specific questions in the comments section, so feel free to ask there.

So, why am I writing this post at all? As of today, June 12th, 2015, there were 83 page views on the previous post about solving a recursion, making it one of the most popular to date given the short period of time it's been up. In that post, we went through how to solve a simple recursion by shuffling terms around to arrive at a sum in terms of the differences between successive terms. This method, sweet though it is, does not work for more complicated recursions, but there is a super clever method to solve the latter by finding their "generating function," which is actually so clever that it's going to blow your mind. That will involve a sort of "stepchild" of power series, so this post is really going to serve as a refresher and prerequisite for that. The idea of a power series (and other series representations of functions, e.g. Fourier series) is also really cool in its own right, and was in fact a reader request (ok well, technically, a request from a guy who not only doesn't read this, but also said he still won't read it even if I make a post about power series), so even if said "reader" doesn't see it, it's still a solid topic.

The sum of an infinite series

To talk about power series, we need to have a notion of the sum of an infinite series. A series is a sum of an infinite list of numbers (said list, without the sum, is called a sequence). If that sequence is the list of numbers $(a_n)_{n \in {\Bbb N}}$ (and notice I've used a common notation for sequences here- this means the list of terms $a_n$ with the index $n$ encompassing the counting numbers ${\Bbb N} = \{ 0,1,2,3,... \}$), then the series would be written as the infinite sum $$
\sum_{n=0}^{\infty}{a_n}
$$ To be precise, this infinite sum, like all infinite things in the study of real numbers, really refers to a limit of finite sums. In particular, the sum $\sum_{n=0}^{\infty}{a_n}$ is the limit as $N$ goes to infinity, of the sequence of partial sums $S_N = \sum_{n=0}^{N}{a_n}$. Get it? The partial sums are a sequence, and the sum of the infinite series is the limit of the sequence. In symbols, $$
\sum_{n=0}^{\infty}{a_n} \buildrel {\scr def} \over{=}
\lim_{N \rightarrow \infty} S_N = \lim_{N \rightarrow \infty} \sum_{n=0}^{N}{a_n}
$$ Note that the symbol $\buildrel {\scr def} \over{=}$ stands for "equals by definition." Clearly, in order for this sequence of $S_N$'s to converge to a (non-infinite) number, the numbers $S_N$ need to "level off" and stop getting bigger.

The difference between $S_{N+1}$ and $S_N$ is $a_{N+1}$, so in order for the partial sums to level off, we need the terms to get smaller, or technically closer to zero (i.e. $|a_n|$ gets smaller) since we could be talking about negative numbers, not just positive. So in order for the sum of the infinite series to exist, it must be the case that $\lim_{n \rightarrow \infty} |a_n| = 0$. By the way, when the differences $|S_{N+1} - S_N| \rightarrow 0$ as $N \rightarrow \infty$, we say that the sequence $(S_N)_{N \in {\Bbb N}}$ is a Cauchy sequence, named after Augustin-Louis Cauchy, one of the pioneers of analysis, the field of math that made a lot of our intuition about the number line (and functions thereof and calculus) rigorous. Without analysis, we wouldn't be able to have a lot of the modern theory that's extensively used in practice today, like the Black-Scholes formula and all the other stochastic calculus for example. So the guy is a big deal. Now, I'm not going to go into it now, but I did want to point out that there will probably be not just one, but a whole series of posts on the real numbers later, and in those we'll go into more detail about sequences' converging. It turns out that sequences of real numbers converge to a limit if and only if they are Cauchy sequences. It kind of makes sense, because if the terms of the sequence aren't eventually getting closer and closer together, then how can they possibly be converging to a limit? But that intuition requires some proving which I'm not going to get into right now. Anyway, onwards with the whole series thing.

Now, it turns out that just the fact that $\lim_{n \rightarrow \infty} |a_n| = 0$ isn't enough to guarantee that the series converges. The $a_n$'s need to go to zero fast enough. As an example, take the series $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n} + ...$. Here, the terms certainly approach zero in absolute value since $\frac{1}{n}$ gets smaller and smaller as $n \rightarrow \infty$, but they don't go to zero fast enough for the series to have a finite sum. To prove this, note that $$
\begin{align}
&1 + \frac{1}{2} + (\frac{1}{3} + \frac{1}{4}) + (\frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8}) + (\frac{1}{9} + ...\\[3mm]
> \ &1 + \frac{1}{2} + (\frac{1}{4} + \frac{1}{4}) + (\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}) + (\frac{1}{16} + ...\\[3mm]
= \ &1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + ...
\end{align}$$ which clearly just keeps adding up to bigger and bigger partial sums and thus diverges.

On the other hand, the series $$1 + \frac{1}{2^2} + \frac{1}{3^2} + ... + \frac{1}{n^2} + ...$$ does converge, and its sum is $\dfrac{\pi^2}{6}$. The proof of this is pretty slick, and of course the first one to come up with it was Euler in 1735 (though he didn't come up with a truly rigorous proof until 1741). I mean, seriously, this guy was an absolute animal- they didn't even have light bulbs yet, and he came up with this ridiculous sum. Anyway, the series $$\sum_{n=0}^{\infty}{\dfrac{1}{n^p}}$$ is called a $p$-series and converges if and only if $p>1$. I'm not going to get into the proof, but it's a nice example of the "going to zero fast enough" thing. As it turns out, there are a whole slew of tests to see if a series converges- the integral test, the alternating series test, the comparison test, etc. You might remember them from your calculus II class. They aren't that exciting, but I just wanted to mention all the above, because it is important when it comes to understanding what we're talking about when we speak of a power series and the convergence properties thereof.

Speaking of power series, let's move on to those now, but if there are any questions on the above discussion, the comments section is the place to ask.

Approximating a function using polynomials

A polynomial is a function of the form $p(x) = c_0 + c_1 x + c_2 x^2 + ... + c_n x^n$. The $c_i$ numbers are called coefficients, and the degree of the polynomial is the highest power of $x$ with a non-zero coefficient.

Polynomials are pretty easy to work with (and, in particular, to differentiate and integrate), so they are a decent choice if we want to approximate another function. If you look at the animated diagram below, you'll see the function $f(x) = e^x$ in blue, and in red, approximations of $f(x)$ using polynomials of increasing degree. This is a great animation ("borrowed", as usual, from Wikipedia, thank you very much) which really demonstrates the main idea I want to get at.

If we look around $x=0$, the approximation is pretty good, and gets better as we increase the degree of the polynomial approximation. When $n=0$, it's the dumbest imaginable "approximation" of $f$: a flat line at the level $f(0)$. For $n=1$, we have a line passing through $f(0)$ and having the same slope as $f$ at that point. A little better...The higher degree approximations take into account more and more of the curvature properties of $f$ and thus begin to "hug" the curve better around $x=0$, and actually further out as well.

This line of reasoning raises an interesting question: if we let the degree of the polynomial approximation approach infinity (and we'd have to really think carefully about what that would entail), could we get an "infinite polynomial" (whatever that means) that is exactly equal to our function for all values of $x$, or at least in a neighborhood of $x=0$?

In order to understand these types of objects, we'll need to make use of the section above in order to actually make sense of such an infinite polynomial. Because this thing is a series involving powers of $x$, it's called a (yes, this is what we've been waiting for...wait for it...) power series.

Power series

Ok, I may have been a bit hasty with the boldface font up there, because I still haven't told you exactly what a power series is. To define it more precisely, a power series is a function of the form $$
p(x) = \sum_{n=0}^{\infty}{c_n x^n}
$$ where the coefficients $c_n$ are some numbers which may depend on $n$ (but which do not depend on $x$).

For a given value of $x$, the numbers $c_n x^n$ are just some new numbers, which we could just as well call $a_n$, and now we are looking at the exact same thing as in the first section about infinite series of numbers. The same rules apply about convergence, which is really the key topic here, since the whole point was to come up with a power series which converges, at least for certain values of $x$, to the value of some other function $f(x)$.

It's worth noting that we are talking about a particular type of convergence here which, in the field of analysis, is called pointwise convergence: at each point $x$, we want the sequence (it's a different sequence of numbers for each value of $x$) of partial sums $$
p_{N}(x) = \sum_{n=0}^{N}{c_n x^n}
$$ to converge to the limit $f(x)$. There are other types of convergence such as uniform convergence, $L^2$-convergence, etc., which I'm not going to go into, but it is important to be clear about what is meant when one says "convergence" in the context of functions; indeed, you often hear of a sequence of functions $p_{n}(x)$ converging to a (limit) function $f(x)$. This could be interpreted in the sense of pointwise convergence, which would mean that the sequence of numbers $p_{1}(x), p_{2}(x), ...$ converges to the number $f(x)$ for each value of $x$, or it could mean that over the range $0 \leq x \leq 1$, the the maximum difference between the $p_{n}(x)$'s and the $f(x)$'s approaches 0 in some way as $n \rightarrow \infty$. Anyway, this is all very detailed, but I'm mentioning it so that you understand we are talking about pointwise convergence and not something else. So with that, let's get back to the discussion at hand.

Given a function $f(x)$, we are looking for some coefficients $c_n$ which make the series $p(x) = \sum_{n=0}^{\infty}{c_n x^n}$ coverge (pointwise) to $f(x)$ for every value of $x$, or at least for some values of $x$ close enough to $x=0$.

As an example, you might recall from precalculus or a similar class in high school, that a geometric series is a series whose terms are $a_0 = a, \ a_1 = ar, \ a_2 = ar^2, \ ... \ , \ a_n = ar^n, \ ... $ where $r$ is a fixed ratio and $a$ is some fixed first term. Clearly, if $|r| \geq 1$, then the terms of the series $\sum_{n=0}^{\infty}{ar^n}$ do not get closer to zero as $n$ gets larger, which means the series diverges, i.e. does not converge to a finite limit. If $|r| < 1$, then the series does converge, and the sum is $\dfrac{a}{1-r}$. To prove this, note that $$
\begin{align}
\sum_{n=0}^{N}{ar^n} &= a + ar + ar^2 + ar^3 + ... + ar^N \\[3mm]
&= a (1 + r + r^2 + r^3 + ... + r^N) \\[3mm]
&= a \dfrac{1-r^{N+1}}{1-r} \tag{$\clubsuit$} \\[3mm]
\end{align}
$$ where $(\clubsuit)$ is true because if you multiply $(1-r)$ by $(1 + r + r^2 + ... + r^N)$, you'll see that you get $1-r^{N+1}$. We're also assuming that $|r| < 1$ so that $1-r \neq 0$ and thus it's safe to divide by it in equation $(\clubsuit)$. So anyway, now we have $$
\begin{align}
\sum_{n=0}^{\infty}{ar^n} &= \lim_{N \rightarrow \infty} \sum_{n=0}^{N}{ar^n} \\[3mm]
 & \buildrel (\clubsuit) \over {=} \lim_{N \rightarrow \infty} a \dfrac{1-r^{N+1}}{1-r} \\[3mm]
&= a \lim_{N \rightarrow \infty} \dfrac{1-r^{N+1}}{1-r} \\[3mm]
&= a \dfrac{1}{1-r} \\[3mm]
&= \dfrac{a}{1-r}
\end{align}
$$ since $r^{N+1} \rightarrow 0$ as $N \rightarrow \infty$, and the rest of that fraction is independent of $N$. So that's a neat little formula, but if we change the name of $r$ to $x$ (and there's no reason we can't do that) and take the particular case of $a=1$, then we have shown that for values of $x$ in the range $|x|<1$ (i.e. $-1 < x < 1$), the power series $$ \sum_{n=0}^{\infty}{x^n} $$ converges pointwise to the function $f(x) = \dfrac{1}{1-x}$. Since the power series representation only works for $-1 < x < 1$, we say that the series has a radius of convergence of 1.

There are lots of common functions with known power series representations, such as $e^x$, $\cos x$, $\sin x$, etc. In fact, combining those 3, you can prove the famous identity involving everyone's favorite math symbols, $e^{i \pi} = -1$. What??? Yup, it's true, as weird as it is.

Those readers who are familiar with calculus can go ahead and keep reading here, though the above is all you will need for Recursions Part 2.

Now that we've gone through approximating a function with polynomials of increasing degree, I just want to point out 3 more things.

The first is that if $f(x) = \sum_{n=0}^{\infty}{c_n (x-c)^n}$ has a radius of convergence $R$ (and note here that I've generalized a bit and centered the series around $x = c$ instead of $x=0$), then the derivative of the function is $f'(x) = \sum_{n=0}^{\infty}{n c_n (x-c)^{n-1}}$, and there's a similar formula for $\int f(x) dx$. Furthermore, both of these also have radius of convergence $R$. Note that since we are dealing with infinite series, not finite sums, these two facts are not trivial, and you have to go through a little limit of partial sums argument to prove them.

The second point is that if a function $f(x)$ is $k$ times differentiable at a point $c \in {\Bbb R}$, then there exists a remainder function $R_{k}(x)$ such that the $k$-th order Taylor polynomial $$ \sum_{n=0}^{k}{\dfrac{f^{(n)}(x-c)}{n!}(x-c)^n} $$ is within $R_{k}(x-c)^k$ of $f(x)$, and the remainder goes to 0 as $x \rightarrow c$. Here, $f^{n}(x-c)$ denotes the $n$-th derivative of $f$ evaluated at the point $x-c$. There are a few subtleties, but intuitively, these Taylor polynomials represent increasingly accurate polynomial approximations as in the earlier diagram. If a function is infinitely differentiable at $x=c$, then (ignoring the subtleties once again) you can let $k$ go to $\infty$ to obtain the Taylor series of $f$. For "nice enough" functions, i.e. ones that aren't contrived to be counterexamples, the Taylor series converges to $f$, but there are a few wacky examples where it actually converges to something else. But that's Taylor's Theorem for you, which basically provides us with a formula to find the $c_n$'s we wanted in order to approximate a function using polynomials.

The third and final point before we wrap up is that there are other types of series that approximate functions as well. A notable example is Fourier series, which are very important in the world of digital signals. A Fourier series approximates a function using sine waves of different frequencies. The details of how this works could be an entire post, but just look at this picture of the first four partial sums of the Fourier series for the square wave function, and it will kind of make sense:


Then there's the sort-of-related Fourier transform, which decomposes a signal into its constituent frequencies, and which can be seen as a sort of limit of Fourier series (which are sums) into integrals.

Ok, that's enough of this topic. I hope you enjoyed it if you made it this far, and I did go through it pretty fast, so feel free to ask any questions that are still lingering in your mind in the comments section.

Prerequisites: Induction

For those of you who have never heard of it, the Putnam exam is a test for college students (mostly math majors) that universities throughout the country compete in. The test is hard- there are 12 questions (in two sets of 6, for which you get three hours per set), and the median score is 0. I've taken it a few times myself, and I think my record was 2 questions correct, which I was pretty pleased with.

Anyway, a lot of schools have a team that prepares for this test (at Dartmouth, this consisted of a bunch of people gathering for free Raymunto's pizza, which is a surefire way to get folks to show up there), and consequently, you can find a lot of the practice problems on the internet. In fact, you can find archives of past Putnam exams and solutions online, for example, here.

Anyway, the reason I mentioned all this is that I found the following problem in a Putnam practice document from Northwestern:

There are $n$ great circles drawn on the surface of a sphere such that no more than 2 intersect at any point. Into how many regions do the circles divide the surface of the sphere?

Now, I'll get to explaining what a great circle is in a second, but first, I'll explain what made me want to write a post about this problem in the first place. Obviously, the solution must be some function of $n$. Ok, great. But what really #GroundMyGears was that in the solutions in this document, they basically looked at the first few cases, $n=1,2,3,4,...$, guessed the answer, and then proved it was correct by induction. Don't get me wrong- this was all correct and everything, but I just felt like guessing the answer and then proving it works by induction was kind of a cop-out in this case. So I worked out the same answer in what I thought was a more satisfying way, and that's what I'm going to show you here. This method works for other recursions as well, so it may actually be useful to you some day.

Ok, first of all, I just said it, and it's in the title of the post, so what is a recursion? A recursion defines an object in terms of itself.

What???

Ok, maybe best to use an example here, and I promise you'll see what I mean: the factorial of a positive integer $n$, denoted $n!$, is defined as the product of the positive integers 1 through $n$. In symbols, $n! = n(n-1)(n-2)...(3)(2)(1)$, or more succinctly, $n! = \prod_{i=1}^{n}{i}$. Here's where it gets interesting: factorials can be defined in terms of themselves as follows: $$
1! = 1 \\
\forall n > 1, n! = n \cdot (n-1)!
$$ Clearly, this gives the same definition as above, but now we've defined the factorial function in terms of itself, but for smaller values of the input variable. This is crucial in computer science, where we can use this method to specify infinitely many (or more precisely, an arbitrarily large number of) objects in a finite number of steps.

Recursion is also very closely related to induction. Properties of recursively defined functions and sets can often be proved by an induction argument that follows the recursive definition (sentence copy/pasted from Wikipedia, thank you very much). A recursive function definition always needs a base case whose value is specified, and then an inductive definition of the function for greater input values, in terms of the values of the function for smaller inputs.

Hopefully the above got the point across (if not, leave a question in the comments section). Let's shift gears now and talk about great circles.

A great circle of a sphere is a circle drawn on the surface of the sphere, whose center coincides with the sphere's center. All great circles have the same radius and diameter as the sphere itself. Another way to put it is that a great circle is the intersection of a sphere and a plane which passes through its center. These are the largest circles that can be drawn on the surface of a sphere. Smaller circles (called small circles) arise when a plane intersects a sphere and does not pass through its center. In the diagram below, the red circle is a great circle, and the blue one is a small circle:

The equator and meridian are examples of great circles on the surface of the earth. While I'm talking about great circles, it's worth mentioning, though we won't need it in this post, that the shortest path between any two points on the surface of a sphere is the great circle arc (i.e. piece of the great circle) connecting them. It's also worth mentioning (and we will need this fact) that any two great circles intersect at two points (can you see why?).

On that note, let's get back to the question about $n$ great circles on the surface of the sphere. Let's call the number of regions on the surface after we've drawn $n$ great circles $R(n)$. With one circle, the sphere is divided into 2 halves, or hemispheres (hemi- is a prefix that means half, as do demi- and semi- by the way, but for some reason, the word turned out to be hemisphere and not semisphere or demisphere...). So $R(1)=2$.

If we add a second circle, it will intersect the first at 2 points, cutting the existing two regions into 4, so $R(2)=4$. Now, a third great circle will intersect the first two at 2 points each. Remember that the question prohibited an intersection at the existing intersection points (if it hit one, it would hit both), so the third circle again cuts the existing regions each in two, implying $R(3)=8$.

Things get trickier on the fourth circle, which is tougher to picture without a diagram. See the green and red circles in the below diagram, which are the fourth and fifth great circles drawn on the surface after the first 3 black ones:
Note first of all that the fourth circle (and each one thereafter) does not intersect every existing region. The fourth circle intersects 6 of the 8 existing regions, and in fact, since each great circle is the intersection of a plane with the sphere, the fact that the fourth circle hits 6 regions is explained in the post The Plane in ${\Bbb R}^3$- I'll leave it to you to explore the connection there (and it actually does not depend on the angles the first three planes make with each other). So the fourth circle adds 6 new regions (one for each of the 6 it intersected and thus cut into two) so that $R(4)=8+6=14$.

In general, we can see by the same logic that the $n^{\scr th}$ circle intersects each of the existing $n-1$ circles twice. Since none of those intersection points existed before drawing the $n^{\scr th}$ circle (because if one had, then we'd have three circles intersecting at one point, which isn't allowed), there must be $2(n-1)$ intersection points of the $n^{\scr th}$ circle with the original $n-1$ circles.

Also, you can see from the diagram that when we draw the $n^{\scr th}$ circle, each set of two new intersection points breaks the $n^{\scr th}$ circle into an arc which cuts one of the existing $R(n-1)$ regions into two new ones. The number of regions the circle intersects (and thus cuts into two) is $2(n-1)$, because if we walk around the $n^{\scr th}$ circle, there is one region after each of the $2(n-1)$ intersection points with the other circles.

The above two paragraphs give us our recursion: $$
\begin{align}
R(n) &= R(n-1) + 2(n-1), n \geq 2 \tag{1}\\[2mm]
R(1) &= 2 \tag{2}
\end{align}
$$ Note that we need only one initial condition because there is only an $R(n-1)$ term in the recursion equation. If there were also an $R(n-2)$ in there, we'd need both $R(1)$ and $R(2)$ to determine the value of $R$ for all values of $n$. So now that we have our recursion, let's solve the thing. For $n \geq 2$, rearranging $(1)$ gives $$R(n) - R(n-1) = 2(n-1) \tag{3}
$$ Since $(3)$ holds for every $n \geq 2$, we have $$
\begin{align}
R(n-1) - R(n-2) &= 2(n-2) \\[3mm]
R(n-2) - R(n-3) &= 2(n-3) \\[3mm]
\vdots \\[3mm]
R(2) - R(1) &= 2(1)
\end{align}
$$ Therefore: $$
\begin{align}
R(n) &= R(n) + 0 \\[3mm]
&= R(n) + (-R(n-1)+R(n-1)) + (-R(n-2)+R(n-2)) + \cdots + (-R(2)+R(2)) + (-R(1)+R(1)) \\[3mm]
&= (R(n)-R(n-1)) + (R(n-1)-R(n-2)) + \cdots + (R(2)-R(1)) + R(1) \\[3mm]
&\overset{(3)}{=} 2(n-1) + 2(n-2) + \cdots + 2(1) + R(1) \\[3mm]
&\overset{(2)}{=} 2(n-1) + 2(n-2) + \cdots + 2(1) + 2 \\[3mm]
&= \left( 2 \sum_{i=1}^{n-1}{i} \right) + 2 \\[3mm]
&= 2 \left( \dfrac{(n-1)(1+(n-1))}{2} \right) + 2 \tag{$\spadesuit$}\\[3mm]
&= (n-1)n+2 \\[3mm]
&= n^2 - n + 2
\end{align}
$$ where the equality $(\spadesuit)$ is because of the fact that an arithmetic series, i.e. a sum of $N$ terms, the first of which is $a_1$, the last of which is $a_N$, and with the difference between successive terms being a constant, has $\dfrac{N(a_1 + a_N)}{2}$ as its sum. Can you prove why?

So now we've solved for $R(n)$ for every value of $n$ using the recursion equation $(1)$ and the initial condition $(2)$.

I hope you found this interesting and maybe even useful. Thanks for reading, and please post any questions or comments in the comments section.

Prerequisites: Pool Part 1, Similar Triangles

In part 1, we showed how to pocket an object ball with some basic physics. In part 2, we'll derive simple methods for making bank and kick shots using similar triangles.

For all of the below, we'll assume, unless explicitly stated otherwise, that we can ignore the effects of spin on the balls that would alter their trajectories. In practice, English (side-spin) as well as topspin and backspin (sliding) will affect the trajectories and need to be taken into account for more complicated shots. For example, if the target ball is to be banked off a rail very close by, it will still be sliding upon contact, which changes its trajectory coming off the rail. Ball speed also affects the trajectory off the rails, since a faster ball compresses the rail more and changes the angle a bit. We'll ignore these effects in our analysis, which should suffice for most easier bank and kick shots you'll encounter, where you just need to hit the cue ball with medium speed and at center. If any good players are reading this, commentary is welcome on how to use spin on some of these shots.

The one-rail bank

In part 1, we looked at a straight shot into the side pocket. Now, suppose we have the following situation where the purple 4 ball is blocking the line to the side pocket:
We need to find an alternative to the shot from part 1. One solution would be to take the long-distance shot to the top-right corner pocket, but we're going to look at an alternative, the bank shot, where we hit the 2 off the top rail and into the bottom side pocket.

The key to executing this shot is the reflection principle, that the 2 will bounce off the rail at the same angle with which it bounces into the rail- angle in equals angle out. The problem is to find the correct point on the rail to hit the 2 into, where angle in = angle out will get the ball on a trajectory to the side pocket.

Take a look at the following diagram, which is the same layout, but with two triangles drawn on.
The angle $\theta$ is the angle in and out. If the contact point with the rail, $Q$, is chosen correctly, then the angle $\theta$ will be the correct one to send the 2 to the target pocket. Now, because the two $\theta$ angles are equal and the yellow line is drawn at a 90 degree angle to the rail, we know that angles $OQP$ and $SQR$ are also equal. Since angles $OPQ$ and $SRQ$ are both right angles and thus equal, the triangles $OPQ$ and $SRQ$ are similar by angle-angle.

Let's use the notation $L(\overline{AB})$ for the length of a line segment $\overline{AB}$. The similarity of triangles $OPQ$ and $SRQ$ implies that the ratios $\dfrac{L(\overline{PQ})}{L(\overline{QR})}$ and $\dfrac{L(\overline{OP})}{L(\overline{SR})}$ are equal.

Remember that $Q$ is still at an unknown position, but given the equality of those ratios, we can find it. $L(\overline{OP})$ and $L(\overline{SR})$ are known lengths, which can be measured in units of segments. One segment is the distance between two of the white diamonds (or sometimes they are circles) running along the sides of the table. In the diagram above, $L(\overline{OP})$ is just shy of 2 segments, and $L(\overline{SR})$ is just shy of 4 segments. Thus $\dfrac{L(\overline{PQ})}{L(\overline{QR})} \approx \dfrac{1}{2}$. Since $L(\overline{PR})$ is about 2 segments, we see that the correct position for $Q$ puts $L(\overline{PQ}) \approx \dfrac{2}{3}$ and $L(\overline{QR}) \approx \dfrac{4}{3}$.

Alternative method: parallel shifts

The ratio calculation above is relatively simple and works, but can be a bit annoying to work out while playing. There is an alternative method that achieves the same result without having to think about any ratio calculations.

Below is the same diagram as the previous one, but with the blue lines added in:
The slope of line $OQ$ is the same as the slope of line $MR$, i.e. the lines are parallel. You can prove this by assigning coordinates to each of the points and calculating the two slopes (it's probably easiest to assign $O=(0,0)$ and go from there). This being the case, we have an easier method for finding point $Q$:

1. Find the midpoint $M$ between the 2 ball and the target pocket.

2. Make a line (with your cue stick) from $M$ to the opposite pocket.

3. Move your cue, keeping it parallel, over to the 2 ball, and where it intersects the top rail is the target contact point $Q$.

A similar method will work for kick shots as well.

The one-rail kick

The kick shot is similar to the bank, except we hit the cue ball off a rail and into an object ball, as opposed to the bank, where we hit the cue ball straight into the object ball, which then bounces off a rail.

Take a look at the following diagram:
Here, we have the cue ball and 2 ball in the same places as before, but the cue ball's line to the 2 is blocked by the purple 4. In order to make contact with the 2, we need to hit the cue ball off a rail first to avoid hitting the 4 before the 2 (for example, if we're playing 9-ball, where you need to hit the lowest-numbered ball first or else give your opponent ball-in-hand).
The red triangles above show a set-up just like the bank above, with the two red triangles being similar. Now, instead of going to a pocket, the blue line goes to the point where the target ending spot lines up with the rail. I won't go through the whole thing again, since it's basically the same thing. Find $M$, draw a line from $M$ to the spot where the target ending position lines up with the rail, and parallel shift the line over to the cue ball to see where it needs to hit the rail.

The two-rail kick

This is a very difficult shot, but if you can make contact on these, then you'll save yourself from giving a good opponent ball-in-hand and running the table on you. Suppose we now have this set-up where there is no way to execute a one-rail kick and hit the 2 first:
Once again, the translucent cue ball is the desired position of the cue ball at contact, and as you can see, the only way to get it there is by hitting the cue ball off of at least two rails. We'll start by drawing a diagram similar to the ones above:
Note that this diagram is not exactly to scale, so some of the lines that should be parallel look a bit off. The same reason it is difficult to draw the diagram is the reason that this shot is trickier to work out than the one-rail kick: we need to work out the unknown contact point $C$, but the trouble is that a change in $C$ changes the angle off the bottom rail and thus also changes the unknown contact point $E$ on the second rail.

The reflection principle will hold at both $C$ and $E$, and we need to work it out so that the cue ball ends up at $G$. The three red triangles are all similar by angle-angle, and this fact gives us a few equations we can use to solve for the location of point $C$.

Define $x_1$ to be the length $L(\overline{BC})$ (unknown), $L_1 = L(\overline{BD})$ (known), $x_2 = L(\overline{DE})$ (unknown), and $L_2 = L(\overline{DF})$ (known). The known quantities can be measured in units of diamonds on the side of the table. Because of the similarity of the red triangles, we have: $$
\begin{align}
\dfrac{x_1}{L_1-x_1} &= \dfrac{L(\overline{AB})}{x_2} \tag{1} \\[3mm]
\dfrac{x_2}{L_2-x_2} &= \dfrac{L_1-x_1}{L(\overline{FG})} \tag{2}
\end{align}
$$ Solving $(1)$ and $(2)$ for $x_1$ gives the location of point $C$. One can do this by solving $(1)$ for $x_2$ and then plugging in the answer every time $x_2$ occurs in $(2)$. This is not very practical while playing, so once again, there is a midpoint/parallel shift method that you can implement easily.

1. Find the midpoint $M$ between $A$, the cue ball starting position, and $G$, the desired cue ball position at contact.

2. Make a line (with your cue stick) from $M$ to $D$, the corner pocket between the two rails off which you're kicking.

3. Move your cue, keeping it parallel, over to the cue ball, and where it intersects the bottom rail is the target contact point $C$.

So there you have it. The two-rail kick.

Now, there's an important point we completely ignored, and that's the effect of spin and, related to that, the fact that the rails are not rigid, but rather have some give and will compress when a ball contacts them and potentially alter the ball's trajectory coming off.

On the two-rail kick, in practice, we want to hit the ball along the lines we calculated above, but with a bit of running English, which means topspin + a bit of spin in the direction the ball will be moving (right English in the example above). I can't find anywhere on the internet why this is the case, but I suspect that it's because when the rail compresses and then launches the cue ball back out, the "launch" makes the angle off the rail greater. Running English compensates for that angle boost and also gives the ball some speed to "run" around the table.

The amount of spin depends on how close the contact point is to the corner pocket (point $D$ in the diagram) and also the speed with which the cue ball is hit.

For the simpler one-rail shots above, especially when the distances involved are relatively small and the cue ball isn't hit too hard (and thus the rail does not compress much), there is a bit of margin for error, and no fancy spin is necessary, but it is important for the two-rail kick where the ball must travel a long distance and with enough speed to go that distance.

I defer to better players to add to the spin point in the comments section or let me know if anything above is off.

Thanks for reading.

Prerequisites: Vectors

In this two-part post, we'll go through some of the basic geometry of pool/billiards.

In Part 2, we'll derive simple methods to make one-rail bank and kick shots (to be defined below). We'll also go briefly into an example of a two-rail kick, with which it's extremely difficult to actually pocket the target ball, but at least you can work your way out of some sticky situations and avoid giving your opponent ball-in-hand.

This analysis also works for mini-golf on flat surfaces, by the way.

How to pocket a ball

This section involves a bit of physics, which I'll explain for those who don't know it already, but you may need to quickly read up on vectors here before proceeding.

Suppose we have the following set-up:
The white ball is the cue ball, and we want to hit it into the 2 ball (the blue one, also known as the object ball) to pocket the latter in the side pocket on the top of the image.

In order to accomplish this, we need the cue ball, upon contact with the 2, to impart a force upon the latter which makes it move in the direction of the pocket. The way to make the force be in that direction is to hit such that the point of contact of the two balls lies along the line between the center of the pocket (where we want the object ball to go), and the center of the object ball as in the next diagram:
It's a subtle difference, but please note that you are aiming for the point of contact, and not the center of the cue ball, to lie along the yellow line upon contact with the 2. The translucent cue ball in the above diagram shows the desired cue ball position upon contact.

If you get this right, and hit the cue ball at center with a reasonable speed, then the force imparted on the 2 will be along the yellow line, and thus it will roll along the yellow line and into the pocket. This is Newton's second law at work, which states that if the mass (i.e. how many kilograms) of the 2 ball is $m$, and the force the cue ball imparts on the 2 is ${\bf F}$ (note that this is a vector quantity, which is why it has a direction, while the mass is a scalar), then ${\bf F} = m {\bf a}$, i.e. the 2 will gain an acceleration ${\bf a}$ due to the force ${\bf F}$. The units of the acceleration are meters per second squared, and thus the units of the force are killograms*meters per second squared, also called Newtons after the same Isaac Newton we were just talking about.

Acceleration is the change, both of magnitude and direction, in velocity per unit time (thus change over one second, in how many meters per second the ball is traveling at that moment). Velocity is just the vector quantity whose magnitude is the speed (in units of meters per second) and whose direction is the direction of motion of the ball. These quantities can all vary over time, as can the force. The ball's mass $m$ is a scalar quantity that is constant over time and is a measure of how much matter is contained in the ball. The heavier the ball, the more force it takes to accelerate the ball by an equivalent amount. That's what the magnitude part of the vector equation ${\bf F} = m {\bf a}$ tells us. The direction part tells us that the acceleration is in the same direction as the force.

Make sense? Ok good- if there are questions on that, they can go in the comments section or maybe I can do a separate post, but my point was that since the cue ball is round and thus contacts the (also round) 2 at exactly one point, the cue ball must impart a force on the 2 i the direction of the yellow line in the diagram above, and thus the 2 will accelerate along that line after the contact. Since no forces act on the ball that would cause it to deviate off of that line after the contact, it will continue along that line and thus into the side pocket.

Where does the cue ball go after the contact?

That's an important question, and good players need to take this into account when planning a series of shots.

As it turns out, the cue ball bounces off perpendicular to the yellow line as in the next diagram:

To see why this is the case, we need to use conservation of momentum. What does this mean? Well, momentum is the vector quantity $m{\bf v}$ where $m$ and ${\bf v}$ are mass and velocity as above. To say that momentum is conserved means that the momentum vector of a system of objects (for a system of multiple objects, this would be the vector sum of the individual momenta) remains constant in the absence of a net external force. In our system of two balls, the force between the balls would not qualify as external. Gravity would, but it is counteracted by the force of the table pushing back up on the balls, which causes them to not fall to the ground. Thus, ignoring friction, energy loss due to the sound of the balls' hitting, etc., the momentum of the system of the two balls is the same right before and right after the collision.

In the diagram above, we have labeled the velocities, and let's assume the cue and 2 have the same mass $m$. Momentum is conserved before and after the collision, which means: $$m{\bf v}_0 = m{\bf v}_1 + m{\bf v}_2
$$
Note that the 2 ball had no velocity initially, so the left-hand side of the equation has only the cue ball's momentum. The $m$'s cancel out to give the vector equation $${\bf v}_0 = {\bf v}_1 + {\bf v}_2 $$ which actually comprises 2 algebraic equations, one in the $x$-component and one in the $y$-component:
$$
\begin{align}
v_{0x} &= v_{1x} + v_{2x} \tag{1}\\[2mm]
v_{0y} &= v_{1y} + v_{2y} \tag{2}
\end{align}
 $$Now, we can use $(1)$ and $(2)$ to obtain: $$
\begin{align}
\| {\bf v}_0 \|^2 &= v_{0x}^2 + v_{0y}^2 \\[2mm]
&= (v_{1x} + v_{2x})^2 + (v_{1y} + v_{2y})^2 \\[2mm]
&= \| {\bf v}_1 \|^2 + \| {\bf v}_2 \|^2 + 2v_{1x}v_{2x} + 2v_{1y}v_{2y} \\[2mm]
&= \| {\bf v}_1 \|^2 + \| {\bf v}_2 \|^2 + 2({\bf v}_1 \cdot {\bf v}_2) \tag{3}
\end{align}
$$ We also know that the energy of the system is conserved. The energy of an object of mass $m$ and speed $v$ is $\frac{1}{2}mv^2$. Technically, this is only the kinetic energy (energy due to motion of a massive particle), but there is no potential energy in this system (e.g. an object high up about to fall and gain speed, and thus kinetic energy, would have potential energy).

Conservation of energy tells us that $$
\begin{align}
&\frac{1}{2} m \| {\bf v}_0 \|^2 = \frac{1}{2} m \| {\bf v}_1 \|^2 + \frac{1}{2} m \| {\bf v}_2 \|^2 \\[2mm]
\Longrightarrow \ &\| {\bf v}_0 \|^2 = \| {\bf v}_1 \|^2 + \| {\bf v}_2 \|^2 \tag{4}
\end{align}
$$ Subtracting equation $(4)$ from equation $(3)$ shows that ${\bf v}_1 \cdot {\bf v}_2 = 0$, i.e. ${\bf v}_1$ and ${\bf v}_2$ are perpendicular. This means that the cue ball indeed bounces off at a right angle to the direction of the 2 after contact.

In part 2 of this post, we'll explore bank and kick shots...