Dowód nierówności o ciągach jednomonotonicznych

Z Wikipedii

Poniżej umieszczony jest dowód nierówności o ciągach jednomonotonicznych.

Dowód ten oparty jest na zasadzie indukcji matematycznej.

[edytuj] Lewa strona

Twierdzenie jest niewątpliwie prawdziwe dla n=1, ponieważ jest tylko jedna permutacja ciągu jednoelementowego, wobec czego:

$b_1=b'_1\Leftrightarrow a_1b_1=a_1b'_1\Rightarrow a_1b_1 \geq a_1b'_1$

Udowodnijmy zatem że dla dowolnego naturalnego n i dwóch ciągów rzeczywistych $(a_i)_{i\in {N_{\leq n+1}}}$ , $(b_i)_{i\in {N_{\leq n+1}}}$ spełniających założenia prawdziwym jest, że jeśli zachodzi:

$a_1b_1+...+a_nb_n~\geq~a_1b'_1+a_2b'_2+...+a_nb'_n~\geq~a_1b_n+a_2b_{n-1}+...+a_nb_1$

to zachodzi również:

$a_1b_1+...+a_nb_n+a_{n+1}+b_{n+1}~\geq~a_1b''_1+a_2b''_2+...+a_nb''_n+a_{n+1}+b''_{n+1}$

(gdzie $(b'_i)_{i\in {N_{\leq n}}}$ jest permutacją $(b_i)_{i\in {N_{\leq n}}}$ , a $(b''_i)_{i\in {N_{\leq n+1}}}$ permutacją $(b_i)_{i\in {N_{\leq n+1}}}$ )

Dla $b'' n + 1 = b n + 1$ jest to oczywiste, ponieważ można ją uzyskać poprzez obustronne dodanie wyrażenia $a n + 1 b n + 1$ w tezie indukcyjnej.

W przeciwnym wypadku istnieją takie naturalne i i j nie większe niż n, że dla pewnych permutacji:

a 1 b' 1 + ... + a n b' n + a n + 1 b n + 1 = a 1 b'' 1 + ... + a n b'' n + a n + 1 b'' n + 1 - (a i b n + 1 + a n + 1 b j) + (a i b j + a n + 1 b n + 1)

a zgodnie z założeniami

$a_i\geq a_{n+1}$

$b'_i=b_j\geq b_{n+1}$

więc:

$(a_i-a_{n+1})(b_j-b_{n+1})=-(a_ib_{n+1}+a_{n+1}b_j)+(a_ib_j+a_{n+1}b_{n+1})\geq 0$

z czego

$a_1b'_1+...+a_nb'_n+a_{n+1}b_{n+1}\geq a_1b''_1+...+a_nb''_n+a_{n+1}b''_{n+1}$

więc oczywiście

$a_1b_1+...+a_nb_n+a_{n+1}b_{n+1}\geq a_1b''_1+...+a_nb''_n+a_{n+1}b''_{n+1}$

Co kończy dowód, ponieważ dla każdej permutacji $''$ możemy znaleźć odpowiednią permutację $'$ , która będzie się od niej różniła co najwyżej jednym elementem.

Kategoria: Dowody matematyczne

We provide Linux to the World

Dowód nierówności o ciągach jednomonotonicznych

Z Wikipedii

[edytuj] Lewa strona

Views

nawigacja

zmiany

dla edytorów

Szukaj