Докажем это утверждение индукцией по $n$. Условимся, рассматривая не более чем $n$-значные числа, дописывать перед каждым нули так, чтобы все числа стали $n$-значными.
Справедливость утверждения при $n=2$ (тогда $k$ может принимать только одно значение $k=1$) проверить нетрудно:
$$
\def\md{\mathclap{.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.}}
\def\0{\hphantom5}
\begin{array}{|c|c|}
\hline
\text{Числа с нечётной суммой}\vphantom{\dfrac12}&\text{Числа с чётной суммой}\\
\hline\\[-6pt]
\colsep{0pt}{\begin{array}{rrrrrrcrrrrrl}
&01&+&03&+\ldots+&09&{+}\0&10&+&12&+\ldots+&18&+\\
{+}&21&+&23&+\ldots+&29&{+}\0&30&+&32&+\ldots+&38&+\\
&&&&&&\md\\
{+}&81&+&83&+\ldots+&89&{+}\0&90&+&92&+\ldots+&98&{=}\\
{=}5(&00&+&20&+\ldots+&80&){+}5(&10&+&30&+\ldots+&90&)+\\
{+}5(&01&+&03&+\ldots+&09&){+}5(&00&+&02&+\ldots+&08&)
\end{array}}&\colsep{0pt}{\begin{array}{rrrrrrcrrrrrl}
&00&+&02&+\ldots+&08&{+}\0&11&+&13&+\ldots+&19&+\\
{+}&20&+&22&+\ldots+&28&{+}\0&31&+&33&+\ldots+&39&+\\
&&&&&&\md\\
{+}&80&+&82&+\ldots+&89&{+}\0&91&+&93&+\ldots+&99&{=}\\
{=}5(&00&+&20&+\ldots+&80&){+}5(&10&+&30&+\ldots+&90&)+\\
{+}5(&02&+&04&+\ldots+&08&){+}5(&01&+&03&+\ldots+&09&)
\end{array}}\\\\[-6pt]
\hline
\end{array}
$$
Переход от $n$ к $n+1$ ненамного сложнее. Чтобы избежать неясностей и большого числа многоточий, удобно использовать знак суммы $\sum$. Будем обозначать $n$-значные числа с чётной суммой цифр (начиная с $00\ldots00$) буквой $a$, с нечётной суммой цифр (начиная с $00\ldots01$) — буквой $b$. Нетрудно видеть, что каждая из переменных $a$ и $b$ может принимать $5\cdot 10^{n-1}$ различных значений. Пусть, далее, $A$ принимает значения $A=p\cdot 10^n$, где $p$ — одно из чисел 0, 2, 4, 6, 8. $B$ — значение $A=q\cdot 10^n$, где $q$ — одно из чисел 1, З, 5, 7, 9. Мы должны доказать, что при каждом натуральном $k\lt n$
$$
\textstyle\sum{}(A+b)^k+\sum{}(B+a)^k=\sum{}(A+a)^k+\sum{}(B+b)^k\tag{*}
$$
(каждая сумма берётся по всевозможным парам значений букв, стоящих в круглой скобке под знаком $\sum$) при условии, что уже доказано равенство сумм $\sum a^l$ и $\sum b^l$ для всех $l\le n-1$: $\sum a^k=\sum b^k=S_k$. Раскроем в (*) каждую скобку, пользуясь формулой
$$
(X+y)^k=X^k+C_k^1X^{k-1}y+\ldots+C_k^lX^{k-l}y^l+\ldots+y^k,
$$
и проверим, что для каждого отдельного $l$ суммы членов вида $X^{k-l}y^l$ в правой и левой частях равенства равны (коэффициент $C_k^l$ мы не пишем):
$$
\def\vc#1{\colsep{0pt}{\begin{array}{c}\\[-6pt]#1\\[6pt]\end{array}}}
\begin{array}{|c|c|c|}
\hline
&\text{Числа с нечётной суммой цифр}\vphantom{\dfrac12}&\text{Числа с чётной суммой цифр}\\
\hline
\vc{\text{Сумма членов}\\\text{вида}~X^k}&5\cdot10^{n-1}\sum A^k+5\cdot10^{n-1}\sum B^k&5\cdot10^{n-1}\sum A^k+5\cdot10^{n-1}\sum B^k\\
\hline
\vc{\text{Сумма членов}\\\text{вида}~X^{k-l}y^l\\1\le l\le k-1}&\vc{\sum A^{k-l}b^l+\sum B^{k-1}a^l=\\[3pt]=\sum b^l\sum A^{k-1}+\sum a^l\sum B^{k-1}=\\[3pt]=s_l\bigl(\sum A^{k-1}+\sum B^{k-l}\bigr)}&\vc{\sum A^{k-l}a^l+\sum B^{k-1}b^l=\\[3pt]=\sum a^l\sum A^{k-1}+\sum b^l\sum B^{k-1}=\\[3pt]=s_l\bigl(\sum A^{k-1}+\sum B^{k-l}\bigr)}\\
\hline
\vc{\text{Сумма членов}\\\text{вида}~y^k}&5\sum b^k+5\sum a^k&5\sum a^k+5\sum b^k\\
\hline
\end{array}
$$
Заметим, что нашу первоначальную выкладку для $n=2$ с помощью аналогичных обозначений можно записать так:
$$
\begin{gather*}
\textstyle\sum{}(A+b)+\sum{}(B+a)=5\sum A+5\sum b+5\sum B+5\sum a\mathrlap,\\
\textstyle\sum{}(A+a)+\sum{}(B+b)=5\sum A+5\sum a+5\sum B+5\sum b
\end{gather*}
$$
(при $k=1$ остаются только первый и последний члены, соответствующие $l=0$ и $l=k$).
Нетрудно видеть, что утверждение задачи справедливо не только в десятичной, но и в любой другой системе счисления с основанием $d$, где $d$ — чётное число (подумайте, где в нашем решении используется чётность основания $d=10$). Если взять $d=2$, получается такой любопытный ряд равенств:
$$
\colsep{0pt}{\begin{array}{rll}
1+2&{}={}&3\\
1+2+4+7&{}={}&3+5+6\\
1^2+2^2+4^2+7^2&{}={}&3^2+5^2+6^2\\
1+2+4+7+8+11+13+14&{}={}&3+5+6+9+10+12+15\\
1^2+2^2+4^2+7^2+8^2+11^2+13^2+14^2&{}={}&3^2+5^2+6^2+9^2+10^2+12^2+15^2\\
1^3+2^3+4^3+7^3+8^3+11^3+13^3+14^3&{}={}&3^3+5^3+6^3+9^3+10^3+12^3+15^3\\
&\mathclap{.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad}
\end{array}}
$$
