Prove this identity

A note to future me:

Today you were trying to do probability questions with your pathetically sad probability skills and you found that
\[\sum_{i=0}^{n-1}\frac{m}{t-i}\frac{\binom{t-m}{i}}{\binom{t}{i}}=1-\frac{\binom{t-m}{n}}{\binom{t}{n}}.\]
Dare you to prove it.

From,
Your arrogant younger self.

Here's a hint:
\[\frac{\binom{t-m}{i}}{\binom{t}{i}}=\frac{\binom{t-i}{m}}{\binom{t}{m}}.\]
Why? Can you think of a combinatorial interpretation for this? Proving it through algebra is trivial. Thinking of an interpretation may lead to some actual learning.

Bonus:
From the identity above, you also managed to find that it implies: \[\sum _{i=0}^n \binom{t-i}{m}=\binom{t+1}{m+1}-\binom{t-n}{m+1}.\] Prove this identity.

A curious identity

I was trying to do a question the other day when I found an interesting identity that is a corollary of the double angle formulae. I've searched online for its name, but it might be so trivial that it doesn't have one. Instead of revealing the identity, I'll let you figure it out for yourself:
\[\frac{1}{2^0}\cos(x_1) = \cos(x_1)\]
\[\frac{1}{2^1}\left(\cos(x_1+x_2)+\cos(x_1-x_2)\right)=\cos(x_1)\cos(x_2)\]
\[\frac{1}{2^{2}}\left(\begin{array}{c}
\phantom{+}\cos(x_{1}+x_{2}+x_{3})\\
+\cos(x_{1}+x_{2}-x_{3})\\
+\cos(x_{1}-x_{2}+x_{3})\\
+\cos(x_{1}-x_{2}-x_{3})\end{array}\right)=\cos(x_{1})\cos(x_{2})\cos(x_{3})\]
Do you see the pattern?
Can you prove the pattern (Hint: Try induction)?
Are there other similar identities involving sines and combinations of sines and cosines?

For those who are curious, the question that led me to this identity was:
Determine the value of \[\cos\left(\frac{\pi}{7}\right)\cos\left(\frac{2\pi}{7}\right)\cos\left(\frac{4\pi}{7}\right).\]

There is a simple way to do this question, and a hard way. Sadly the identity I found led to the hard way.

Need Practice for the GRE?

Have I got the site for you (see title).

Upon the grave realization that I'll have to take the Physics and Math GRE in a couple years (oh yes, I prepare YEARS in advance), I've started a site that updates daily with Math and Physics GRE questions. Come visit (link below), it'll be fun.

Let us go then, you and I.

Thin Cars and Parking Lots

A quick question I came across today:

Suppose you had an infinitely thin car. How big do you have to build a parking lot for the car to be able to turn 180 degrees in the parking lot? 

Think about it for a while, and then highlight the area below to see the answer.

Surprisingly, there is no lower limit on the size of the parking lot. In other words, the parking lot can be as small as you want.                                                                                                

This is better known as the (thinly disguised) Kakeya Needle Problem. Unfortunately, the proof relies on existence theorems which (as far as I know) do not provide an explicit way to show us how we can jiggle the car around until it rotates 180 degrees. So while it might cool to tell your friend you can turn an infinitely thin car on a parking lot with zero area, I know of no way that you can physically show how it can be done.

Number of Primes with Desired Digit Strings

This post was previously very, very wrong. It has been corrected as of July 12th, 2011.


Greetings and salutations to my loyal readers (there are about 30 of you I think)!

I've been a bit busy recently organizing an online study group for The Feynman Lectures on Physics, so today I'll just post a short note based on an observation someone made about my last post on the Kempner series.

The observations was that since the prime harmonic series (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...) diverges, we can take out all the terms with a specific sequence of digits to make the series convergent as we did with the harmonic series. Or in other words:

"given any finite string of numbers, i.e. 24485983 that there exist infinitely many primes whose base 10 representation contain that string."

We knew from the my last post that the harmonic series became convergent if we took out all the terms with a '9' (or more generally any string of digits). For example, we could take out all primes with the digit string '13'. This would make the harmonic series convergent (after removing all the terms with '13'). Now consider the prime harmonic series, which is a subset of the original full harmonic series. Since the prime harmonic series diverges to infinity, we must have taken out an infinite number of primes with '13'. Therefore, the conclusion is that there are an infinite number of primes with any string of digits you can imagine.

