Edytujesz „Twierdzenie matematyczne”

'''Twierdzenie matematyczne''' – [[bełkot pseudonaukowy]] osadzony w świecie [[matematyka|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 [[klawiatura|klawiaturze]] oraz w 5% z [[zaimek|zaimków]].

== Cele tworzenia twierdzeń matematycznych ==
* 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 [[Szwedzki stół|szwedzkim stołem]] i [[open bar|darmową wódą]].

== Przykład twierdzenia matematycznego ==
Niech ''n'' będzie potęgą liczby rzeczywistej ''b'', takiej, że <math>b>1</math>, 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:

: <math>T(n)=\left\{ \begin{matrix} \ \Theta (1) &: n\ =\ 1 \\ \ a\cdot 
T(\frac{n}{b}) + f(n)&:n\ =\ b^i \end{matrix} \right.</math>

to

: <math>\! T(n)\ =\ \Theta (n^{log_ba})\ +\ \sum_{j = 0}^{\log_bn-1} a^j\cdot f(\frac{n}{b^j})</math>

Nic z tego nie rozumiesz? Spokojnie, zobacz jak wygląda dowód prawdziwości tego ustrojstwa:

=== Dowód ===
Korzystając z oszacowania z lematu Pitagorasa dla sumy interpolowanych wielomianów sacharozy pokażemy, że dla kolejnych przypadków zachodzi:

* <math>\! T(n)\ =\ \Theta (n^{log_ba})\ +\ O(n^{log_ba})\ =\ \Theta(n^{log_ba})</math>

* <math>\! T(n) = \Theta (n^{log_ba}) + \Theta(n^{log_ba}\cdot \ln\ n) = \Theta(n^{log_ba}\cdot \ln\ n)</math>

* <math>\! T(n) = \Theta (n^{log_ba}) + \Theta(f(n)) = \Theta(f(n))</math>, ponieważ <math>\! f(n) = \Omega (n^{log_ba + \epsilon})</math>

Oczywistym i jakże widocznym jest fakt, że dla dowolnych ''n'' (nie będących potęga ''b'') wartość argumentu <math>\! \frac{n}{b} </math> może oznaczać <math>\left\lfloor \frac{n}{b} \right\rfloor</math> lub <math>\left\lceil\frac{n}{b} \right\rceil</math>.

Odpowiednio górne i dolne oszacowanie dla funkcji

:: <math>\! T(n) = a\cdot T(\left\lfloor \frac{n}{b} \right\rfloor )\ +\ f(n)</math>   (1)

i

:: <math>\! T(n) = a\cdot T(\left\lceil \frac{n}{b} \right\rceil )\ +\ f(n)</math>    (2)

jest <del>banalne</del> arcybanalne do znalezienia, przy wykorzystaniu własności <math>\! \left\lfloor \frac{n}{b} \right\rfloor \geqslant \frac{n}{b}</math>  i  <math>\! \left\lceil \frac{n}{b} \right\rceil \leqslant \frac{n}{b}</math>

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 [[Przedszkole|czterolatkowie]] wiedzą jak:

Niech 

<math>n[i]=\left\{ \begin{matrix} \ n &: i=0\\ 
\  \left\lceil \frac{n[i-1]}{b}  \right\rceil &:i>0 \end{matrix} \right.</math>

Wtedy schodzenie w dół [[Rekurencja|rekursji]] oznacza jej rekurencyjne wywoływanie kolejno dla argumentów <math>\! n[0],\ n[1],\ n[2],\ \cdots</math>

:: <math>\! 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 </math>

Korzystając z nierówności <math>\left\lceil a \right\rceil \leqslant a\ +\ 1</math> mamy:

* <math>n[0] \leqslant n</math>
* <math>n[1] \leqslant \frac{n}{b} + 1</math>
* <math>n[2] \leqslant \frac{n}{b^2} + \frac{1}{b} + 1</math>
* <math>n[3] \leqslant \frac{n}{b^3} + \frac{1}{b^2} + \frac{1}{b} + 1</math>
* <math>\cdots </math>
* <math>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}</math> 

Dla <math>i = \left\lfloor \log _bn \right\rfloor</math>

: <math>\! n[i] = n[\left\lfloor \log _bn \right\rfloor ] < \frac{n}{b^{\left\lfloor \log _bn \right\rfloor}} + \frac{b}{b-1} \leqslant \frac{n}{b^{\log _bn -1}} + \frac{b}{b-1} = \frac{n}{\frac{n}{b}} + \frac{b}{b-1} \in O(1)</math> 

Oznacza to, że dla wywołań rekursji na poziomie co najmniej <math>n[\left\lfloor \log _bn \right\rfloor ]</math> i większych rozmiar problemu jest stały.

W ten oto sposób kończymy nasz jakże banalny dowód!

== Zobacz też ==
* [[Metody dowodzenia twierdzeń]]
* [[Twierdzenie Mefja]]
* [[Twierdzenie o nieskończonej liczbie małp]]
* [[Twierdzenie o równouprawnieniu]]

{{Matematyka}}

[[Kategoria:Matematyka]]