Сколько существует пятизначных чисел, в записи которых нет стоящих рядом одинаковых цифр?

Шестизначных чисел от 100 000 до 999 999 существует 900 000. Из них у 90% (810 000) первая и вторая цифры различны. Из этих 810 000 чисел у 90% (т. е. 729 000) различны вторая и третья цифры. Из этих 729 000 чисел у 90% (т. е 656 100) различны третья и четвёртая цифра. И т. д.

Короче, число шестизначных чисел, у которых нет рядом стоящих одинаковых чисел равно:

900 000 • 0.9 • 0.9 • 0.9 • 0.9 • 0.9 = 1 000 000 • (0.9^6) = 9^6 = 531 441.

Аналогично, для n-значного чисел это равно 9^n.

Поскольку числа от 0 до 999 999 включают шестизначные, пятизначные, четырёхзначные и т. д. числа и ноль, то искомое число равно:

S (6) = 9^6 + 9^5 + 9^4 + 9^3 + 9^2 + 9^1 + 9^0

Воспользовавшись формулой для суммы геометрической прогрессии получим

S (6) = (9^7-1) / 8 = 597 871