Обозначим (n) как число последовательностей n значений 0,1 и 2, где значение 0 не может быть рядом с другим 0 в последовательности. Например, мы можем иметь (0,1,0,2), но не (0,0,2,1)Строка прямого доказательства n длины
Докажите, что a (n) = 2a (n-1) + 2a (п-2) при п ≥ 3
Вы можете построить любую такую последовательность длиной n (для n>2) однозначно в одном из этих четырех способов:
s(n-1), 1
s(n-1), 2
s(n-2), 1, 0
s(n-2), 2, 0
Где s(n-1) любая такая последовательность длины n-1 и s(n-2) - любая такая последовательность длины n-2.
Или выразить словами; последовательность длиной n (для n>2) может представлять собой любую последовательность длины n-1 с последующей 1 или 2, или любой последовательностью длиной n-2 с последующим 1, 0 или 2, 0.
Если a(n) - число таких последовательностей длины n, это наблюдение сразу же дает a(n) = 2a(n-1) + 2a(n-2) по мере необходимости.
И для полноты, a(1) = 3 и a(2) = 8.
Вы хотите сказать, что a (n) - это число таких последовательностей, а не определенная последовательность? –
Вы уверены? Если a (n) - последовательность, то что означает (n) = 2a (n-1) + 2a (n-2)? –
правильно, вы имели это право, например, (3) - номер такой последовательности длины 3 и 2a (3-1) + 2a (3-2) означает, если мы суммируем двойной номер такой последовательности длины 2 с удвоением числа такой последовательности длины 1 мы получим номер такой последовательности длины 3 – user2420374