The purpose of this note was to show that the same conclusion could be reached via a direct proof rather than as a corollary of another proof. However, I realized that my direct proof had a rather large flaw in it. As a cop-out, I'll show in this note that one can prove this result as a corollary of another theorem, namely Dirichlet's theorem for prime progressions.

Proof

Dirichlet's theorem states that there are infinitely many primes in the arithmetic sequence \[a, a+d, a+2d, a+3d, \ldots\] where $a$ and $d$ are coprime.

To prove that there are infinitely many primes which contain '13', set $a=13$ and $d=100$. We get the sequence 13, 113, 213, ... in which all terms contain the digit string '13' and by Dirichlet's theorem must contain an infinite number of primes.

$\blacksquare$

Although we used Dirichlet's theorem for showing this particular result, there are other theorems we could have used as well. For example, we could have used the fact that the prime counting function $\pi(x)$ is bound by \[\frac{1}{2}\frac{x}{\log(x)}<\pi(x)<2\frac{x}{\log(x)}.\]
Just so I don't feel like a complete hack, here are some exercises for you guys.

Exercises

1. Prove that there are infinitely many primes containing 42 (if you use Dirichlet's Theorem, use it carefully).
2. Prove that there are infinitely many primes starting with the digits 42.

The Kempner Series - A modified harmonic series

The harmonic series is considered a classic textbook example of a series that seems to converge but is actually divergent. For those that need a reminder, the harmonic series is: \[\sum_{n=1}^{\infty}\frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\cdots.\]
Now here's an interesting question:

How can we modify the harmonic series to make it convergent?

Disregarding trivial answers such as "remove all the terms", this question is actually pretty hard to answer. Say we removed every second term starting from the first (i.e. 1, 1/3, 1/5, etc). Would that work?
\[\sum_{\substack{n=1 \\ n\ is\ even}}^{\infty}\frac{1}{n}=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{8}\cdots=\frac{1}{2}\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\cdots\right).\]
From above, it seems like it would not work since it just produces half of the original series (which is not a very well defined quantity since the original series was divergent anyway).

$\frac{d}{dx}(f(x)g(x)) \neq f^\prime(x)g^\prime(x)$? Think again!

One of the most unintuitive and frustrating facts about calculus is that \[\frac{d}{dx}(f(x)g(x))\neq f^\prime(x)g^\prime(x).\]
It is said in certain apocryphal tales that the great man himself once made the above mistake. Instead of the pretty but untrue equation above, we have the unsightly but true "product rule":
\[\frac{d}{dx}f(x)g(x)= f(x)g^\prime(x)+f^\prime(x)g(x).\]

Making your own pendulum wave machine

This post is a continuation of a three part post started here.

Pendulum Waves - Mathematical Description cont. 2

If you missed the first two parts to this post, you can start here to get some context.

Pendulum Waves - Mathematical Description cont.

This is the second of a three part post on mathematically explaining the pendulum waves apparatus (below). The first part is located here.

We'll start off from where we ended last time.
We had two possible equations that we could use to continue our derivation with:

\[y(x,t)=A\cos\left(k_{0}x+\omega(x)t\right)\]\[y(x,t)=A\cos\left(k(t)x+\omega_{0}t\right).\]

Let's use the first of the two equations above.

Since we start the pendulum waves by setting all the pendula to maximum amplitude, we have \[y\left(x,0\right)=A=A\cos\left(k_{0}x+\omega\left(0\right)\cdot0\right)\]\[A=A\cos\left(k_{0}x\right)\implies k_{0}=0.\]

Let's figure out what $\omega(x)$ is. We'll forget about $\omega$ as a function of $x$ for a moment and look at $\omega$ as a function of the n-th pendulum instead.

Recall that the total time of the dance is $\Gamma$ during which the longest pendulum performs $N$ oscillations. So the period of the longest pendulum is $T=\frac{\Gamma}{N}$. OK, so we have the period of one pendulum now. How do we figure out the gabajillion other pendulums on the thing? Well, we also know that as the pendulums get shorter, their number of oscilations increases. More specifically, if the longest pendulum has 51 oscillations, then its shorter neighbour will have 52 oscillations, its shorter neighbour will have 53 oscillations, and so forth. So letting $n$ represent the n-th pendulum (counting from 0), the period of any pendulum on the apparatus is $T=\frac{\Gamma}{N+n}$.

