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