комбинаторика - Про лягушку

Обозначим через $%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$%.