Республиканская олимпиада по математике, 2003 год, 10 класс

Заданы две последовательности $\{a_n\}$ и $\{b_n\}$ по следующему правилу: $$a_0 = b_0 = 0, ~a_n = a_{n-1}^2 +3, ~b_n=b_{n-1}^2 +2^n.$$ Что больше $a_{2003}$ или $b_{2003}$?

Комментарий/решение

$Ответ:a_{2003}$

Докажем по индукции что $a_{n}>b_{n}+2^n$ для $n>2$. Очевидно что База при $n=3$ верна. Пусть верно для $n=k$, тогда $a_{k}>b_{k}+2^k$. Тогда $a_{k+1}=a_{k}^2+3>b_{k}^2+2^{k+1}b_{k}+2^{2k}+3>b_{k}^2+2^k+2^{k+1}=b_{k+1}+2^{k+1}$, что и требовалось доказать.