Należy pokazać że dowolna liczba naturalna jest podzielna przez 9 wtedy i tylko wtedy gdy suma jej cyfr dzieli się przez 9.
Postanowiłem udowodnić ogólniej że dowolna liczba naturalna przystaje sumie swojej cyfr modulo 9, tj. \(\displaystyle{ \sum_{i=0}^n a_i 10^i = 9k + \sum_{i=0}^n a_i}\), gdzie \(\displaystyle{ \forall n\in \NN \quad a_n < 10}\) i \(\displaystyle{ k \in \NN}\). Indukcyjnie:
Dla \(\displaystyle{ n=0}\) oczywiste. Załóżmy że dla pewnego naturalnego \(\displaystyle{ n}\) zachodzi \(\displaystyle{ \sum_{i=0}^n a_i 10^i = 9k + \sum_{i=0}^n a_i}\). Mamy
\(\displaystyle{ \begin{aligned}
\sum_{i=0}^{n+1} a_i 10^i &= 9k + \sum_{i=0}^n a_i + a_{n+1} 10^{n+1} = \\
&= 9k + \sum_{i=0}^n a_i + a_{n+1} (1+9)^{n+1} = \\
&= 9k + \sum_{i=0}^n a_i + a_{n+1} \sum_{i=0}^{n+1} {n+1 \choose i} 9^i = \\
&= 9k + \sum_{i=0}^n a_i + a_{n+1} (1 + \sum_{i=1}^{n+1} {n+1 \choose i} 9^i) = \\
&= 9k + \sum_{i=0}^n a_i + a_{n+1} + 9l = \\
&= 9(k + l) + \sum_{i=0}^{n+1} a_i
\end{aligned}}\)
gdzie \(\displaystyle{ l \in \NN}\), co kończy dowód.
Poszukałem w internecie przykładowych rozwiązań i takiego nie znalazłem, mimo że pojawiały się również indukcyjne. Nie pomyliłem niczego?
