Parzysta suma
-
mol_ksiazkowy
- Użytkownik
- Posty: 11361
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Parzysta suma
Udowodnić, że suma \(\displaystyle{ \lfloor \frac{n}{1} \rfloor + ...+ \lfloor \frac{n}{n} \rfloor + \lfloor \sqrt{n} \rfloor }\) jest parzystą dla \(\displaystyle{ n=1, 2, 3, ...}\)
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Parzysta suma
Można obliczyć, że dla jakiejś małej liczby, np. \(\displaystyle{ n=3}\) ta suma rzeczywiście wychodzi parzysta (jeśli chcemy, to możemy zacząć i od jedynki, nic to nie zmienia, pozostawiam tę bazę indukcji jako ćwiczenie).
Dalej rozumujemy indukcyjnie, rozważając parzystość wyrażenia
\(\displaystyle{ \sum_{k=1}^{n+1}\left(\left\lfloor \frac{n+1}{k}\right\rfloor -\left\lfloor \frac{n}{k}\right\rfloor\right)+\lfloor \sqrt{n+1}\rfloor -\lfloor \sqrt{n}\rfloor}\)
(tak możemy zapisać różnicę dwóch kolejnych wyrazów ciągu, gdyż oczywiście \(\displaystyle{ \left\lfloor \frac{n}{n+1}\right\rfloor=0}\), więc dopisanie takiego wyrazu nic nie zmienia).
Uwaga nr 1: wyrażenie \(\displaystyle{ \lfloor\sqrt{n+1}\rfloor -\lfloor \sqrt{n}\rfloor}\) przyjmuje tylko dwie możliwe wartości, zero, gdy \(\displaystyle{ n+1}\) nie jest kwadratem liczby naturalnej i jeden, gdy \(\displaystyle{ n+1}\) jest kwadratem liczby naturalnej.
Uwaga nr 2: wyrażenie \(\displaystyle{ \left\lfloor \frac{n+1}{k}\right\rfloor -\left\lfloor\frac{n}{k}\right\rfloor}\) też przyjmuje tylko dwie możliwe wartości, a mianowicie zero, gdy \(\displaystyle{ k}\) nie jest dzielnikiem liczby \(\displaystyle{ n+1}\) i jeden, gdy \(\displaystyle{ k}\) dzieli \(\displaystyle{ n+1}\).
Oczywiście wśród liczb \(\displaystyle{ \left\{1,2,\ldots n+1\right\}}\) są wszystkie dzielniki całkowite dodatnie liczby \(\displaystyle{ n+1}\), a jeśli
\(\displaystyle{ n+1}\) jest postaci \(\displaystyle{ \prod_{i=1}^{j}p_{i}^{\alpha_{i}}}\), to ma \(\displaystyle{ \prod_{i=1}^{j}(\alpha_{i}+1)}\) dzielników całkowitych dodatnich. To oznacza, że w tej sumie
\(\displaystyle{ \sum_{k=1}^{n+1}\left(\left\lfloor \frac{n+1}{k}\right\rfloor -\left\lfloor \frac{n}{k}\right\rfloor\right)}\) mamy
\(\displaystyle{ \prod_{i=1}^{j}(\alpha_{i}+1)}\) jedynek i \(\displaystyle{ n+1-\prod_{i=1}^{j}(\alpha_{i}+1)}\) zer.
Liczba \(\displaystyle{ \prod_{i=1}^{j}(\alpha_{i}+1)}\) jest nieparzysta dokładnie wtedy, gdy każdy dzielnik pierwszy liczby \(\displaystyle{ n+1}\) występuje w rozkładzie \(\displaystyle{ n+1}\) na czynniki pierwsze w parzystej potędze, czyli gdy \(\displaystyle{ n+1}\) jest kwadratem liczby naturalnej.
Zatem gdy \(\displaystyle{ n+1}\) jest kwadratem liczby naturalnej, to w kroku indukcyjnym dodajemy do parzystej z założenia sumy dla \(\displaystyle{ n}\) nieparzystą liczbę \(\displaystyle{ \sum_{k=1}^{n+1}\left(\left\lfloor \frac{n+1}{k}\right\rfloor -\left\lfloor \frac{n}{k}\right\rfloor\right)}\) powiększoną o \(\displaystyle{ 1}\), czyli liczbę parzystą, a suma dwóch liczb parzystych jest parzysta.
Natomiast gdy \(\displaystyle{ n+1}\) nie jest kwadratem liczby naturalnej, to w kroku indukcyjnym do sumy dla \(\displaystyle{ n}\), która z założenia indukcyjnego jest parzysta, dodajemy parzystą sumę (gdyż pewne \(\displaystyle{ \alpha_{i}}\) jest nieparzyste, a wówczas \(\displaystyle{ \alpha_{i}+1}\) jest parzyste) „powiększoną" o \(\displaystyle{ \lfloor \sqrt{n+1}\rfloor-\lfloor \sqrt{n}\rfloor=0}\), czyli liczbę parzystą, i znów korzystamy z tego, że suma dwóch liczb parzystych jest parzysta.
To kończy krok indukcyjny.
Dalej rozumujemy indukcyjnie, rozważając parzystość wyrażenia
\(\displaystyle{ \sum_{k=1}^{n+1}\left(\left\lfloor \frac{n+1}{k}\right\rfloor -\left\lfloor \frac{n}{k}\right\rfloor\right)+\lfloor \sqrt{n+1}\rfloor -\lfloor \sqrt{n}\rfloor}\)
(tak możemy zapisać różnicę dwóch kolejnych wyrazów ciągu, gdyż oczywiście \(\displaystyle{ \left\lfloor \frac{n}{n+1}\right\rfloor=0}\), więc dopisanie takiego wyrazu nic nie zmienia).
Uwaga nr 1: wyrażenie \(\displaystyle{ \lfloor\sqrt{n+1}\rfloor -\lfloor \sqrt{n}\rfloor}\) przyjmuje tylko dwie możliwe wartości, zero, gdy \(\displaystyle{ n+1}\) nie jest kwadratem liczby naturalnej i jeden, gdy \(\displaystyle{ n+1}\) jest kwadratem liczby naturalnej.
Uwaga nr 2: wyrażenie \(\displaystyle{ \left\lfloor \frac{n+1}{k}\right\rfloor -\left\lfloor\frac{n}{k}\right\rfloor}\) też przyjmuje tylko dwie możliwe wartości, a mianowicie zero, gdy \(\displaystyle{ k}\) nie jest dzielnikiem liczby \(\displaystyle{ n+1}\) i jeden, gdy \(\displaystyle{ k}\) dzieli \(\displaystyle{ n+1}\).
Oczywiście wśród liczb \(\displaystyle{ \left\{1,2,\ldots n+1\right\}}\) są wszystkie dzielniki całkowite dodatnie liczby \(\displaystyle{ n+1}\), a jeśli
\(\displaystyle{ n+1}\) jest postaci \(\displaystyle{ \prod_{i=1}^{j}p_{i}^{\alpha_{i}}}\), to ma \(\displaystyle{ \prod_{i=1}^{j}(\alpha_{i}+1)}\) dzielników całkowitych dodatnich. To oznacza, że w tej sumie
\(\displaystyle{ \sum_{k=1}^{n+1}\left(\left\lfloor \frac{n+1}{k}\right\rfloor -\left\lfloor \frac{n}{k}\right\rfloor\right)}\) mamy
\(\displaystyle{ \prod_{i=1}^{j}(\alpha_{i}+1)}\) jedynek i \(\displaystyle{ n+1-\prod_{i=1}^{j}(\alpha_{i}+1)}\) zer.
Liczba \(\displaystyle{ \prod_{i=1}^{j}(\alpha_{i}+1)}\) jest nieparzysta dokładnie wtedy, gdy każdy dzielnik pierwszy liczby \(\displaystyle{ n+1}\) występuje w rozkładzie \(\displaystyle{ n+1}\) na czynniki pierwsze w parzystej potędze, czyli gdy \(\displaystyle{ n+1}\) jest kwadratem liczby naturalnej.
Zatem gdy \(\displaystyle{ n+1}\) jest kwadratem liczby naturalnej, to w kroku indukcyjnym dodajemy do parzystej z założenia sumy dla \(\displaystyle{ n}\) nieparzystą liczbę \(\displaystyle{ \sum_{k=1}^{n+1}\left(\left\lfloor \frac{n+1}{k}\right\rfloor -\left\lfloor \frac{n}{k}\right\rfloor\right)}\) powiększoną o \(\displaystyle{ 1}\), czyli liczbę parzystą, a suma dwóch liczb parzystych jest parzysta.
Natomiast gdy \(\displaystyle{ n+1}\) nie jest kwadratem liczby naturalnej, to w kroku indukcyjnym do sumy dla \(\displaystyle{ n}\), która z założenia indukcyjnego jest parzysta, dodajemy parzystą sumę (gdyż pewne \(\displaystyle{ \alpha_{i}}\) jest nieparzyste, a wówczas \(\displaystyle{ \alpha_{i}+1}\) jest parzyste) „powiększoną" o \(\displaystyle{ \lfloor \sqrt{n+1}\rfloor-\lfloor \sqrt{n}\rfloor=0}\), czyli liczbę parzystą, i znów korzystamy z tego, że suma dwóch liczb parzystych jest parzysta.
To kończy krok indukcyjny.