Олимпиадные задачи из источника «параграф 2. Рекуррентные последовательности»
параграф 2. Рекуррентные последовательности
НазадПусть(1 +$\sqrt{2}$+$\sqrt{3}$)<sup>n</sup>=<i>p</i><sub>n</sub>+<i>q</i><sub>n</sub>$\sqrt{2}$+<i>r</i><sub>n</sub>$\sqrt{3}$+<i>s</i><sub>n</sub>$\sqrt{6}$(<i>n</i>$\geqslant$0). Найдите: а) $\lim\limits_{n\to \infty}^{}$${\dfrac{p_n}{q_n}}$; б) $\lim\limits_{n\to \infty}^{}$${\dfrac{p_n}{r_n}}$; в) $\lim\limits_{n\to \infty}^{}$${\dfrac{p_n}{s_n}}$.
Каким линейным рекуррентным соотношениям удовлетворяют последовательности a) <i>a</i><sub>n</sub>=<i>n</i><sup>2</sup>; б) <i>a</i><sub>n</sub>=<i>n</i><sup>3</sup>?
Найдите формулу<i>n</i>-го члена для последовательностей, заданных условиями (<i>n</i>$\geqslant$0): <table> <tr><td align="LEFT">a) <i>a</i><sub>0</sub> = 0, <i>a</i><sub>1</sub> = 1, <i>a</i><sub>n + 2</sub> = 4<i>a</i><sub>n + 1</sub> - 5<i>a</i><sub>n</sub>;</td> </tr> <tr><td align="LEFT"> б) <i>a</i><sub>0</sub> = 1, <i>a</i><sub>1</sub> = 2, <i>a</i><sub>n + 2</sub> = 2<i>a</i><sub>n + 1</sub> - 2<i>a</i><sub>n</sub>;</td> </tr> <tr><td align...
Пусть характеристическое уравнение (<a href="https://problems.ru/view_problem_details_new.php?id=">11.3</a>) последовательности (<a href="https://problems.ru/view_problem_details_new.php?id=">11.2</a>) имеет комплексные корни<i>x</i><sub>1, 2</sub>=<i>a</i>±<i>ib</i>=<i>re</i><sup>±i$\scriptstyle \varphi$</sup>. Докажите, что для некоторой пары чисел<i>c</i><sub>1</sub>,<i>c</i><sub>2</sub>будет выполняться равенство<div align="CENTER"> <i>a</i><sub>n</sub> = <i>r</i><sup>n</sup>(<i>c</i><sub>1</sub>cos <i>n</i>$\displaystyle \var...
Как будет выглядеть формула <i>n</i>-го члена для рекуррентной последовательности <i>k</i>-го порядка, если
a) характеристическое уравнение имеет простые корни <i>x</i><sub>1</sub>,..., <i>x<sub>k</sub></i>, отличные от нуля;
б) характеристическое уравнение имеет отличные от нуля корни <i>x</i><sub>1</sub>, ..., <i>x<sub>m</sub></i> с кратностями α<sub>1</sub>, ..., α<i><sub>m</sub></i> соответственно?
Определения, связанные с рекуррентными последовательностями, смотри в <a href="https://problems.ru/thes.php?letter=15#linejnaja_recurrentnaja">справочнике</a>.
Пять моряков высадились на остров и к вечеру набрали кучу кокосовых орехов. Дележ отложили на утро. Один из них, проснувшись ночью, угостил одним орехом мартышку, а из остальных орехов взял себе точно пятую часть, после чего лёг спать и быстро уснул. За ночь так же поступили один за другим и остальные моряки; при этом каждый не знал о действиях предшественников. На утро они поделили оставшиеся орехи поровну, но для мартышки в этот раз лишнего ореха не осталось. Каким могло быть наименьшее число орехов в собранной куче?
Определим последовательности {<i>x</i><sub>n</sub>} и {<i>y</i><sub>n</sub>} при помощи условий:<div align="CENTER"> <i>x</i><sub>n</sub> = <i>x</i><sub>n - 1</sub> + 2<i>y</i><sub>n - 1</sub>sin<sup>2</sup>$\displaystyle \alpha$, <i>y</i><sub>n</sub> = <i>y</i><sub>n - 1</sub> + 2<i>x</i><sub>n - 1</sub>cos<sup>2</sup>$\displaystyle \alpha$; <i>x</i><sub>0</sub> = 0, <i>y</i><sub>0</sub> = cos$\displaystyle \alpha$. </div>Найдите выражение для<i>x</i><sub>n</sub>и<i>y</...
Докажите, что последовательность <i>a<sub>n</sub></i> = 1 + 17<i>n</i>² (<i>n</i> ≥ 0) содержит бесконечно много квадратов целых чисел.
Докажите, что при всех натуральных<i>n</i>выполняется сравнение[(1 +$\sqrt{2}$)<sup>n</sup>]$\equiv$<i>n</i>(mod 2).
Найдите у чисел а) (6 + <img width="33" height="36" align="MIDDLE" border="0" src="/storage/problem-media/61477/problem_61477_img_2.gif">)<sup>1999</sup>; б) (6 + <img width="33" height="36" align="MIDDLE" border="0" src="/storage/problem-media/61477/problem_61477_img_3.gif">)<sup>1999</sup>; в) (6 + <img width="33" height="36" align="MIDDLE" border="0" src="/storage/problem-media/61477/problem_61477_img_3.gif">)<sup>2000</sup> первые 1000 знаков после запятой.
Садовник, привив черенок редкого растения, оставляет его расти два года, а затем ежегодно берет от него по 6 черенков. С каждым новым черенком он поступает аналогично. Сколько будет растений и черенков на<i>n</i>-ом году роста первоначального растения?
Докажите, что для любого числа<i>p</i>> 2 найдется такое число$\beta$, что<div align="CENTER"> $\displaystyle \underbrace{\sqrt{2+\sqrt{2+\ldots+\sqrt{2+ \sqrt{2+p}}}}}{n~\mbox{\scriptsize {радикалов}}}^{},$ = $\displaystyle \beta^{2^n}{}$ - $\displaystyle \beta^{-2^n}_{}$. </div>
Лягушка прыгает по вершинам шестиугольника <i>ABCDEF</i>, каждый раз перемещаясь в одну из соседних вершин.
а) Сколькими способами она может попасть из <i>A</i> в <i>C</i> за <i>n</i> прыжков?
б) Тот же вопрос, но при условии, что ей нельзя прыгать в <i>D</i>?
<b>Лягушка-сапер</b>.
в) Пусть путь лягушки начинается в вершине <i>A</i>, а в вершине <i>D</i> находится мина. Каждую секунду она делает очередной прыжок. Какова вероятность того, что она еще будет жива через <i>n</i> секунд?
г)* Какова средняя продолжительность жизни таких лягушек?
Лягушка прыгает по вершинам треугольника <i>ABC</i>, перемещаясь каждый раз в одну из соседних вершин.
Сколькими способами она может попасть из <i>A</i> в <i>A</i> за <i>n</i> прыжков?
Укажите явный вид коэффициентов в многочленах <i>F<sub>n</sub></i>(<i>x</i>) и <i>L<sub>n</sub></i>(<i>x</i>). Решите задачи <a href="https://mirolimp.ru/tasks/160581">160581</a> и <a href="https://mirolimp.ru/tasks/160582">160582</a>, используя многочлены Фибоначчи.
Про многочлены Фибоначчи и Люка смотри <a href="https://problems.ru/thes.php?letter=12#fibonacci">статьи</a> в справочнике.
Докажите, что многочлены Фибоначчи и Люка связаны с многочленами Чебышёва равенствами
<i>U<sub>n</sub></i>(<sup><i>x</i></sup>/<sub>2</sub>) = <i>i<sup>–n</sup>F</i><sub><i>n</i>+1</sub>(<i>ix</i>); 2<i>T<sub>n</sub></i>(<sup><i>x</i></sup>/<sub>2</sub>) = <i>i<sup>–n</sup>L<sub>n</sub></i>(<i>ix</i>).
Про многочлены Фибоначчи, Люка и Чебышёва смотри в <a href="https://problems.ru/thes.php?letter=12#chebysheva">справочнике</a>.
Получите формулу для многочленов Фибоначчи и Люка, аналогичную формуле Бине (см. задачи <a href="https://mirolimp.ru/tasks/160578">160578</a> и <a href="https://mirolimp.ru/tasks/160587">160587</a>).
Определения многочленов Фибоначчи и Люка смотри <a href="https://problems.ru/thes.php?letter=12#fibonacci">здесь</a>.
Разложите функции <img align="middle" src="/storage/problem-media/61469/problem_61469_img_2.gif"> и <img align="middle" src="/storage/problem-media/61469/problem_61469_img_3.gif"> (<i>n</i> ≥ 1) в цепные дроби.
Определения многочленов Фибоначчи <i>F<sub>n</sub></i>(<i>x</i>) и Люка <i>L<sub>n</sub></i>(<i>x</i>) смотри, например, <a href="https://problems.ru/thes.php?letter=12#fibonacci">здесь</a>.
Вычислите несколько первых многочленов Фибоначчи и Люка (определения многочленов Фибоначчи и Люка смотри <a href="https://problems.ru/thes.php?letter=12#fibonacci">здесь</a>). Какие значения эти многочлены принимают при <i>x</i> = 1? Докажите, что многочлены Люка связаны с многочлены Фибоначчи соотношениями:
а) <i>L<sub>n</sub></i>(<i>x</i>) = <i>F</i><sub><i>n</i>–1</sub>(<i>x</i>) + <i>F</i><sub><i>n</i>+1</sub>(<i>x</i>) (<i>n</i> ≥ 1);
б) <i>F<sub>n</sub></i>(<i>x</i>)(<i>x</i>² + 4) = <i>L</i><sub><i>n</i>–1</sub>(...
Докажите, что произвольная последовательность<i>Q</i><sub>n</sub>, заданная условиями<div align="CENTER"> <i>Q</i><sub>0</sub> = $\displaystyle \alpha$, <i>Q</i><sub>1</sub> = $\displaystyle \beta$, <i>Q</i><sub>n + 2</sub> = <i>Q</i><sub>n + 1</sub> + <i>Q</i><sub>n</sub> (<i>n</i> $\displaystyle \geqslant$ 0), </div>может быть выражена через числа Фибоначчи<i>F</i><sub>n</sub>и числа Люка<i>L</i><sub>n</sub>(определение чисел Люка смотри в задаче<a href="https://mirolimp.ru/tasks/160585">3.133</a>).
Найдите все целочисленные решения уравнения <i>a</i>² – 3<i>b</i>² = 1.
Докажите, что уравнение (<i>x + y</i><img width="25" height="38" align="MIDDLE" border="0" src="/storage/problem-media/61465/problem_61465_img_2.gif">)<sup>4</sup> + (<i>z + t</i><img width="25" height="38" align="MIDDLE" border="0" src="/storage/problem-media/61465/problem_61465_img_2.gif">)<sup>4</sup> = 2 + <img width="25" height="38" align="MIDDLE" border="0" src="/storage/problem-media/61465/problem_61465_img_2.gif"> не имеет решений в рациональных числах.
Рассмотрим равенства:<div align="CENTER"> <table> <tr valign="MIDDLE"><td align="RIGHT">2 + $\displaystyle \sqrt{3}$</td> <td align="CENTER">=</td> <td align="LEFT">$\displaystyle \sqrt{4}$ + $\displaystyle \sqrt{3}$,</td> </tr> <tr valign="MIDDLE"><td align="RIGHT">(2 + $\displaystyle \sqrt{3}$)<sup>2</sup></td> <td align="CENTER">=</td> <td align="LEFT">$\displaystyle \sqrt{49}$ + $\displaystyle \sqrt{48}$,</td> </tr> <tr valign="MIDDLE"><td align="RIGHT">(2 + $\displaystyle \sqrt{3}$)<sup>3</sup></td> <td align="CENTER"...
При возведении числа 1 + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/61463/problem_61463_img_2.gif"> в различные степени, можно обнаружить некоторые закономерности:
(1 + <img width="25" height="38" align="MIDDLE" border="0" src="/storage/problem-media/61463/problem_61463_img_2.gif">)<sup>1</sup> = 1 + <img width="25" height="38" align="MIDDLE" border="0" src="/storage/problem-media/61463/problem_61463_img_2.gif"> = <img width="25" height="38" align="MIDDLE" border="0" src="/storage/problem-media/61463/problem_61463_img_2.g...
Найдите формулу<i>n</i>-го члена для последовательностей, заданных условиями (<i>n</i>$\geqslant$0): <table> <tr><td align="LEFT">a) <i>a</i><sub>0</sub> = 0, <i>a</i><sub>1</sub> = 1, <i>a</i><sub>n + 2</sub> = 5<i>a</i><sub>n + 1</sub> - 6<i>a</i><sub>n</sub>;</td> </tr> <tr><td align="LEFT"> б) <i>a</i><sub>0</sub> = 1, <i>a</i><sub>1</sub> = 1, <i>a</i><sub>n + 2</sub> = 3<i>a</i><sub>n + 1</sub> - 2<i>a</i><sub>n</sub>;</td> </tr> <tr><td align...