Hey guys! Sooo, last week in Tute A y'all saw this cool fact that one way to check the divisibility of a (natural) number by \(3\) is to add up all of its digits and check to see if the resulting sum is divisible by \(3\).
E.g.: take \(832745812349\), now \(8+3+2+7+4+5+8+1+2+3+4+9=56\) and \(56\) isn't divisible by \(3\). Therefore \(832745812349\) isn't divisible by \(3\).
And in fact, this is also true for \(9\), you can add up the digits of a number and if this sum is divisible by \(9\), then the original number must also be divisible by \(9\) (and vice versa).
I then asked you to try to figure out a similar trick for \(11\), and you can find the rule (and a derivation/proof) here!
Well, I then issued like a super-ninja-hax-challenge version of this where I asked you to derive a similar rule for divisibility by \(101,1001,10001,100001,\ldots\) How did you go with this? I'll write the answer below, but I kinda want you to take a look at the above blog post first.
Here we go:
So, the trick for divisibility with respect to \(11\) of a \(k\)-digit whole number (with digit representation) \(\overline{n_0 n_1 n_2\ldots n_k}\) is to take the following "alternating sum" \begin{align} n_k-n_{k-1}+n_{k-2}-\ldots+(-1)^kn_0,\end{align} and if this sum is divisible by \(11\), then the original number is divisible by \(11\). Note in particular, the order in which we've go - we've taken the last digit, subtracted the second last...etc. And the reason that we've done this is because this presentation generalises more easily to \(101,1001,\ldots\)
So, what about \(101\)? Well, the rule is to take the last two digits, subtract the next pair, then add the next pair, and so forth. So, let's see an example:
the number \(74914071682\) satisfies that \begin{align} 82-16+7-14+49-7=101,\end{align} which is clearly divisible by \(101\). Thus, \(74914071682\) should be divisible by \(101\) and indeed: \(74914071682=101\times 741723482\).
And the generalisation to \(1001\) involves us taking the last three digits, then subtracting the next triple, and adding the next triple...etc. And I the pattern goes on...
What about the proof!? I hear you ask. Well, it's pretty similar to the proof for our rule regarding divisibility by \(11\). So, I'll let this to you guys as a healthy challenge exercise. =)
Showing posts with label MAST20026. Show all posts
Showing posts with label MAST20026. Show all posts
Monday, 23 March 2015
Monday, 24 November 2014
Analysis for Realsies: 8 (final)
Okay, as promised - my last words. =P
In my previous post, I promised you guys that I'd show you how to differentiate \(\sin(x)\) from first principles and that I'd also prove a cool geometric fact to do with the lunes of Alhazen.
So, you suddenly wake up in the dead of night with cold beads of sweat on your forehead aperch'd, and there is but one solitary thought plaguing your addled-mind: how the heck do you actually differentiate \(\sin(x)\)? Well, when in doubt...write it out in first principles: \begin{align}\frac{\mathrm{d}\sin(x)}{\mathrm{d}x}=&\lim_{h\to0}\frac{\sin(x+h)-\sin(x)}{h}\\=&\lim_{h\to0}\frac{\sin(x)\cos(h)+\cos(x)\sin(h)-\sin(x)}{h}\\=&\lim_{h\to0}\sin(x)\frac{\cos(h)-1}{h}+\cos(x)\frac{\sin(h)}{h}.\end{align} So, we see that we need to calculate these two limits: \begin{align}\lim_{h\to0}\frac{\sin(h)}{h}\text{ and }\lim_{h\to0}\frac{1-\cos(h)}{h}.\end{align} To calculate the former, consider the following picture:
The height of the smaller triangle is \(\sin(x)\). This is shorter than the circular arc, which is of length \(x=\frac{x}{2\pi}\times2\pi\). Moreover, the area of the circular sector is \(\frac{1}{2}x=\frac{x}{2\pi}\times\pi\times1^2\), which is less than the area of the big triangle: \(\frac{1}{2}\tan(x)\). Putting these two inequalities together, we have: \begin{align}\forall x\in(0,\frac{\pi}{2}), \sin(x)\leq x\leq\tan(x).\end{align} Dividing by \(\sin(x)\) and taking the reciprocal, we see that: \begin{align}\cos(x)\leq\frac{\sin(x)}{x}\leq 1.\end{align} Since \(\lim_{h\to0^+}\cos(h)=0\), the sandwich theorem tells us that: \begin{align}\lim_{h\to0^+}\frac{\sin(h)}{h}=1.\end{align}Since \(\frac{\sin(h)}{h}\) is an even function, the limit from the negative side of \(h=0\) must also approach \(1\). Knowing this first limit allows us to compute the second:\begin{align}\lim_{h\to0}\frac{1-\cos(h)}{h}=&\lim_{h\to0}\frac{1-\cos^2(h)}{h(1+\cos(h))}\\=&\lim_{h\to0}\frac{\sin^2(h)}{h(1+\cos(h))}=\frac{1}{2}\times0=0.\end{align} Shoving this into our first principles computation of the derivative of \(\sin(x)\) and we see that \(\frac{\mathrm{d}\sin(x)}{\mathrm{d}x}=\cos(x)\). W00000t! Having assured yourself that you're perfectly capable of differentiating \(\sin(x)\), you drift back to sleep...
Only to be awoken by an infernal desire to prove that the area of the two dark shaded burgundy "lunes" (the crescent shaped moon things) in the following diagram add up to the area of the white triangle in the middle:
Orrite, let's prove this. First note that the white triangle in the middle is a right-angled triangle (this is true of all triangles circumscribed by a circle whose hypotenuse is the diameter), and we denote its side-lengths by \(a\leq b\leq c\), where \(c\) is the diameter of the big circle. Pythagoras' theorem tells us that \begin{align} a^2+b^2=c^2,\end{align} hence, the area of the yellow semicircle (\(\frac{1}{8}\pi c^2\)) is equal to the total area of the two (duo-toned) smaller red semicircles (\(\frac{1}{8}\pi a^2+\frac{1}{8}\pi b^2\)). Now, the area of the yellow semicircle is the same as the area of white triangle and the two lighter red sections, and therefore:
Area of the white triangle+area of the light red bits=area of the dark red bits+area of the light red bits.
Cancelling the light red bits from both sides then yields the desired result. =)
Well, it's been a good semester guys, I hope that you have an awesome Christmas break!
In my previous post, I promised you guys that I'd show you how to differentiate \(\sin(x)\) from first principles and that I'd also prove a cool geometric fact to do with the lunes of Alhazen.
So, you suddenly wake up in the dead of night with cold beads of sweat on your forehead aperch'd, and there is but one solitary thought plaguing your addled-mind: how the heck do you actually differentiate \(\sin(x)\)? Well, when in doubt...write it out in first principles: \begin{align}\frac{\mathrm{d}\sin(x)}{\mathrm{d}x}=&\lim_{h\to0}\frac{\sin(x+h)-\sin(x)}{h}\\=&\lim_{h\to0}\frac{\sin(x)\cos(h)+\cos(x)\sin(h)-\sin(x)}{h}\\=&\lim_{h\to0}\sin(x)\frac{\cos(h)-1}{h}+\cos(x)\frac{\sin(h)}{h}.\end{align} So, we see that we need to calculate these two limits: \begin{align}\lim_{h\to0}\frac{\sin(h)}{h}\text{ and }\lim_{h\to0}\frac{1-\cos(h)}{h}.\end{align} To calculate the former, consider the following picture:
Only to be awoken by an infernal desire to prove that the area of the two dark shaded burgundy "lunes" (the crescent shaped moon things) in the following diagram add up to the area of the white triangle in the middle:
Orrite, let's prove this. First note that the white triangle in the middle is a right-angled triangle (this is true of all triangles circumscribed by a circle whose hypotenuse is the diameter), and we denote its side-lengths by \(a\leq b\leq c\), where \(c\) is the diameter of the big circle. Pythagoras' theorem tells us that \begin{align} a^2+b^2=c^2,\end{align} hence, the area of the yellow semicircle (\(\frac{1}{8}\pi c^2\)) is equal to the total area of the two (duo-toned) smaller red semicircles (\(\frac{1}{8}\pi a^2+\frac{1}{8}\pi b^2\)). Now, the area of the yellow semicircle is the same as the area of white triangle and the two lighter red sections, and therefore:
Area of the white triangle+area of the light red bits=area of the dark red bits+area of the light red bits.
Cancelling the light red bits from both sides then yields the desired result. =)
Well, it's been a good semester guys, I hope that you have an awesome Christmas break!
Sunday, 26 October 2014
Analysis for Realsies: 7
Hey guys! W0000, SWOTVAC! It's time to learn every subject that you've done this semester from scratch within a week! Awwww yisssssss!
A week or two ago, you'll have seen a question in your tute B prac sheets asking you if the following sequence converges: \begin{align}\sum_{k=1}^{\infty}\sin(k+k^{-1}).\end{align} And the answer is no, by the divergence test. That is: the sequence \((\sin(k))\) doesn't converge to \(0\), so the series can't actually converge. But, we didn't really show that this sequence doesn't converge to \(0\), so just said that this is true by obviousness. There are probably a fair few ways that you guys can prove this, but let's just use something that you're all totes guns with now: \(\epsilon-N\) proofs!
And let's do this by proof-by-contradiction: assume that \(\lim_{k\to\infty}\sin(k+k^{-1})=0\). This means that for \(\epsilon=\frac{1}{3}\sin(1)>0\), there exists some \(N\in\mathbb{N}\) such that for every \(n>N\), \begin{align}|\sin(n)-0|<\epsilon=\frac{1}{3}\sin(1).\end{align} Consider an arbitrary integer \(k>N\), then \begin{align} |\sin(k+k^{-1})|<\epsilon\text{ and }|\cos(k+k^{-1})|>\sqrt{1-\epsilon^2}=\sqrt{1-\frac{\sin^2(1)}{3}}>\frac{\sqrt{8}}{3}.\end{align} Now, since \(k+1\) is also larger than \(N\), we see that: \begin{align}\epsilon>&|\sin\left(k+1+\frac{1}{k+1}\right)-0|\\=&|\sin\left(k+\frac{1}{k}-\frac{1}{k(k+1)}\right)|\\ =&\left|\sin\left(1-\frac{1}{k(k+1)}\right)\cos(k+k^{-1})+\sin(k+k^{-1})\cos\left(1-\frac{1}{k(k+1)}\right)\right|\\ =&\left|\sin\left(1-\frac{1}{k(k+1)}\right)\cos(k+k^{-1})--\sin(k+k^{-1})\cos\left(1-\frac{1}{k(k+1)}\right)\right|\\ \geq&\left||\sin\left(1-\frac{1}{k(k+1)}\right)\cos(k+k^{-1})|-|\sin(k+k^{-1})\cos\left(1-\frac{1}{k(k+1)}\right)|\right|,\end{align} where this final line is due to (one of the forms of) the triangle inequality. This in turn means that: \begin{align}\epsilon=\frac{\sin(1)}{3}>&\sin\left(1-\frac{1}{k(k+1)}\right)|\cos(k+k^{-1})|-|\sin(k+k^{-1})|\\ >&\frac{\sqrt{8}}{3}\sin\left(1-\frac{1}{k(k+1)}\right)- \frac{\sin(1)}{3}, \end{align} for all \(k>N\). This is false when \(k\) is large enough (because \(\sqrt{8}-1>1\) and \(\lim_{k\to\infty}\sin(1+(k(k+1))^{-1})=\sin(1)\). Soooooooo, we see that the sequence \((\sin(k))\) can't possibly converge to \(0\), and we're done!
Now, if you were in my tute A classes last week, I would have given you the following two variants of the above problem:
Do the following series converge? \begin{align} \sum_{k=1}^{\infty} \sin\left(\pi k+\frac{1}{\pi k}\right)\text{ and }\sum_{k=1}^{\infty}\sin\left(2\pi k+\frac{1}{2\pi k}\right).\end{align}
Answer: yes (for the left series) and no (for the right).
To see that \(\sum \sin(\pi k+\frac{1}{\pi k})\) converges, observe that \begin{align} \sin\left(\pi k+\frac{1}{\pi k}\right)=(-1)^k\sin(\tfrac{1}{\pi k}).\end{align} The desired convergence follows from invoking the alternating series theorem. =)
To see that \(\sum \sin(2\pi k+\frac{1}{\pi k})\) diverges, observe that \begin{align} \sin\left(2\pi k+\frac{1}{2\pi k}\right)=\sin(\tfrac{1}{2\pi k}).\end{align} Intuitively, when \(k\) is epically huge, \(\frac{1}{2\pi k}\) will be tiny. And for \(x\) really close to \(0\), \(\sin(x)\approx x\). Thus, we expect that for large \(k\), \begin{align}\sin(\tfrac{1}{2\pi k})\approx \tfrac{1}{2\pi k}.\end{align} Hence, the whole series behaves roughly like \(\frac{1}{2\pi}\) times the harmonic series...which totally blows up to infinity!
But...how can we formally set this out? Let's do it using the mean value theorem!
So, basically, the MVT tells us that there exists some \(c_k\in(0,\frac{1}{2\pi k})\) such that \begin{align}\cos(c_k)=\frac{\sin(\tfrac{1}{2\pi k})-\sin(0)}{\tfrac{1}{2\pi k} - 0}\text{, and thus:}\\ \sin(\frac{1}{2\pi k})=\frac{1}{2\pi k}\cos(c_k)\geq\frac{1}{2\pi k}\cos(\tfrac{1}{2\pi}). \end{align} This in turn means that: \begin{align}\sum_{k=0}^{\infty}\sin\left(2\pi k+\frac{1}{\pi k}\right)\geq \cos(\tfrac{1}{2\pi})\sum_{k=0}^{\infty}\frac{1}{2\pi k}.\end{align} Since the right series blows up to infinity, our series \(\sum \sin(2\pi k+\frac{1}{\pi k})\) is divergent! (Note that we're really just applying of the comparison test for series)
Okay...so, this blog post has gotten way longer than I had in mind...and I had hoped to show you guys how to differentiate \(\sin(x)\) from first principles and also a nice little geometric fact that Pat showed me in class...maybe...I'll do another blog post at some point...
A week or two ago, you'll have seen a question in your tute B prac sheets asking you if the following sequence converges: \begin{align}\sum_{k=1}^{\infty}\sin(k+k^{-1}).\end{align} And the answer is no, by the divergence test. That is: the sequence \((\sin(k))\) doesn't converge to \(0\), so the series can't actually converge. But, we didn't really show that this sequence doesn't converge to \(0\), so just said that this is true by obviousness. There are probably a fair few ways that you guys can prove this, but let's just use something that you're all totes guns with now: \(\epsilon-N\) proofs!
And let's do this by proof-by-contradiction: assume that \(\lim_{k\to\infty}\sin(k+k^{-1})=0\). This means that for \(\epsilon=\frac{1}{3}\sin(1)>0\), there exists some \(N\in\mathbb{N}\) such that for every \(n>N\), \begin{align}|\sin(n)-0|<\epsilon=\frac{1}{3}\sin(1).\end{align} Consider an arbitrary integer \(k>N\), then \begin{align} |\sin(k+k^{-1})|<\epsilon\text{ and }|\cos(k+k^{-1})|>\sqrt{1-\epsilon^2}=\sqrt{1-\frac{\sin^2(1)}{3}}>\frac{\sqrt{8}}{3}.\end{align} Now, since \(k+1\) is also larger than \(N\), we see that: \begin{align}\epsilon>&|\sin\left(k+1+\frac{1}{k+1}\right)-0|\\=&|\sin\left(k+\frac{1}{k}-\frac{1}{k(k+1)}\right)|\\ =&\left|\sin\left(1-\frac{1}{k(k+1)}\right)\cos(k+k^{-1})+\sin(k+k^{-1})\cos\left(1-\frac{1}{k(k+1)}\right)\right|\\ =&\left|\sin\left(1-\frac{1}{k(k+1)}\right)\cos(k+k^{-1})--\sin(k+k^{-1})\cos\left(1-\frac{1}{k(k+1)}\right)\right|\\ \geq&\left||\sin\left(1-\frac{1}{k(k+1)}\right)\cos(k+k^{-1})|-|\sin(k+k^{-1})\cos\left(1-\frac{1}{k(k+1)}\right)|\right|,\end{align} where this final line is due to (one of the forms of) the triangle inequality. This in turn means that: \begin{align}\epsilon=\frac{\sin(1)}{3}>&\sin\left(1-\frac{1}{k(k+1)}\right)|\cos(k+k^{-1})|-|\sin(k+k^{-1})|\\ >&\frac{\sqrt{8}}{3}\sin\left(1-\frac{1}{k(k+1)}\right)- \frac{\sin(1)}{3}, \end{align} for all \(k>N\). This is false when \(k\) is large enough (because \(\sqrt{8}-1>1\) and \(\lim_{k\to\infty}\sin(1+(k(k+1))^{-1})=\sin(1)\). Soooooooo, we see that the sequence \((\sin(k))\) can't possibly converge to \(0\), and we're done!
Now, if you were in my tute A classes last week, I would have given you the following two variants of the above problem:
Do the following series converge? \begin{align} \sum_{k=1}^{\infty} \sin\left(\pi k+\frac{1}{\pi k}\right)\text{ and }\sum_{k=1}^{\infty}\sin\left(2\pi k+\frac{1}{2\pi k}\right).\end{align}
Answer: yes (for the left series) and no (for the right).
To see that \(\sum \sin(\pi k+\frac{1}{\pi k})\) converges, observe that \begin{align} \sin\left(\pi k+\frac{1}{\pi k}\right)=(-1)^k\sin(\tfrac{1}{\pi k}).\end{align} The desired convergence follows from invoking the alternating series theorem. =)
To see that \(\sum \sin(2\pi k+\frac{1}{\pi k})\) diverges, observe that \begin{align} \sin\left(2\pi k+\frac{1}{2\pi k}\right)=\sin(\tfrac{1}{2\pi k}).\end{align} Intuitively, when \(k\) is epically huge, \(\frac{1}{2\pi k}\) will be tiny. And for \(x\) really close to \(0\), \(\sin(x)\approx x\). Thus, we expect that for large \(k\), \begin{align}\sin(\tfrac{1}{2\pi k})\approx \tfrac{1}{2\pi k}.\end{align} Hence, the whole series behaves roughly like \(\frac{1}{2\pi}\) times the harmonic series...which totally blows up to infinity!
But...how can we formally set this out? Let's do it using the mean value theorem!
So, basically, the MVT tells us that there exists some \(c_k\in(0,\frac{1}{2\pi k})\) such that \begin{align}\cos(c_k)=\frac{\sin(\tfrac{1}{2\pi k})-\sin(0)}{\tfrac{1}{2\pi k} - 0}\text{, and thus:}\\ \sin(\frac{1}{2\pi k})=\frac{1}{2\pi k}\cos(c_k)\geq\frac{1}{2\pi k}\cos(\tfrac{1}{2\pi}). \end{align} This in turn means that: \begin{align}\sum_{k=0}^{\infty}\sin\left(2\pi k+\frac{1}{\pi k}\right)\geq \cos(\tfrac{1}{2\pi})\sum_{k=0}^{\infty}\frac{1}{2\pi k}.\end{align} Since the right series blows up to infinity, our series \(\sum \sin(2\pi k+\frac{1}{\pi k})\) is divergent! (Note that we're really just applying of the comparison test for series)
Okay...so, this blog post has gotten way longer than I had in mind...and I had hoped to show you guys how to differentiate \(\sin(x)\) from first principles and also a nice little geometric fact that Pat showed me in class...maybe...I'll do another blog post at some point...
Monday, 13 October 2014
Analysis for Realsies: 6
One of the challenge fun exercises that I gave you last week's tute B was to exactly compute the integral of \(\frac{1}{1+x^4}\) rather than to rely on comparison techniques to show that this is integrable. How did you guys go with it? I know that I certainly didn't see the first step of this when I tried to do this integral in first year. =P
My hint was the \(1+x^4\) was factorisable into two real polynomials, and one way to see this is to factorise it into four linear terms involving complex numbers and to pair up linear terms until you got pairings which produced real quadratic polynomials. The other way is to complete the square: \begin{align}1+x^4=&1+2x^4+x^4-2x^2\\=&(1+x^2)^2-(\sqrt{2}x)^2\\=&(1-\sqrt{2}x+x^2)(1+\sqrt{2}x+x^2).\end{align} Now, if you're comfortable with partial fractions, you should immediately notice that: \begin{align}\frac{1}{1-\sqrt{2}x+x^2}-\frac{1}{1+\sqrt{2}x+x^2}&=\frac{2\sqrt{2}x}{1+x^4}\text{, and}\\ \frac{1}{1-\sqrt{2}x+x^2}+\frac{1}{1+\sqrt{2}x+x^2}&=\frac{2+2x^2}{1+x^4}.\end{align} Since \(1=\frac{1}{2}(2+2x^2)-\frac{x}{2\sqrt{2}}2\sqrt{2}x\), we see that: \begin{align}\frac{1}{1+x^4}=&\frac{1}{2}\left(\frac{1}{1-\sqrt{2}x+x^2}+\frac{1}{1+\sqrt{2}x+x^2}\right)\\&-\frac{x}{2\sqrt{2}}\left(\frac{1}{1-\sqrt{2}x+x^2}-\frac{1}{1+\sqrt{2}x+x^2}\right)\\=&\frac{\frac{1}{2}-\frac{x}{2\sqrt{2}}}{1-\sqrt{2}x+x^2}+\frac{\frac{1}{2}+\frac{x}{2\sqrt{2}}}{1+\sqrt{2}x+x^2}\\=& \frac{1+\sqrt{2}x}{4(1+\sqrt{2}x+x^2)}+\frac{1-\sqrt{2}x}{4(1+\sqrt{2}x+x^2)}\\&+\frac{1}{4(1+\sqrt{2}x+x^2)}+\frac{1}{4(1-\sqrt{2}x+x^2)}.\end{align} Finally, integrating the two upper-line terms into a logarithm and integrating the two lower-line terms into an inverse tan function, we get: \begin{align} \int \frac{\mathrm{d}x}{1+x^4}=&\frac{1}{4\sqrt{2}}\log|1+\sqrt{2}x+x^2|-\frac{1}{4\sqrt{2}}\log|1-\sqrt{2}x+x^2|\\&+\frac{1}{2\sqrt{2}}\mathrm{arctan}(\sqrt{2}x+1)+\frac{1}{2\sqrt{2}}\mathrm{arctan}(\sqrt{2}x-1).\end{align}Aaaaaaand here's another fun exercise: differentiate \(\sin(x)\) from first principles! And here's a hint (it's written in white, so highlight it):
You'll probably need to show at some point that \(\lim_{x\to 0}\frac{\sin(x)}{x}=1\)...and this can totes be done by proving the following inequality \(\sin(x)<x<\tan(x)\) for \(x\in(0,\frac{\pi}{2})\). And...this can be done...geometrically.
=P
My hint was the \(1+x^4\) was factorisable into two real polynomials, and one way to see this is to factorise it into four linear terms involving complex numbers and to pair up linear terms until you got pairings which produced real quadratic polynomials. The other way is to complete the square: \begin{align}1+x^4=&1+2x^4+x^4-2x^2\\=&(1+x^2)^2-(\sqrt{2}x)^2\\=&(1-\sqrt{2}x+x^2)(1+\sqrt{2}x+x^2).\end{align} Now, if you're comfortable with partial fractions, you should immediately notice that: \begin{align}\frac{1}{1-\sqrt{2}x+x^2}-\frac{1}{1+\sqrt{2}x+x^2}&=\frac{2\sqrt{2}x}{1+x^4}\text{, and}\\ \frac{1}{1-\sqrt{2}x+x^2}+\frac{1}{1+\sqrt{2}x+x^2}&=\frac{2+2x^2}{1+x^4}.\end{align} Since \(1=\frac{1}{2}(2+2x^2)-\frac{x}{2\sqrt{2}}2\sqrt{2}x\), we see that: \begin{align}\frac{1}{1+x^4}=&\frac{1}{2}\left(\frac{1}{1-\sqrt{2}x+x^2}+\frac{1}{1+\sqrt{2}x+x^2}\right)\\&-\frac{x}{2\sqrt{2}}\left(\frac{1}{1-\sqrt{2}x+x^2}-\frac{1}{1+\sqrt{2}x+x^2}\right)\\=&\frac{\frac{1}{2}-\frac{x}{2\sqrt{2}}}{1-\sqrt{2}x+x^2}+\frac{\frac{1}{2}+\frac{x}{2\sqrt{2}}}{1+\sqrt{2}x+x^2}\\=& \frac{1+\sqrt{2}x}{4(1+\sqrt{2}x+x^2)}+\frac{1-\sqrt{2}x}{4(1+\sqrt{2}x+x^2)}\\&+\frac{1}{4(1+\sqrt{2}x+x^2)}+\frac{1}{4(1-\sqrt{2}x+x^2)}.\end{align} Finally, integrating the two upper-line terms into a logarithm and integrating the two lower-line terms into an inverse tan function, we get: \begin{align} \int \frac{\mathrm{d}x}{1+x^4}=&\frac{1}{4\sqrt{2}}\log|1+\sqrt{2}x+x^2|-\frac{1}{4\sqrt{2}}\log|1-\sqrt{2}x+x^2|\\&+\frac{1}{2\sqrt{2}}\mathrm{arctan}(\sqrt{2}x+1)+\frac{1}{2\sqrt{2}}\mathrm{arctan}(\sqrt{2}x-1).\end{align}Aaaaaaand here's another fun exercise: differentiate \(\sin(x)\) from first principles! And here's a hint (it's written in white, so highlight it):
You'll probably need to show at some point that \(\lim_{x\to 0}\frac{\sin(x)}{x}=1\)...and this can totes be done by proving the following inequality \(\sin(x)<x<\tan(x)\) for \(x\in(0,\frac{\pi}{2})\). And...this can be done...geometrically.
=P
Thursday, 2 October 2014
Analysis for Realsies: 5
Hey guys! I hope that you've been having a good semester break. I...had a picnic on campus today? Totes the right weather for picnics, right? =P
I think that a few weeks ago, we had a look at question about Fibonacci numbers in our tute, and the solution sheet doesn't provide an actual solution for it. Soooooooo...here we go!
First, the question:
"You have seen the Fibonacci sequence, defined by \(f_{n+2}=f_{n+1}+f_n\) with \(f_1=f_2=1\). Now define a new sequence as follows: \begin{align}g_n=\frac{f_{n+1}}{f_n}.\end{align} Find the limit of this sequence (you should try to prove that the limit exists first). Do you recognise the limit? Is there something special about it?"
Okay, so I can see at least two ways to do this problem. The usual first-year-accelerated-maths-1 approach would be to use solve for the Fibonacci sequence as a second-order difference equation. Doing this, you get: \begin{align} f_n=\frac{1}{\sqrt{5}}(\phi^n-(-\phi)^{-n}),\text{ where }\phi=\frac{1+\sqrt{5}}{2}\text{ is the golden ratio.} \end{align} And it's pretty straightforward to work out that the limit \begin{align}\lim_{n\rightarrow\infty} g_n=\lim_{n\to\infty}\frac{\phi^{(n+1)}-(-\phi)^{-(n+1)}}{\phi^n-(-\phi)^{-n}}=\phi.\end{align}
Happily, in this course, you guys don't learn about difference equations, so we totes get to do it in a different way! So, first thing's first, let's use the monotone convergence theorem to show that this sequence converges. Observe that \begin{align} g_n=\frac{f_{n+1}}{f_n}=\frac{f_{n-1}+f_n}{f_n}=\frac{1+\left(\frac{f_n}{f_{n-1}}\right)}{\left(\frac{f_n}{f_{n-1}}\right)}=\frac{1+g_{n-1}}{g_{n-1}}.\end{align} Taking this one step further by replacing \(g_{n-1}\) with \(\frac{1+g_{n-2}}{g_{n-2}}\), we obtain that: \begin{align} g_n=\frac{1+2g_{n-2}}{1+g_{n-2}}=1+\frac{g_{n-2}}{1+g_{n-2}}=2-\frac{1}{1+g_{n-2}}.\end{align} Since \(f_n\) is always positive, \(g_n\) (as a fraction of two positive numbers) is always positive. And for positive numbers, \(\frac{1}{1+x}>0\), so the above equation tells us that the sequence \(\{g_n\}\) is bounded between \(1\) and \(2\) (although you do need to check \(g_1\) and \(g_2\) separately, because they don't necessarily satisfy the above recursion). Now, we'd love to apply the monotone convergence theorem, but the actual sequence isn't monotonic. Thankfully, the odd indexed terms are increasing, and the even indexed terms are decreasing, which means that we can still apply the theorem to these odd and even index subsequences.
As an example, let's prove (by induction) that the odd terms are increasing.
Consider the statements \(P(n): g_{2n+1}>g_{2n-1}\). For \(n=1\), this is true \(g_3=\frac{3}{2}>1=g_1\). So, we've checked the "base case" of our induction proof. Let's check the "induction step". Assume that \(P(k)\) is true. This means that: \begin{align}g_{2k+1}&>g_{2k-1}\\ \Rightarrow 1+g_{2k+1}&>1+g_{2k-1}\\ \Rightarrow \frac{1}{1+g_{2k+1}}&<\frac{1}{1+g_{2k-1}}\\ \Rightarrow 2-\frac{1}{1+g_{2k+1}}&>2-\frac{1}{1+g_{2k-1}}\\ \Rightarrow g_{2k+3}&>g_{2k+1}. \end{align} And so we see that \(P(k)\Rightarrow P(k+1)\), and so by the principle of mathematical induction, \(P(n)\) is true for all natural numbers \(n\). That is: the odd indexed terms are increasing.
Similarly, YOU can show that the even terms are decreasing. =)
So, the subsequence \(\{g_{2n-1}\}\) converges to some \(g\). Specifically, \begin{align} g=\lim_{n\to\infty}g_n=\lim_{n\to\infty}2-\frac{1}{1+g_{n-2}}=2-\frac{1}{1+g}.\end{align} Solving for \(g\), we get: \begin{align} g=\frac{1\pm\sqrt{5}}{2}=\frac{1+\sqrt{5}}{2}.\end{align} We take the positive square root as \(g\) needs to be greater than or equal to \(1\). Similarly, the subsequence \(\{g_{2n}\}\) converges to the same \(g\), which of course, is the golden ratio \(\phi\).
Finally, we need to show that the fact that these two subsequences both converge to \(g=\phi\), means that the whole sequence \(g_n\) converges to \(\phi\). And...let's do this the fun way: \(\epsilon-N\). Huzzah! Okay, so, the fact that \(\{g_{2n-1}\}\) converges to \(\phi\) means that: for every \(\epsilon>0\), there exists some \(N_{odd}\in\mathbb{N}\) such that \(\forall n>N_{odd}\), \(|g_{2n-1}-\phi|<\epsilon\). Similarly, the fact that \(\{g_{2n}\}\) converges to \(\phi\) means that: for every \(\epsilon>0\), there exists some \(N_{even}\in\mathbb{N}\) such that \(\forall n>N_{even}\), \(|g_{2n}-\phi|<\epsilon\). Thus, for every \(\epsilon>0\), there exists a natural number \(N=\max\{2N_{odd}-1,2N_{even}\}\) such that \(\forall n>N\), \begin{align} |g_n-\phi|=\left\{\right. \begin{array}{c c} |g_{2n_1-1}-\phi| <\epsilon, & \text{ if the index }n=2n_1-1\text{ is odd, and} \\ |g_{2n_2}-\phi|<\epsilon, & \text{ if the index }n=2n_2\text{ is even.}\end{array}\end{align} This is precisely the \(\epsilon-N\) definition of convergence, and we're done.
HURRAY!
So easy, right? =P
I think that a few weeks ago, we had a look at question about Fibonacci numbers in our tute, and the solution sheet doesn't provide an actual solution for it. Soooooooo...here we go!
First, the question:
"You have seen the Fibonacci sequence, defined by \(f_{n+2}=f_{n+1}+f_n\) with \(f_1=f_2=1\). Now define a new sequence as follows: \begin{align}g_n=\frac{f_{n+1}}{f_n}.\end{align} Find the limit of this sequence (you should try to prove that the limit exists first). Do you recognise the limit? Is there something special about it?"
Okay, so I can see at least two ways to do this problem. The usual first-year-accelerated-maths-1 approach would be to use solve for the Fibonacci sequence as a second-order difference equation. Doing this, you get: \begin{align} f_n=\frac{1}{\sqrt{5}}(\phi^n-(-\phi)^{-n}),\text{ where }\phi=\frac{1+\sqrt{5}}{2}\text{ is the golden ratio.} \end{align} And it's pretty straightforward to work out that the limit \begin{align}\lim_{n\rightarrow\infty} g_n=\lim_{n\to\infty}\frac{\phi^{(n+1)}-(-\phi)^{-(n+1)}}{\phi^n-(-\phi)^{-n}}=\phi.\end{align}
Happily, in this course, you guys don't learn about difference equations, so we totes get to do it in a different way! So, first thing's first, let's use the monotone convergence theorem to show that this sequence converges. Observe that \begin{align} g_n=\frac{f_{n+1}}{f_n}=\frac{f_{n-1}+f_n}{f_n}=\frac{1+\left(\frac{f_n}{f_{n-1}}\right)}{\left(\frac{f_n}{f_{n-1}}\right)}=\frac{1+g_{n-1}}{g_{n-1}}.\end{align} Taking this one step further by replacing \(g_{n-1}\) with \(\frac{1+g_{n-2}}{g_{n-2}}\), we obtain that: \begin{align} g_n=\frac{1+2g_{n-2}}{1+g_{n-2}}=1+\frac{g_{n-2}}{1+g_{n-2}}=2-\frac{1}{1+g_{n-2}}.\end{align} Since \(f_n\) is always positive, \(g_n\) (as a fraction of two positive numbers) is always positive. And for positive numbers, \(\frac{1}{1+x}>0\), so the above equation tells us that the sequence \(\{g_n\}\) is bounded between \(1\) and \(2\) (although you do need to check \(g_1\) and \(g_2\) separately, because they don't necessarily satisfy the above recursion). Now, we'd love to apply the monotone convergence theorem, but the actual sequence isn't monotonic. Thankfully, the odd indexed terms are increasing, and the even indexed terms are decreasing, which means that we can still apply the theorem to these odd and even index subsequences.
As an example, let's prove (by induction) that the odd terms are increasing.
Consider the statements \(P(n): g_{2n+1}>g_{2n-1}\). For \(n=1\), this is true \(g_3=\frac{3}{2}>1=g_1\). So, we've checked the "base case" of our induction proof. Let's check the "induction step". Assume that \(P(k)\) is true. This means that: \begin{align}g_{2k+1}&>g_{2k-1}\\ \Rightarrow 1+g_{2k+1}&>1+g_{2k-1}\\ \Rightarrow \frac{1}{1+g_{2k+1}}&<\frac{1}{1+g_{2k-1}}\\ \Rightarrow 2-\frac{1}{1+g_{2k+1}}&>2-\frac{1}{1+g_{2k-1}}\\ \Rightarrow g_{2k+3}&>g_{2k+1}. \end{align} And so we see that \(P(k)\Rightarrow P(k+1)\), and so by the principle of mathematical induction, \(P(n)\) is true for all natural numbers \(n\). That is: the odd indexed terms are increasing.
Similarly, YOU can show that the even terms are decreasing. =)
So, the subsequence \(\{g_{2n-1}\}\) converges to some \(g\). Specifically, \begin{align} g=\lim_{n\to\infty}g_n=\lim_{n\to\infty}2-\frac{1}{1+g_{n-2}}=2-\frac{1}{1+g}.\end{align} Solving for \(g\), we get: \begin{align} g=\frac{1\pm\sqrt{5}}{2}=\frac{1+\sqrt{5}}{2}.\end{align} We take the positive square root as \(g\) needs to be greater than or equal to \(1\). Similarly, the subsequence \(\{g_{2n}\}\) converges to the same \(g\), which of course, is the golden ratio \(\phi\).
Finally, we need to show that the fact that these two subsequences both converge to \(g=\phi\), means that the whole sequence \(g_n\) converges to \(\phi\). And...let's do this the fun way: \(\epsilon-N\). Huzzah! Okay, so, the fact that \(\{g_{2n-1}\}\) converges to \(\phi\) means that: for every \(\epsilon>0\), there exists some \(N_{odd}\in\mathbb{N}\) such that \(\forall n>N_{odd}\), \(|g_{2n-1}-\phi|<\epsilon\). Similarly, the fact that \(\{g_{2n}\}\) converges to \(\phi\) means that: for every \(\epsilon>0\), there exists some \(N_{even}\in\mathbb{N}\) such that \(\forall n>N_{even}\), \(|g_{2n}-\phi|<\epsilon\). Thus, for every \(\epsilon>0\), there exists a natural number \(N=\max\{2N_{odd}-1,2N_{even}\}\) such that \(\forall n>N\), \begin{align} |g_n-\phi|=\left\{\right. \begin{array}{c c} |g_{2n_1-1}-\phi| <\epsilon, & \text{ if the index }n=2n_1-1\text{ is odd, and} \\ |g_{2n_2}-\phi|<\epsilon, & \text{ if the index }n=2n_2\text{ is even.}\end{array}\end{align} This is precisely the \(\epsilon-N\) definition of convergence, and we're done.
HURRAY!
So easy, right? =P
Friday, 12 September 2014
Analysis for Realsies: 4
As promised, here're a few alternative solutions to questions 2 and 3 from your second assignment!
Question 2: Carefully prove that if \(p\) is a prime number, then \(\sqrt{p}\) is irrational.
We'll prove this by contradiction. Assume that \(p\) is a prime number and that \(\sqrt{p}\) is rational (premise). This means that there are coprime integers \(a\in\mathbb{Z},b\in\mathbb{N}\) such that \(\sqrt{p}=\frac{a}{b}\). Hence, \(p=\frac{a^2}{b^2}\), which in turn means that \(a^2=pb^2\). By definition, this means that \(p\) is a factor of \(a^2\). At this point, the proof can take one of two directions...
Proof 1 (the direct approach):
Invoking the unique-prime-factorisation theorem (better known as the fundamental theorem of arithmetic), we see that \(a\) and \(b\) may be respectively uniquely expressed as a product of prime factors: \begin{align} a=p_1\times p_2\times\ldots\times p_n\text{ and }b=q_1\times q_2\times\ldots\times q_n\end{align}. Thus, the equation \(a^2=pb^2\) becomes: \begin{align} p_1\times\ldots\times p_m\times p_1\times\ldots\times p_m=p\times q_1\times\ldots\times q_n\times q_1\times\ldots\times q_n.\end{align} Since \(a^2=pb^2\) is an integer - \(\mathbb{Z}\) is, after all, closed under multiplication - the above expressions must both be the unique (up to reordering of factors) prime factorisation of \(a^2\). However, the left-hand-side has \(2n\) terms, whilst the right-hand-side has \(2m+1\) terms\(\Rightarrow\)CONTRADICTION!
Comments: this is a very elegant approach - and to be honest, I've never thought of it before. Probably because I've always just gone to this second method:
Proof 2 (the standard approach):
Similarly invoking the unique-prime-factorisation theorem, we express the equation \(a^2=pb^2\) as: \begin{align} p_1\times\ldots\times p_n\times p_1\times\ldots\times p_n=p\times q_1\times\ldots\times q_m\times q_1\times\ldots\times q_m.\end{align} This means that \(p\) must be equal to one of the \(p_i\). Thus, \(p=p_i\) is a divisor of \(a\), that is: there exists \(k\in\mathbb{Z}\) such that \(a=pk\). This in turn implies that \(p^2k^2=pb^2\), and hence \(pk^2=b^2\). By the same argument as above, this means that \(p\) is also a divisor of \(b\). But this then means that \(a\) and \(b\) both have \(p\) as a factor, thus contradicting the fact that \(a\) and \(b\) are coprime...and we're done.
Comments: this more-or-less follows the approach you guys took for proving that \(\sqrt{2}\) is irrational.
Note that the rough ideas of these proof should work more generally. And you should be able to use this to show that the square roots of "square-free" integers are irrational!
And now, it's time for...
Question 3: Carefully prove that if \(A\) and \(B\) are nonempty [bounded] sets such that for each \(a\in A, \exists b\in B\) with \(a<b\) and for each \(b\in B,\exists a\in A\) with \(a<b\) then \begin{align} \inf A\leq\inf B\text{ and }\sup A\leq \sup B.\end{align} Well, the thing about this question is that it really should have been split into two questions. Instead of showing that: \begin{align} (\forall a\in A, \exists b\in B, a<b)&\wedge (\forall b\in B, \exists a\in A, a<b)\\ \Rightarrow (\inf A\leq \inf B)&\wedge (\sup A\leq \sup B), \end{align} I would have liked you guys to try to prove the following two facts: \begin{align}(\forall a\in A, \exists b\in B, a<b)&\Rightarrow (\sup A\leq \sup B)\text{ and}\\ (\forall b\in B, \exists a\in A, a<b)&\Rightarrow (\inf A\leq \inf B). \end{align} These are really disparate facts, and it might be a bit more illuminating to consider them separately. In fact, I'm just going to prove the first of these two facts - I'll leave it as an exercise for you to repeat the proof and derive the second.
Method 1 (by definition):
This first method utilises one of the defining properties of the supremum of a set - that is is the smallest upper bound. So, if we can show that \(\sup B\) is also an upper bound for the set \(A\), then by definition, the smallest upper bound \(\sup A\) of \(A\) must be less than or equal to \(\sup B\). In order to show that \(\sup B\) is an upper bound of \(A\), consider an arbitrary element \(a\in A\). Unpacking our premise that \begin{align}\forall a\in A, \exists b\in B, a<b \end{align} we see that there is some \(b\in B\) such that \(a<b\). But then, by the definitional fact that the supremum \(\sup B\) of \(B\) must be greater than or equal to anything in \(B\), we conclude that: \begin{align} \text{given an arbitrary }a\in A, \exists b\in B, a<b<\sup B.\end{align} This of course tells us that \(\sup B\) is an upper bound for \(A\), and we're done.
Comment: this is a particular elegant/clean method, and as such might be difficult to see the first few times that you approach questions of this nature. But with more practice, you'll be able to see this no probs!
Method 2 (by another definition):
Our second method is based on the slightly more geometric/intuitionistic characterisation of the supremum \(\sup A\) of a set \(A\) satisfying the properties that:
Let's assume that \(\sup A>\sup B\), then choose \(\epsilon=\sup A-\sup B>0\) and we know that \(\sup A-\epsilon<\sup B\), hence: \begin{align}\sup B=\sup A-(\sup A - \sup B)=\sup A-\epsilon>\sup B.\end{align} Which, is a contradiction, because a number cannot be strictly greater than itself. This then gives us the desired conclusion that \(\sup A\leq\sup B\). =)
Now, I also promised to write up solutions to Question 6 from your tutorial because that was kinda tricky (and the official solutions don't have it). And I will...at some point during the week? For now, I just want to really encourage you guys to try those "Do this for homework" exercises - they're pretty involved, but they're questions that you can learn a HUGE deal from.
Huzzah?!??
=)
Question 2: Carefully prove that if \(p\) is a prime number, then \(\sqrt{p}\) is irrational.
We'll prove this by contradiction. Assume that \(p\) is a prime number and that \(\sqrt{p}\) is rational (premise). This means that there are coprime integers \(a\in\mathbb{Z},b\in\mathbb{N}\) such that \(\sqrt{p}=\frac{a}{b}\). Hence, \(p=\frac{a^2}{b^2}\), which in turn means that \(a^2=pb^2\). By definition, this means that \(p\) is a factor of \(a^2\). At this point, the proof can take one of two directions...
Proof 1 (the direct approach):
Invoking the unique-prime-factorisation theorem (better known as the fundamental theorem of arithmetic), we see that \(a\) and \(b\) may be respectively uniquely expressed as a product of prime factors: \begin{align} a=p_1\times p_2\times\ldots\times p_n\text{ and }b=q_1\times q_2\times\ldots\times q_n\end{align}. Thus, the equation \(a^2=pb^2\) becomes: \begin{align} p_1\times\ldots\times p_m\times p_1\times\ldots\times p_m=p\times q_1\times\ldots\times q_n\times q_1\times\ldots\times q_n.\end{align} Since \(a^2=pb^2\) is an integer - \(\mathbb{Z}\) is, after all, closed under multiplication - the above expressions must both be the unique (up to reordering of factors) prime factorisation of \(a^2\). However, the left-hand-side has \(2n\) terms, whilst the right-hand-side has \(2m+1\) terms\(\Rightarrow\)CONTRADICTION!
Comments: this is a very elegant approach - and to be honest, I've never thought of it before. Probably because I've always just gone to this second method:
Proof 2 (the standard approach):
Similarly invoking the unique-prime-factorisation theorem, we express the equation \(a^2=pb^2\) as: \begin{align} p_1\times\ldots\times p_n\times p_1\times\ldots\times p_n=p\times q_1\times\ldots\times q_m\times q_1\times\ldots\times q_m.\end{align} This means that \(p\) must be equal to one of the \(p_i\). Thus, \(p=p_i\) is a divisor of \(a\), that is: there exists \(k\in\mathbb{Z}\) such that \(a=pk\). This in turn implies that \(p^2k^2=pb^2\), and hence \(pk^2=b^2\). By the same argument as above, this means that \(p\) is also a divisor of \(b\). But this then means that \(a\) and \(b\) both have \(p\) as a factor, thus contradicting the fact that \(a\) and \(b\) are coprime...and we're done.
Comments: this more-or-less follows the approach you guys took for proving that \(\sqrt{2}\) is irrational.
Note that the rough ideas of these proof should work more generally. And you should be able to use this to show that the square roots of "square-free" integers are irrational!
And now, it's time for...
Question 3: Carefully prove that if \(A\) and \(B\) are nonempty [bounded] sets such that for each \(a\in A, \exists b\in B\) with \(a<b\) and for each \(b\in B,\exists a\in A\) with \(a<b\) then \begin{align} \inf A\leq\inf B\text{ and }\sup A\leq \sup B.\end{align} Well, the thing about this question is that it really should have been split into two questions. Instead of showing that: \begin{align} (\forall a\in A, \exists b\in B, a<b)&\wedge (\forall b\in B, \exists a\in A, a<b)\\ \Rightarrow (\inf A\leq \inf B)&\wedge (\sup A\leq \sup B), \end{align} I would have liked you guys to try to prove the following two facts: \begin{align}(\forall a\in A, \exists b\in B, a<b)&\Rightarrow (\sup A\leq \sup B)\text{ and}\\ (\forall b\in B, \exists a\in A, a<b)&\Rightarrow (\inf A\leq \inf B). \end{align} These are really disparate facts, and it might be a bit more illuminating to consider them separately. In fact, I'm just going to prove the first of these two facts - I'll leave it as an exercise for you to repeat the proof and derive the second.
Method 1 (by definition):
This first method utilises one of the defining properties of the supremum of a set - that is is the smallest upper bound. So, if we can show that \(\sup B\) is also an upper bound for the set \(A\), then by definition, the smallest upper bound \(\sup A\) of \(A\) must be less than or equal to \(\sup B\). In order to show that \(\sup B\) is an upper bound of \(A\), consider an arbitrary element \(a\in A\). Unpacking our premise that \begin{align}\forall a\in A, \exists b\in B, a<b \end{align} we see that there is some \(b\in B\) such that \(a<b\). But then, by the definitional fact that the supremum \(\sup B\) of \(B\) must be greater than or equal to anything in \(B\), we conclude that: \begin{align} \text{given an arbitrary }a\in A, \exists b\in B, a<b<\sup B.\end{align} This of course tells us that \(\sup B\) is an upper bound for \(A\), and we're done.
Comment: this is a particular elegant/clean method, and as such might be difficult to see the first few times that you approach questions of this nature. But with more practice, you'll be able to see this no probs!
Method 2 (by another definition):
Our second method is based on the slightly more geometric/intuitionistic characterisation of the supremum \(\sup A\) of a set \(A\) satisfying the properties that:
- an upper bound of \(A\), and
- for any \(\epsilon>0\), \(\sup A-\epsilon\) is less than some element \(a\in A\).
Let's assume that \(\sup A>\sup B\), then choose \(\epsilon=\sup A-\sup B>0\) and we know that \(\sup A-\epsilon<\sup B\), hence: \begin{align}\sup B=\sup A-(\sup A - \sup B)=\sup A-\epsilon>\sup B.\end{align} Which, is a contradiction, because a number cannot be strictly greater than itself. This then gives us the desired conclusion that \(\sup A\leq\sup B\). =)
Now, I also promised to write up solutions to Question 6 from your tutorial because that was kinda tricky (and the official solutions don't have it). And I will...at some point during the week? For now, I just want to really encourage you guys to try those "Do this for homework" exercises - they're pretty involved, but they're questions that you can learn a HUGE deal from.
Huzzah?!??
=)
Monday, 1 September 2014
Analysis for Realsies: 3
I love Community. You love Community. Who doesn't love Community?
Now, if you love Community (premise), then you love Magnitude (inference). And if love Magnitude, then surely you love POP! POP! quizzes (conclusion/pun-ch line), right?
Question 1 (it's the only question): which of these four numbers do we know for certain is irrational?
A) \(\pi+e\).
B) \(e\pi\).
C) \(e^\pi\).
D) All of the above.
Strangely enough, the answer is C: we have no idea if \(\pi+e\) or \( e\pi\) are actually irrational (even though we strongly suspect that they are). Having said that, we do know that at least one of those two numbers is irrational. Assume not, then there exist integers \(p,q\in\mathbb{N}\) such that \(\pi+e=\frac{p}{q}\) and \(m,n\in\mathbb{N}\) such that \(e\pi=\frac{m}{n}\). Then, \begin{align}\frac{p}{q}\pi=\pi^2+e\pi=\pi^2+\frac{m}{n}\Rightarrow 0=\pi^2-\frac{p}{q}\pi+\frac{m}{n}.\end{align} Which is a contradiction, because \(\pi\) is transcendental and (hence) cannot be the solution to some quadratic equation with rational coefficients.
To show that \(e^\pi\) is irrational, we invoke the Gelfond-Schneider theorem. Which says that if \(a,b\) are algebraic numbers with \(a\neq0,1\) and \(b\) irrational, then \(a^b\) is transcendental (and hence necessarily irrational). The fact that \(e^\pi\) is irrational then follows from using the (kinda awesome) fact that \(e^\pi=(-1)^{-\sqrt{-1}}\).
I HAVE NO IDEA HOW THE GELFOND-SCHNEIDER THEOREM WORKS.
Number theory, she is a...how you say...a...bi-........................................-iiiutiful. =)
Now, if you love Community (premise), then you love Magnitude (inference). And if love Magnitude, then surely you love POP! POP! quizzes (conclusion/pun-ch line), right?
Question 1 (it's the only question): which of these four numbers do we know for certain is irrational?
A) \(\pi+e\).
B) \(e\pi\).
C) \(e^\pi\).
D) All of the above.
Strangely enough, the answer is C: we have no idea if \(\pi+e\) or \( e\pi\) are actually irrational (even though we strongly suspect that they are). Having said that, we do know that at least one of those two numbers is irrational. Assume not, then there exist integers \(p,q\in\mathbb{N}\) such that \(\pi+e=\frac{p}{q}\) and \(m,n\in\mathbb{N}\) such that \(e\pi=\frac{m}{n}\). Then, \begin{align}\frac{p}{q}\pi=\pi^2+e\pi=\pi^2+\frac{m}{n}\Rightarrow 0=\pi^2-\frac{p}{q}\pi+\frac{m}{n}.\end{align} Which is a contradiction, because \(\pi\) is transcendental and (hence) cannot be the solution to some quadratic equation with rational coefficients.
To show that \(e^\pi\) is irrational, we invoke the Gelfond-Schneider theorem. Which says that if \(a,b\) are algebraic numbers with \(a\neq0,1\) and \(b\) irrational, then \(a^b\) is transcendental (and hence necessarily irrational). The fact that \(e^\pi\) is irrational then follows from using the (kinda awesome) fact that \(e^\pi=(-1)^{-\sqrt{-1}}\).
I HAVE NO IDEA HOW THE GELFOND-SCHNEIDER THEOREM WORKS.
Number theory, she is a...how you say...a...bi-........................................-iiiutiful. =)
Monday, 18 August 2014
Analysis for Realsies: 2
Hey guys! This post is based on a little variant of question 5c. on last week's Tute A sheet. In particular, you were told that a three-digit number is divisible by \(3\) if and only if the sum of its digits add up to a multiple of \(3\). If you were in my tute, I should have pointed out to you that your proof works also for divisibility by \(9\), and that this fact is true for any integer - not just three-digit ones. Now, instead of playing around with divisibility by 3, we're going to have a play around with divisibility by 11. =P
I think that it's a little odd that (ever since your first kindergarten lesson on factorising quadratics) we're so adept at factorising algebraic objects like: \begin{align} x^2-y^2=(x-y)(x+y), \end{align} and yet most of us never think to use the above completing-the-square formula on actual numbers...to simplify computations. For example: \begin{align} 6.79^2-3.21^2=(6.79-3.21)(6.79+3.21)=3.58\times 10=35.8 \end{align}
And along the same vein of thought, some of you know that if you expand \((x+y)^n\), you get something of the form: \begin{align} x^n+nx^{n-1}y+{n\choose 2}x^{n-2}y+\ldots+y^n.\end{align} But maybe you've never thought to apply it to actual numbers to get something like: \begin{align} 10^k=(11-1)^k=11^k+k\cdot11^{k-1}\cdot(-1)+{k\choose2}\cdot11^{k-2}\cdot(-1)^2+\ldots+(-1)^k.\end{align} So, one consequence of this is that any power \(10^k\) of \(10\) can be written as \begin{align}11\times\text{something}+(-1)^\text{k}.\end{align}
So, now let's take a \(n\)-digit number like \(\overline{a_na_{n-1}\ldots a_1}\), then we know that this number can be written as the following sum:\begin{align}a_n10^n+a_{n-1}10^{n-1}+\ldots+a_1.\end{align} Now, invoking our earlier observation about powers of \(10\), this sum can be written as: \begin{align} 11\times\text{some big nasty sum of integers}+a_n(-1)^n+a_{n-1}(-1)^{n-1}+\ldots+a_1(-1)^0.\end{align} Since \begin{align} a_n(-1)^n+a_{n-1}(-1)^{n-1}+\ldots+a_1(-1)^0 \end{align} is just \begin{align} a_0-a_1+a_2-a_3+\ldots+(-1)^na_n,\end{align} so to figure out if a number is divisible by \(11\), you can just take its last digit, minus the second last, add the third last, minus the fourth last...etc., and if the number that you wind up with is divisible by \(11\), then the entire thing is.
Let's try this out on an actual number! Let's take \(80586\). Well, \(6-8+5-0+8=11\) is totes divisible by \(11\). Sooo, \(80586\) should also be divisible. And it totes is: \(80586=11\times 7326.\)
The algebra in the previous paragraph might have been a tad on the messy side, but I think that you should all be fine with it! =)
I think that it's a little odd that (ever since your first kindergarten lesson on factorising quadratics) we're so adept at factorising algebraic objects like: \begin{align} x^2-y^2=(x-y)(x+y), \end{align} and yet most of us never think to use the above completing-the-square formula on actual numbers...to simplify computations. For example: \begin{align} 6.79^2-3.21^2=(6.79-3.21)(6.79+3.21)=3.58\times 10=35.8 \end{align}
And along the same vein of thought, some of you know that if you expand \((x+y)^n\), you get something of the form: \begin{align} x^n+nx^{n-1}y+{n\choose 2}x^{n-2}y+\ldots+y^n.\end{align} But maybe you've never thought to apply it to actual numbers to get something like: \begin{align} 10^k=(11-1)^k=11^k+k\cdot11^{k-1}\cdot(-1)+{k\choose2}\cdot11^{k-2}\cdot(-1)^2+\ldots+(-1)^k.\end{align} So, one consequence of this is that any power \(10^k\) of \(10\) can be written as \begin{align}11\times\text{something}+(-1)^\text{k}.\end{align}
So, now let's take a \(n\)-digit number like \(\overline{a_na_{n-1}\ldots a_1}\), then we know that this number can be written as the following sum:\begin{align}a_n10^n+a_{n-1}10^{n-1}+\ldots+a_1.\end{align} Now, invoking our earlier observation about powers of \(10\), this sum can be written as: \begin{align} 11\times\text{some big nasty sum of integers}+a_n(-1)^n+a_{n-1}(-1)^{n-1}+\ldots+a_1(-1)^0.\end{align} Since \begin{align} a_n(-1)^n+a_{n-1}(-1)^{n-1}+\ldots+a_1(-1)^0 \end{align} is just \begin{align} a_0-a_1+a_2-a_3+\ldots+(-1)^na_n,\end{align} so to figure out if a number is divisible by \(11\), you can just take its last digit, minus the second last, add the third last, minus the fourth last...etc., and if the number that you wind up with is divisible by \(11\), then the entire thing is.
Let's try this out on an actual number! Let's take \(80586\). Well, \(6-8+5-0+8=11\) is totes divisible by \(11\). Sooo, \(80586\) should also be divisible. And it totes is: \(80586=11\times 7326.\)
The algebra in the previous paragraph might have been a tad on the messy side, but I think that you should all be fine with it! =)
Wednesday, 13 August 2014
Analysis for Realsies: 1
If you were in one of my B-tutorials last week, you might recall this little "wrong" proof:
Claim: Every natural number can be unambiguously described in fourteen words or fewer.
Proof: (let's break this up into steps) We're going to attempt a proof by contradiction.
1) Assume that there exists a natural number \(n\in\mathbb{N}\) that cannot be unambiguously described in fourteen words or fewer.
2) Then (by the well-ordering principle), there is a smallest number \(n_0\in\mathbb{N}\) that cannot be unambiguously described in fourteen words or fewer.
3) Then, \(n_0\) is "the smallest natural number that cannot be unambiguously described in fourteen words or fewer".
4) But this is an unambiguous description of \(n_0\), thus contradicting our initial claim that there exists a natural number that cannot be unambiguously described in fourteen words or fewer.
...Q.E.D.???
Now, there's something that feels pretty darn wrong about this "result" - after all, if I write down an epically epically HUGE number, I shouldn't expect to be able to unambiguously express it in fewer than fifteen words. I mean, this English language is finite, and the number of sentences that you can build with fourteen words is finite, but the number of natural numbers is infinite. So, the claim is totes wrong.
But where does it go wrong?
And the answer is kinda subtle...the problem at the heart of this proof is the following description:
(*): "the smallest natural number that cannot be unambiguously described in fourteen words or fewer",
whilst it certainly intuitively makes sense to us as a description, it is self-referential, and you've already seen from class what can happen if you allow for self-referential statements: Russell's Paradox! In particular, in our case, assigning this description to a number contradicts the very description: it's totes logically inconsistent.
So, we see that in step 4), we can't actually conclude that we've contradicted our initial assumption; all we've done is shown that (*) is a sucky sucky description.
Logic, fo'shizzle and stuff.
=)
Claim: Every natural number can be unambiguously described in fourteen words or fewer.
Proof: (let's break this up into steps) We're going to attempt a proof by contradiction.
1) Assume that there exists a natural number \(n\in\mathbb{N}\) that cannot be unambiguously described in fourteen words or fewer.
2) Then (by the well-ordering principle), there is a smallest number \(n_0\in\mathbb{N}\) that cannot be unambiguously described in fourteen words or fewer.
3) Then, \(n_0\) is "the smallest natural number that cannot be unambiguously described in fourteen words or fewer".
4) But this is an unambiguous description of \(n_0\), thus contradicting our initial claim that there exists a natural number that cannot be unambiguously described in fourteen words or fewer.
...Q.E.D.???
Now, there's something that feels pretty darn wrong about this "result" - after all, if I write down an epically epically HUGE number, I shouldn't expect to be able to unambiguously express it in fewer than fifteen words. I mean, this English language is finite, and the number of sentences that you can build with fourteen words is finite, but the number of natural numbers is infinite. So, the claim is totes wrong.
But where does it go wrong?
And the answer is kinda subtle...the problem at the heart of this proof is the following description:
(*): "the smallest natural number that cannot be unambiguously described in fourteen words or fewer",
whilst it certainly intuitively makes sense to us as a description, it is self-referential, and you've already seen from class what can happen if you allow for self-referential statements: Russell's Paradox! In particular, in our case, assigning this description to a number contradicts the very description: it's totes logically inconsistent.
So, we see that in step 4), we can't actually conclude that we've contradicted our initial assumption; all we've done is shown that (*) is a sucky sucky description.
Logic, fo'shizzle and stuff.
=)
Subscribe to:
Posts (Atom)