Примем известный всем метод математической индукции.
1) Проверим истинность утверждения при n=1, то есть,
P(1) - истинное утверждение.
2) Предположим, что и при n=k выражение
истинно.
Покажем, что тогда имеет место P(k+1), то есть
и, как
, так и
делятся на 3, то и их сумма
делится на 3.
Таким образом, P(k+1) - справедливо утверждение, и, следовательно