Легкая задача про числовой треугольник

[Sonic86]

Пусть задана последовательность $B=(b_1,...,b_n)$ чисел из множества $\{0;1;2\}$. Пусть $a_{n,k}: (\forall n)a_{1,n}=b_n$ и $a_{n+1,k}=|a_{n,k}-a_{n,k+1}|$ - числовой треугольник $T=T(B)$. Треугольник назовем хорошим, если $(\forall n)a_{n,1}\in\{0;1\}$, иначе назовем плохим. Докажите, что число хороших треугольников на единицу больше, чем плохих.

(по мотивам)

http://dxdy.ru/topic55533.html

[Sonic86]

(Оффтоп)

Я опять непонятно написал? Если непонятно - могу пояснить. Или просто неинтересно?

[griboedovaa]

Sonic86 в сообщении #588127 писал(а):

$a_{n+1,k}=|a_{n,k}-a_{n,k+1}|$ - числовой треугольник $T=T(A)$.

(по мотивам)

http://dxdy.ru/topic55533.html

Для чего это условие?

[Sonic86]

griboedovaa в сообщении #588614 писал(а):

Для чего это условие?

Я определил 2-мерную последовательность рекуррентно и обозвал ее треугольником (подчеркнул функциональную зависимость от $A$), чтобы потом можно было говорить о хороших и плохих треугольниках, об их количестве и т.п.

(Оффтоп)

Слово "треугольник" выбрано из очевидных соображений: если мы в $\mathbb{Z}^2$ нарисуем в ячейке $(n,k)$ число $a_{n,k}$, а в других ячейках ничего не напишем, то графически получим нечто похожее на треугольник.
Что такое "по мотивам", наверное, объяснять не надо...

[Dave]

С индексами что-то непонятно. Не с того боку треугольник строится. Да и то, хороший он или плохой, определяется только условием $(\forall n)a_n\in\{0;1\}$.

[Sonic86]

Dave в сообщении #588650 писал(а):

Да и то, хороший он или плохой, определяется только условием $(\forall n)a_n\in\{0;1\}$.

Блин, я индексы перепутал
Заменил в исходном сообщении $a_n$ на $b_n$ и исправил индексы. Понятнее стало?

[Dave]

Sonic86 в сообщении #588737 писал(а):

Заменил в исходном сообщении $a_n$ на $b_n$ и исправил индексы. Понятнее стало?

Значительно понятней

Ясно, что в любом треугольнике присутствуют только числа $0$, $1$ или $2$.
Рассмотрим любой плохой треугольник. Пусть $m=\min \; \{n \mid a_{n,1}=2\}$. Число $2$ могло быть получено только как модуль разности чисел $0$ и $2$. Индукцией по $r$ доказываем, что для любого $r=\overline{0,m-1}$: $a_{m-r,k}=0$ при $k=\overline{1,r}$ и $a_{m-r,r+1}=2$. Для $r=0$ это верно, а если бы при каком-то $r \geqslant 1$ было $a_{m-r,r+1}=0$, то должно было быть $a_{m-r,r}=2$, $a_{m-r,r-1}=2$ и т.д., $a_{m-r,1}=2$, что противоречило бы минимальности $m$.
Таким образом, взяв $r=m-1$, получим, что любой плохой треугольник с соответствующим $m$ начинается с $b_1=b_2=\ldots=b_{m-1}=0$ и $b_m=2$. Очевидно, что верно и обратное. Значит плохих треугольников с таким $m$ ровно $3^{n-m}$, а всего плохих треугольников

$$3^{n-1}+3^{n-2}+\ldots+3^1+1=\frac {3^n-1} {3-1}=\frac {3^n-1} 2,$$

а хороших, стало быть,

$$3^n-\frac {3^n-1} 2=\frac {3^n+1} 2.$$