Posts

Pocket maths: good rational approximations

Pt En An obvious way of creating rational approximations for irrational numbers is by truncating its decimal expansion. For example, $3$, $3.1$ and $3.14$ are all rational approximations of $\pi $; as fractions, those approximations would be written $3$, $\frac{31}{10}$ and $\frac{314}{100} $. Notice how $\frac{314}{100}$ has $100$ as the denominator and yet only produces an approximation correct up to two decimal places. Claim: by using continued fractions one can obtain better rational approximations for irrational numbers. Method: if $x $ is an irrational number, instead of truncating its decimal expansion, we can truncate its continued fraction. Taking $\pi $ as an example, we have $$\pi = 3 + \frac1{7 + \frac1{15 + \cdots}} $$ and by taking $$\pi \approx 3 + \frac17 = \frac{22}{7} $$ we get the approximation $\pi \approx 3.14285\cdots$: it is correct up to two decimal places just as $\frac{314}{100} $, but $7$ is a much smaller denominator than $100$. (And all in all, $\frac...
Post a Comment
Read more

Twitter proof: the roots go hand in hand

Pt En In this twitter proof we will have a look at a rather curious, yet simple, property of real polynomials. Claim: if $p(x) = \sum_{i=0}^n a_ix^i $ is a polynomial with real coefficients, then for all complex numbers $z $, $$p(z) = 0 \iff p(\bar{z}) = 0$$ which means that the complex roots of $p(x) $ come in conjugate pairs. Twitter proof: it suffices to show that $p(z) = 0 \implies p(\bar{z}) = 0$. Assume that $p(z) = 0$ and recall that $a_i = \bar{a_i} $: $$\begin{align} p(\bar{z}) &= \sum_{i=0}^n a_i\bar{z}^i \\ &= \sum_{i=0}^n \overline{a_iz^i} \\ &= \overline{\sum_{i=0}^n a_iz^i} = \overline{p(z)} = 0 \end {align} $$ Neste post vamos dar uma olhadela a uma propriedade curiosa, mas simples, dos polinómios com coeficientes reais. Proposição: se $p(x) = \sum_{i=0}^n a_ix^i $ é um polinómio com coeficientes reais, então para qualquer número complexo $z $ vem $$p(z) = 0 \iff p(\bar{z}) = 0$$ o que significa que as raízes complexas de $p(x) $ vêm em pares conjuga...
Post a Comment
Read more

Twitter proof: interpolating polynomials

Pt En In this post I will show the existence of a family of polynomials that are very useful for interpolation. For that I will use what are known as Lagrange polynomials. Claim: given $n+1$ pairs $(x_i, y_i) $ with $0\leq i \leq n $ and with $x_i \neq x_j $ whenever $i\neq j $, there exists a polynomial $p(x) $ of degree at most $n $ such that $$p(x_i) = y_i,\ i = 0, \cdots, n $$ Twitter proof: consider the polynomial $$l_i(x) = \prod_{j\neq i} \frac{x - x_j}{x_i - x_j} $$ with $l_i(x_i) = 1$ and $l_i(x_j) = 0$ whenever $j \neq i$. Define $p(x) $ to be $$p(x) = \sum_{i=0}^{n} y_i l_i(x) $$ $p(x) $ has degree at most $n $ because so do the $l_i(x) $ and $p(x_k) = \sum_i y_i l_i(x_k) = y_k $. In a future post I will show the uniqueness of the polynomial satisfying the constraints in the claim. Neste post vou mostrar a existência de uma família interessante de polinómios, muito útil em interpolação. Para isso vou usar uns polinómios chamados polinómios de Lagrange. Proposição: d...
Post a Comment
Read more

Twitter proof: can't touch this (exponential)

Pt En In this twitter proof we will see that no polynomial grows faster than the exponential function. Claim: the ratio $\frac{x^p}{e^x}$ tends to $0$ as $x $ tends to infinity. Twitter proof: recall that by the Taylor expansion of $e^x $ we have $$e^x = \sum_{i=0}^\infty \frac{x^i}{i!}$$ and for $x > 0$ we have $$\frac{x^p}{e^x} \leq \frac{x^p}{\sum_{i=0}^{p+1} a_ix^i} \to 0 $$ where $a_{p+1} \neq 0$ thus proving our claim. The way I like to look at this is "if the exponential has a bit of every polynomial inside, then it will grow faster than any fixed polynomial $p(x)$" (because, in particular, the exponential "has a bit" of all other polynomials that have degree higher than that of $p(x) $. Neste post vamos ver que a função exponencial cresce mais depressa que qualquer função polinomial. Proposição: o rácio $\frac{x^p}{e^x}$ tende para $0$ quando $x $ tende para infinito. Prova num tweet: sabemos pela expansão de Taylor de $e^x $ que $$e^x = \sum...
Post a Comment
Read more

Twitter proof: irrational high-order roots of 2

Pt En For this twitter proof we will be using a piece of mathematics straight from the 17th century. Claim: the number $\sqrt[n]{2} $ is irrational for $n \geq 3$. Twitter proof: suppose that $n \geq 3$ and $\sqrt[n]{2}$ is rational, i.e. $\sqrt[n]{2} = \frac{a}{b}$ for some integers $a, b $. Then taking the $n $-th power of both sides we get $2 = \frac{a^n}{b^n} \iff b^n + b^n = a^n $, contradicting the well-known Fermat's Last Theorem . Para esta prova num tweet vamos usar um pedaço de matemática do século 17. Proposição: o número $\sqrt[n]{2} $ é irracional para $n \geq 3$. Prova num tweet: suponhamos que $n\geq 3$ e que $\sqrt[n]{2} $ é racional, i.e. $\sqrt[n]{2} = \frac{a}{b} $ para alguns inteiros $a, b $. Se for esse o caso, elevando os dois lados da igualdade a $n $, obtemos $2 = \frac{a^n}{b^n} \iff b^n + b^n = a^n $, contrariando o famoso Último Teorema de Fermat . &nbsp&nbsp- RGS join the mathspp mailing list
Post a Comment
Read more

Twitter proof: the sum of inverses diverges

Pt En In this post I will share with you my favourite proof that the series of the inverses diverges: $\sum_{i=1}^\infty \frac1i = \infty $. Claim : the series $\sum_i \frac1i$ diverges. Twitter proof : consider the series $$ \begin{align} &\frac12 + \frac12 + \frac12 + \cdots = \\ &\frac12 + 2 \times\frac14 + 4\times \frac18 + \cdots = \\ &\frac12 + \frac14 + \frac14 + \frac18 + \cdots \leq \\ &\frac12 + \frac13 + \frac14 + \frac15 + \cdots \end{align}$$ that clearly diverges because it is a series of a constant nonzero term. By the comparison test, the series of the inverses also diverges. Comment with your favourite way to prove this fact!! Neste post quero partilhar com todos a minha prova preferida de que a série dos inversos dos naturais diverge: $\sum_{i=1}^\infty \frac1i = \infty $. Proposição : a série $\sum_i \frac1i$ diverge. Prova num tweet : considere-se a série$$ \begin{align} &\frac12 + \frac12 + \frac12 + \cdots = \\ &\frac12 + 2 \times\fr...
Post a Comment
Read more

Twitter proof: the Tower of Hanoi

Image
Pt En In this post we prove what the minimum number of moves to solve the problem of the Tower of Hanoi is! Claim: let $T(n)$ denote the number of moves it takes to solve the Tower of Hanoi with $n$ disks; then $T(n) = 2^{n}-1$. Twitter proof: note that to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ disks to the top of the bigger disk. Each time we move the top $n-1$ disks to another pole we must take, at least, $T(n-1)$ moves (by definition of $T$) hence we clearly have $T(n) = 2T(n-1) + 1$. Just notice that $B(n) = 2^n - 1$ satisfies the recurrence relation and that $T(0) = B(0) = 0$. If you are having trouble understanding what I mean by to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ dis...
Post a Comment
Read more