Matematyka.pl

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.

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.