Twierdzenie matematyczne

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

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}}$