Twierdzenie matematyczne

Szablon:Tbeł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

• 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

Niech n będzie potęgą liczby rzeczywistej b, takiej, że $b>1$, 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:

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

to

$\!T(n)\ =\ \Theta (n^{log_{b}a})\ +\ \sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f({\frac {n}{b^{j}}})$

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:

• $\!T(n)\ =\ \Theta (n^{log_{b}a})\ +\ O(n^{log_{b}a})\ =\ \Theta (n^{log_{b}a})$

• $\!T(n)=\Theta (n^{log_{b}a})+\Theta (n^{log_{b}a}\cdot \ln \ n)=\Theta (n^{log_{b}a}\cdot \ln \ n)$

• $\!T(n)=\Theta (n^{log_{b}a})+\Theta (f(n))=\Theta (f(n))$, ponieważ $\!f(n)=\Omega (n^{log_{b}a+\epsilon })$

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

Odpowiednio górne i dolne oszacowanie dla funkcji

$\!T(n)=a\cdot T(\left\lfloor {\frac {n}{b}}\right\rfloor )\ +\ f(n)$ (1)

i

$\!T(n)=a\cdot T(\left\lceil {\frac {n}{b}}\right\rceil )\ +\ f(n)$ (2)

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

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

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

Wtedy schodzenie w dół rekursji oznacza jej rekurencyjne wywoływanie kolejno dla argumentów $\!n[0],\ n[1],\ n[2],\ \cdots$

$\!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$

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

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

Dla $i=\left\lfloor \log _{b}n\right\rfloor$

$\!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)$

Oznacza to, że dla wywołań rekursji na poziomie co najmniej $n[\left\lfloor \log _{b}n\right\rfloor ]$ i większych rozmiar problemu jest stały.

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