Witajcie, mam taki problem z zadaniem, nad którym siedzę już kilka godzin i rozważałem różne metody, ale nie za bardzo wiem jak to ruszyć.
Otóż mam rekurencję daną wzorem
\(\displaystyle{ \left\{\begin{array}{l} K_{0} = 1 \\ K_{n+1} = 1 + min(2K_{\left \lfloor n/2 \right \rfloor}, 3K_{\left \lfloor n/3 \right \rfloor}) \end{array}}\)
dla \(\displaystyle{ n\geq0}\)
Wykazać mam, że \(\displaystyle{ K_{n} \geq n}\).
Jakieś pomysły? Wydaje mi się, że trzeba to jakoś ograniczyć, tylko nie mam pomysłu czym.
Wykazać nierówność dla ciągu rekurencyjnego
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Wykazać nierówność dla ciągu rekurencyjnego
Proponowałbym wzmocnić tezę do \(\displaystyle{ K_n\ge n+1}\) i udowadniać to indukcyjnie - oczywiście zakładając w drugim kroku, że teza jest prawdziwa dla wszystkich \(\displaystyle{ k\le n}\) i pokazując, że w takim razie jest też prawdziwa dla \(\displaystyle{ n+1}\).
Po drodze przydadzą się łatwe do wykazania nierówności:
\(\displaystyle{ \left \lfloor \frac n2 \right \rfloor}\ge \frac n2 - \frac 12}\)
i
\(\displaystyle{ \left \lfloor \frac n3 \right \rfloor}\ge \frac n3 - \frac 23}\)
Q.
Po drodze przydadzą się łatwe do wykazania nierówności:
\(\displaystyle{ \left \lfloor \frac n2 \right \rfloor}\ge \frac n2 - \frac 12}\)
i
\(\displaystyle{ \left \lfloor \frac n3 \right \rfloor}\ge \frac n3 - \frac 23}\)
Q.