To express $\omega$ as a function of $x$, note that the x-position of the pendulum is $x=nd$ (so $n=\frac{x}{d}$ where $d$ is the common spacing between adjacent pendulums. We're almost done now. Now we can see that: \[\omega(x)=\frac{2\pi}{T}=\frac{2\pi}{\frac{\Gamma}{N+\frac{x}{d}}}\] \[\omega(x)=\frac{2\pi \left(N+\frac{x}{d}\right)}{\Gamma}=\frac{2\pi \left(Nd+x\right)}{\Gamma d}\]

Therefore, our complete wave equation is: \[y(x,t)=A\cos\left(\frac{2\pi \left(Nd+x\right)}{\Gamma d}t\right)\]

As a note of interest, we can rewrite the equation above as

\[y(x,t)=A\cos\left(\frac{2\pi t}{\Gamma d}x + \frac{2\pi N}{\Gamma}t\right)\] which corresponds to \[y(x,t)=A\cos\left(k(t)x+\omega_{0}t\right).\]

And we are done! That's the equation describing all of the waves you see in the video above.

Now that we are finished, we can take a nice break and prepare ourselves for the next post, where I'll discuss the properties of the equation we've just found. 

Pendulum Waves - Mathematical Description

Everyone likes bling, so let's start this post off with some eye-candy (skip to 20s if you've got very little patience):

That was pretty damn cool. Even if you're not admitting it, I know you're thinking it.

Lately, that video has been posted and reposted all over the internet. Now, don't get me wrong, I love spreading the joy of physics to no end. For those unsatisfied with simply seeing the video however, this post will be dedicated to presenting the nitty-gritty mathematical details of this marvelous phenomenon. If you would like to skip the math and just get some specifications to making your own pendulum wave machine, proceed here.

This is how the apparatus works in a nutshell:

The period of one complete cycle of the dance is 60 seconds. The length of the longest pendulum has been adjusted so that it executes 51 oscillations in this 60 second period. The length of each successive shorter pendulum is carefully adjusted so that it executes one additional oscillation in this period. Thus, the 15th pendulum (shortest) undergoes 65 (51 oscillations + 14 pendulums from the first) oscillations. When all 15 pendulums are started together, they quickly fall out of sync—their relative phases continuously change because of their different periods of oscillation. However, after 60 seconds they will all have executed an integral number of oscillations and be back in sync again at that instant, ready to repeat the dance. [1]

Let's begin. In a typical undergraduate physics course, you have most likely come across the (somewhat useless) travelling wave equation:

\[y(x,t)=A\cos\left(kx+\omega t+\phi\right)\]
where $A$ is the amplitude, $k=\frac{2\pi}{\lambda}$ is the wave number, $\omega=\frac{2\pi}{T}$ is the angular frequency, and $\phi$ is the phase shift. By convention, $\lambda$ and $T$ are used to denote the wavelength and period of the wave respectively. Lets also call the number of oscillations the longest pendulum goes thru $N$ (51 in this case) and the total time for the entire "dance" $\Gamma$ (60s in this case).

From the video, we can see that at $t=0$ and for any $x$ (we pick $x=0$), we have the maximum amplitude, $A$:

\[y\left(0,0\right)=A\cos\left(k\cdot0+\omega\cdot0+\phi\right)\]\[A=A\cos\left(\phi\right)\implies\phi=0.\]
Another thing we can see is that because the waves change shape in time, the wavelength must be a function of time and so the wave number (since it depends on $\lambda$) must also be a function of time. So instead of a fixed $k$, we have $k(t)$. Another thing to note is that since each individual pendulum is adjusted to give one more oscillation than their longer neighbour, the period and therefore the angular frequency must be a function of location, so we have $\omega(x)$.

Putting it all together, we have the equation:

