22n–1 + 1 = 3(22n–2 – 22n–3 + 22n–4 – ... – 2 + 1) = 3(22n–3 + 22n–5 + ... + 2) + 3, поэтому достаточно доказать, что
22n–3 + 22n–5 + ... + 2 ≡ 3n² – 7n + 2 ≡ 3n² + 2n + 2 (mod 9), или что (22n–3 + 1) + (22n–5 + 1) + ... + (2 + 1) ≡ 3n² + 3n + 3 (mod 9).
Сокращая на 3, получим (22n–4 – 22n–5 + ... + 1) + (22n–6 – 22n–7 + ... + 1) + ... + 1 ≡ n² + n + 1 ≡ (n – 1)² (mod 3).
Заменив в левой части 2 на –1, получим (2n – 3) + (2n – 5) + ... + 1 = (n – 1)².
Пошаговое объяснение:
