Twierdzenie matematyczne – bełkot pseudonaukowy osadzony w świecie matematyki, tzw. „królowej nauk bezużytecznych”. Zdanie składające się w 60% procentach ze słów absolutnie niezrozumiałych i nieznanych dla zwykłych ludzi, w 35% z dziwnych znaczków, których próżny trud szukać na klawiaturze oraz w 5% z zaimków.
Cele tworzenia twierdzeń matematycznych[edytuj • edytuj kod]
- Pobieranie grantów naukowych.
- Budowanie podstaw dla tworzenia bardziej zaawansowanych twierdzeń, tak by koledzy z wydziału też mogli pobierać granty.
- Uwalanie studentów.
- Pisanie nikomu niepotrzebnych prac naukowych.
- Organizowanie konferencji naukowych, których jedynym prawdziwym celem jest uczestniczenie wygłaszających prelekcje w bankietach ze szwedzkim stołem i darmową wódą.
Przykład twierdzenia matematycznego[edytuj • edytuj kod]
Niech n będzie potęgą liczby rzeczywistej b, takiej, że
, a f niech będzie bijekcją na zbiór półpełny liczb zespolonych odwrotnie przekształconych. Jeśli dla pewnej dodatniej liczby całkowitej i funkcja T jest zdefiniowana następująco:
![{\displaystyle T(n)=\left\{{\begin{matrix}\ \Theta (1)&:n\ =\ 1\\\ a\cdot T({\frac {n}{b}})+f(n)&:n\ =\ b^{i}\end{matrix}}\right.}](https://nonsa.pl/api/rest_v1/media/math/render/svg/58a6299d61df30d5e8fc6e679d22a2b6a9da81cd)
to
![{\displaystyle \!T(n)\ =\ \Theta (n^{log_{b}a})\ +\ \sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f({\frac {n}{b^{j}}})}](https://nonsa.pl/api/rest_v1/media/math/render/svg/0a16b8de604012cd150183b7661e46f8e928ad74)
Nic z tego nie rozumiesz? Spokojnie, zobacz jak wygląda dowód prawdziwości tego ustrojstwa:
Korzystając z oszacowania z lematu Pitagorasa dla sumy interpolowanych wielomianów sacharozy pokażemy, że dla kolejnych przypadków zachodzi:
![{\displaystyle \!T(n)\ =\ \Theta (n^{log_{b}a})\ +\ O(n^{log_{b}a})\ =\ \Theta (n^{log_{b}a})}](https://nonsa.pl/api/rest_v1/media/math/render/svg/6f7ea19eb846f2a1fe19403e9285a7fb3994d281)
![{\displaystyle \!T(n)=\Theta (n^{log_{b}a})+\Theta (n^{log_{b}a}\cdot \ln \ n)=\Theta (n^{log_{b}a}\cdot \ln \ n)}](https://nonsa.pl/api/rest_v1/media/math/render/svg/cf46d761de4e6b6eacfa11481808de657c9436eb)
, ponieważ ![{\displaystyle \!f(n)=\Omega (n^{log_{b}a+\epsilon })}](https://nonsa.pl/api/rest_v1/media/math/render/svg/f27b81e64d9f85b4459e77c625d4fcdea36b4524)
Oczywistym i jakże widocznym jest fakt, że dla dowolnych n (nie będących potęga b) wartość argumentu
może oznaczać
lub
.
Odpowiednio górne i dolne oszacowanie dla funkcji
(1)
i
(2)
jest banalne arcybanalne do znalezienia, przy wykorzystaniu własności
i
Równanie rekurencyjne można oszacować z góry w następujący sposób, tak prosty i oczywisty, że nawet czytający ten dowód czterolatkowie wiedzą jak:
Niech
Wtedy schodzenie w dół rekursji oznacza jej rekurencyjne wywoływanie kolejno dla argumentów
![{\displaystyle \!T(n)=T(\left\lceil {\frac {n}{b}}\right\rceil )=\ T(\left\lceil {\frac {\left\lceil {\frac {n}{b}}\right\rceil }{b}}\right\rceil )=\cdots }](https://nonsa.pl/api/rest_v1/media/math/render/svg/941017740080dace11c0682218160c65b020c1dc)
Korzystając z nierówności
mamy:
![{\displaystyle n[0]\leqslant n}](https://nonsa.pl/api/rest_v1/media/math/render/svg/5bea25418a40f9465d67870b3c1619d49c585492)
![{\displaystyle n[1]\leqslant {\frac {n}{b}}+1}](https://nonsa.pl/api/rest_v1/media/math/render/svg/fc2e4a998fa9390c92bedacbaf8456d656800fe0)
![{\displaystyle n[2]\leqslant {\frac {n}{b^{2}}}+{\frac {1}{b}}+1}](https://nonsa.pl/api/rest_v1/media/math/render/svg/f0cc2612d0eca61a05962ba93171945987e0bddb)
![{\displaystyle n[3]\leqslant {\frac {n}{b^{3}}}+{\frac {1}{b^{2}}}+{\frac {1}{b}}+1}](https://nonsa.pl/api/rest_v1/media/math/render/svg/51c6b874b50bd88a7a19163fbb9c4d7695b6b008)
![{\displaystyle \cdots }](https://nonsa.pl/api/rest_v1/media/math/render/svg/e1d67495288eac0fa90d5bbcad7d9a343c15ad56)
![{\displaystyle n[i]\leqslant {\frac {n}{b^{i}}}+\sum _{k=0}^{i-1}{\frac {1}{b^{k}}}<{\frac {n}{b^{i}}}+\sum _{k=0}^{\infty }{\frac {1}{b^{k}}}={\frac {n}{b^{i}}}+{\frac {b}{b-1}}}](https://nonsa.pl/api/rest_v1/media/math/render/svg/4a6c54e914095d5403a50ebc8bc03c9c0782a89d)
Dla
![{\displaystyle \!n[i]=n[\left\lfloor \log _{b}n\right\rfloor ]<{\frac {n}{b^{\left\lfloor \log _{b}n\right\rfloor }}}+{\frac {b}{b-1}}\leqslant {\frac {n}{b^{\log _{b}n-1}}}+{\frac {b}{b-1}}={\frac {n}{\frac {n}{b}}}+{\frac {b}{b-1}}\in O(1)}](https://nonsa.pl/api/rest_v1/media/math/render/svg/8ba5f16debcc7a2595e7a22198008c8dd45374a2)
Oznacza to, że dla wywołań rekursji na poziomie co najmniej
i większych rozmiar problemu jest stały.
W ten oto sposób kończymy nasz jakże banalny dowód!