\[y(x,t)=A\cos\left(k(t)x+\omega(x)t\right).\]
Now lets think for a moment. If $k(t)$ and $\omega(x)$ were independent of each other, the combination of some random $k$ and $\omega$ probably would not create the pretty patterns we see in the video. Aha! We have to conclude that $k(t)$ and $\omega(x)$ are some how working together - that these two functions are not independent of each other. More specifically, the cause to $k$ changing with time is due to constructing the machine so that the oscillations of each adjacent pendulum differs by 1 (i.e. due to tuning $w$ with x). With a bit of handwaving, we can choose to express one function in terms of the other and essentially throw away one of them. Our wave equation can now be modified to either one of:

\[y(x,t)=A\cos\left(k_{0}x+\omega(x)t\right)\]\[y(x,t)=A\cos\left(k(t)x+\omega_{0}t\right).\]
The constants $k_{0}$ and $\omega_{0}$ are used to describe the wave at $t=0$ and $x=0$ respectively.

Now the two expressions above are really the same, since they're both very general functions of $x$ and $t$. This means we can pick our choice of which equation to use.

Since I don't like overly long, dry, and boring posts, I'll end this post right here and continue the derivation in my next post. If you feel like doing the derivation yourself, go for it! It's a great way to learn.

Proof - Equal temperatures for opposing points on a circle

If you would like a bit of intuition before we delve into the proof, see my last post.

Ready to go? Great.

Let the function $T(x)$ represent the temperature at some position $x$. Around a circle, $T(x)$ is periodic about $2\pi$ radians when $x$ lies on the circle's circumference. Thus, $T(x)=T(x+2\pi)$. Let us define a new function $D(x)=T(x)-T(x+\pi)$. Note that $D(x)$ is continuous as it is a difference of continuous functions $T(x)$ and $T(x+\pi)$.

Let:

$D(0)=L$ and $D(\pi)=-D(0)=-L$.

• If $L=-L=0,$ $T(x)-T(x+\pi)=0$ and we are done.

• If $L\neq0,$ then one of $L$ or $-L$ must be above zero and the other below zero.

Since $D(x)$ is a continuous function, we can apply the Intermediate Value Theorem to it. By the Intermediate Value Theorem, the function $D(x)=0$ for some $x\in[0,\pi]$.
Therefore, $T(x)-T(x+\pi)=0$, and $T(x)=T(x+\pi)$ for some $x\in[0,\pi]$. 

$\blacksquare$

Equal temperatures at two opposite points across the earth

This is a neat question I got in my first year calculus course:

Imagine a circle anywhere in the universe. (For example, draw a circle on a sheet of paper, or imagine the equator is a circle.) Prove that there are two points directly opposite each other on the circle with the same temperature.

Proof - Reducing prime checking bounds to $\sqrt{n}$

This is a simple proof accompanying my last post on generating primes.


Let $n$ be a non-prime (i.e. composite), then it must have factors $a$ and $b$ less than $n$.

In other words: $n=ab$, with $n>a>1$ and $n>b>1$.

Suppose $a>\sqrt{n}$ and $b>\sqrt{n}$. This would mean $ab>n$. This cannot be as we just stated that $n=ab$.

Thus, the conclusion we draw is that either $a$ or $b$ is less than or equal to $\sqrt{n}$.

Let us say that  it is $a\leq \sqrt{n}$.

Since $a>1$ , there must exist a prime $p$ that divides $a$. Furthermore, $p\leq a$ since it divides $a$.

We saw earlier that $a$ divides $n$. Since $p$  divides $a$, our prime $p$ must divide $n$. This gives us the result we are trying to prove: $p\leq a$ and $a\leq \sqrt{n}$. Therefore: $p\leq a\leq\sqrt{n}$.

Conclusion: If $n$ is not prime, it must have a prime factor (or regular factor) below $\sqrt{n}$. Otherwise, $n$ must be prime.


$\blacksquare$

Prime Number Generation

If I asked you right now: what is the 10001st prime number?  It would be very hard to come up with an answer on the spot. (this is question #7 on Project Euler). However, if one did want to find the answer, one method to use would be simple “trial division”.

A bit of an introduction

Hello.

My name is Paul Liu. It's nice to meet you. I was going to have a lovely conversation with you. However, since my current readership is zero, I'll edit more info into this page when people start giving a damn. For now, lets just get started. It's going to be a long long journey. I hope you'll find the time to share it with me.