User:LebesgueStieltjes/proofs

Proof of Pithagoras's Theorem using differential equation

The statement of the theorem is well-konwn: Given a right triangle with legs $a,b$ and hypotenuse $c$, the following equality holds

Failed to parse (unknown function "\LARGE"): {\displaystyle \LARGE a^2+b^2=c^2}

Right triangle modified

As seen on the figure, if $da$ is sufficiently small, the triangle $AA'D$ can be considered as a right-angled triangle, similar to the original triangle with the following correspondence:
Failed to parse (unknown function "\LARGE"): {\displaystyle \LARGE\frac{a}{c}=\frac{dc}{da}}
This leads to the integral formula as follows:
Failed to parse (unknown function "\Large"): {\displaystyle \Large \int a\text{ } \mathrm{d}a = \int c\text{ } \mathrm{d}c }
The solution gives us the $a^{2}+C=c^{2}$ equation. The value of the constant $C$ is determined by the initial value problem, because if $a=0$, then $c=b$. This leads us to the desired result $a^{2}+b^{2}=c^{2}$

Can computers answer any question?

One might ask: if I can describe a problem or ask a question (yes/no for the sake of simplicity) in a well-defined language, is there always an algorithm which answers it correctly? Formally, given an alphabet, a language ${\cal {L}}$ is a set of words, each word consisting of letters of that alphabet. We say, that a language is decidable if for an arbitrary word there is an algorithm, that decides whether the word is in ${\cal {L}}$ or not. Is there such an algorithm for every language?
Assume, that every algorithm is a word of the given alphabet - for example if the alphabet is binary, we know that every algorithm can be translated into ones and zeros. An algorithm works as follows: it gets a word as input and answers with yes or no or runs forever - think of endless loops. Now fix a special language ${\cal {D}}$. $d\in {\cal {D}}$ If and only if $d$ is a code of an algorithm and if we give $d$ as an input for that algorithm - remember, $d$ is also a word - then the answer is no.
Now assume, that the algorithm, that decides if $d\in {\cal {D}}$ for every word, exists. By the existence of that algorithm we also mean, that it is also a word - denoted by $W$ - , as every algorithm is. If $W\in {\cal {D}}$, then the answer for $W$ is yes, but it also means, that the algorithm $W$ answers no for the input $W$. Likewise, if the answer is no, i.e. $W\notin {\cal {D}}$, then $W$ should be accepted by itself which leads to contradiction in both cases, so we found a question with no algorithm deciding it.

Explicit formula for the Fibonacci numbers

The Fibonacci-series is defined by a recursion: $F_{n}=F_{n-1}+F_{n-2}$ and $F_{0}=0$, $F_{1}=1$. Of course, we can easily calculate the first few element, but there is an exact formula, that calculates $F_{n}$ without knowing the previous ones.
First of all, we calculate the generator function: $f(x)=\sum \limits _{k=0}^{\infty }F_{n}x^{n}$. Using the definition of $F_{n}$ we obtain, that $f(x)=x+\sum \limits _{k=2}^{\infty }F_{n-1}x^{n}+F_{n-2}x^{n}=x+x\sum \limits _{k=0}^{\infty }F_{n}x^{n}+x^{2}\sum \limits _{k=0}^{\infty }F_{n}x^{n}=x+xf(x)+x^{2}f(x)$, thus $f(x)={\frac {x}{1-x-x^{2}}}$. Factoring the denominator we get Failed to parse (unknown function "\LARGE"): {\displaystyle \LARGE f(x)=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\frac{2x}{\sqrt{5} - 1}}-\frac{1}{1-\frac{2x}{\sqrt{5}+1}}\right)}

Thus the generator function is the sum of two geometric series: $f(x)={\frac {1}{\sqrt {5}}}\left(\sum \limits _{k=0}^{\infty }\left({\frac {2x}{{\sqrt {5}}-1}}\right)^{n}-\left({\frac {-2x}{{\sqrt {5}}+1}}\right)^{n}\right)={\frac {1}{\sqrt {5}}}\left(\sum \limits _{k=0}^{\infty }x^{n}\left(\left({\frac {2}{{\sqrt {5}}-1}}\right)^{n}-\left({\frac {-2}{{\sqrt {5}}+1}}\right)^{n}\right)\right)=\sum \limits _{k=0}^{\infty }F_{n}x^{n}$
Comparing the coefficient of $x^{n}$ leads to $F_{n}={\frac {1}{\sqrt {5}}}\left(\left({\frac {2}{{\sqrt {5}}-1}}\right)^{n}-\left({\frac {-2}{{\sqrt {5}}+1}}\right)^{n}\right)$