лягушка прыгает по вершинам треугольника ABC каждый раз перемещаясь в одну из соседних вершин. начинает она в точке А.сколько способов у лягушки вернуться в А за n прыжков?

задан 8 Июл '13 17:43

10|600 символов нужно символов осталось
2

Обозначим через $%a_n$%, $%b_n$%, $%c_n$% число способов переместиться за $%n$% прыжков в точку $%A$%, $%B$%, $%C$% соответственно, начиная из точки $%A$%. Из соображений симметрии, $%b_n=c_n$%, так как в любом маршруте можно поменять роли $%B$% и $%C$%.

Очевидно, что $%a_{n+1}=b_n+c_n=2b_n$%, так как в точку $%A$% можно прийти или из $%B$%, или из $%C$%. Аналогично, $%b_{n+1}=a_n+c_n=a_n+b_n$% из тех же соображений. Непосредственно ясно, что $%b_0=0$%, $%b_1=1$%, и при этом имеет место рекуррентное соотношение $%b_{n+2}=a_{n+1}+b_{n+1}=b_{n+1}+2b_n$%. Для нахождения формулы общего члена здесь имеются стандартные способы, но их можно избежать следующим образом. Попытаемся найти несколько первых членов последовательности $%b_n$% ($%n\ge0$%), и угадать общую закономерность, которую далее станет можно доказать методом математической индукции.

Последовательность получается такая: $%0,1,1,3,5,11,21,\ldots$%. Здесь каждый следующий член примерно в два раза больше предыдущего, поэтому имеет смысл сравнить нашу последовательность с последовательностью степеней двойки: $%1,2,4,8,16,32,64,\ldots$%. Видно, что у второй последовательности каждый член примерно втрое больше. Поэтому рассмотрим утроенную последовательность $%3b_n$%, члены которой равны $%0,3,3,9,15,33,63,\ldots$%. Сравнивая с последовательностью степеней двойки, мы видим, что она получается из $%3b_n$% прибавлением последовательности $%1,-1,1,-1,\ldots$%, для которой формула общего члена равна $%(-1)^n$% (напомним, что последовательности у нас нумеруются с нулевого члена). Таким образом, для нескольких первых членов последовательности верна формула $%3b_n=2^n-(-1)^n$%, то есть $%b_n=(2^n-(-1)^n)/3$%. Остаётся подставить эти значения в рекуррентную формулу и убедиться в справедливости этого равенства для всех $%n\ge0$%, применяя метод математической индукции.

С учётом того, что $%a_n=2b_{n-1}$% при $%n\ge1$%, имеем окончательный ответ $$a_n=\frac{2^n+2\cdot(-1)^n}3.$$ При $%n=0$% формула также даёт верное значение $%a_0=1$%.

ссылка

отвечен 8 Июл '13 23:19

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×846

задан
8 Июл '13 17:43

показан
2452 раза

обновлен
8 Июл '13 23:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru