Thursday, 16 April 2015

Maths on Steroids (Accelerated Mathematics 1, 2015): 2

The week before Easter, a friend of mine showed me the following question before my Tuesday morning tute, I solved it and decided that it'd be a good question to give to you guys. =P

Actually, we could do this question using Descartes' circle theorem, but that's probably a bit overkill. Instead, let's tackle it with basic primary school geometry, and a bit of induction and telescoping! Consider the following figure:

Problem: order the radii of all the little yellow circles up from the bottom of the center as a sequence \(\{r_n\}\) and show that \begin{align}r_n=\frac{1}{2n(n+1)}.\end{align} When doing proofs for general results like this, it can often really really help to work out a few baby cases. So, let's start by showing that \(r_1=\frac{1}{4}\).

As you can see from the diagram below, we've got a (vertical) trapezium with two right angles opposite each other and with the parallel sides of lengths \(1\) and \(r_1\). Thus, by chopping off a rectangle at the bottom of this trapezium, we're left with a right-angled triangle with sides of lengths \(1-r_1,1\) and \(1+r_1\).
And so, Pythagoras' theorem tells us that \begin{align} (1-r_1)^2+1^2&=(1+r_1)^2 \\ \Rightarrow 1&=4r_1.\end{align} Oookay, that was fair straight forward. Let's try this again for \(r_2\):
So, we see that by repeat this trapezium trick to calculate \(r_2\) we get: \begin{align} (1-2r_1-r_2)^2+1^2&=(1+r_2)^2\\ \Rightarrow 1&=(1+r_2)^2-(1-2r_1-r_2)^2\\ &=4(r_1+r_2)(1-r_1).\end{align} Substituting in \(r_1=\frac{1}{4}\), we show that \(r_2=\frac{1}{12}\). Now, if we keep going with this trapezium trick (*), we see that to compute \(r_{n+1}\), we get: \begin{align} (1-2(r_1+\ldots+r_n)-r_{n+1})^2+1^2&=(1+r_{n+1})^2\\ \Rightarrow 1&=(1+r_{n+1})^2-(1-2(r_1+\ldots+r_n)-r_{n+1})^2\\ &=4(r_1+\ldots+r_{n+1})(1-r_1-\ldots-r_{n}).\end{align} Thus, \begin{align} r_{n+1}=\frac{1}{4-4(r_1+\ldots+r_n)}-(r_1+\ldots+r_n).\end{align} So, we've now got this recursive expression for \(r_{n+1}\) and recursion should really make us think: induction.

We're going to use a slightly stronger form (**) of mathematical induction than what you're used to seeing. Don't worry - the logic is the same. =) Okay, here goes...

Let's start off with a proposition: let the proposition \(p(n)\) be the statement that \(r_n=\frac{1}{2n(n+1)}\), and we're going to prove these statements for every \(n\in\mathbb{N}\).

Base case: \(n=1\)... well, we've actually already proven this above. We showed that \(r_1=\frac{1}{4}=\frac{1}{2\times1\times 2}\).

(Strong) induction step: now, we're going to do something a little different to showing that "\(p(k)\Rightarrow p(k+1)\)". We're actually going to show that \begin{align}p(1),p(2),\ldots, p(k)\text{ all being true }\Rightarrow p(k+1)\text{ is true.}\end{align} Take a moment to think about that logic, and I hope that you see that it's the same type of logic as you usually use in induction, except that it feels stronger because you're assuming more things for the induction step.

Okay....breathe out.

So, let's assume that \(p(1),\ldots,p(k)\) are all true. Now, we showed before that \begin{align} r_{k+1}=\frac{1}{4-4(r_1+\ldots+r_k)}-(r_1+\ldots+r_k).\end{align} And now, invoking all of our assumptions, we can try to work out what \(r_1+\ldots+r_k\) is equal to, and hence what \(r_{k+1}\) is equal to: \begin{align} r_1+\ldots+r_k&=\frac{1}{2}\left(\frac{1}{1\times 2}+\frac{1}{2\times 3}+\ldots+\frac{1}{k\times (k+1)}\right)\\ &=\frac{1}{2}\left(\frac{1}{1}-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\frac{1}{3}-\frac{1}{4}+\ldots-\frac{1}{k}+\frac{1}{k}-\frac{1}{k+1}\right)\\ &=\frac{k}{2(k+1)}.\end{align} W000t! Telescoping! And substituting this in, we get that: \begin{align}r_{k+1}&=\frac{1}{4-\frac{2k}{k+1}}-\frac{k}{2(k+1)}\\ &=\frac{k+1}{2(k+2)}-\frac{k}{2(k+1)}\\&=\frac{(k+1)^2-k(k+2)}{2(k+1)(k+2)}=\frac{1}{2(k+1)(k+2)},\end{align} which is precisely what we want. I.E.: the proposition \(p(k+1)\) is true!

Therefore, by the principle of (strong) mathematical induction, the propositions \(p(n)\) are true for all \(n\in\mathbb{N}\).


*: Bah, I didn't feel like drawing the diagram.
**: strictly speaking, it's not stronger - it's the same strength! It's just that it seems stronger.

No comments:

Post a Comment