9
$\begingroup$

I have a very interesting number theory problem. Let $ S_n $ be a number consisting of only $n$ ones. For instance, $S_1=1\\S_2=11 \\ S_4=1111$ The problem is to prove that the sum of the digits of $S^2_n$ can be calculated using the formula $81\cdot \left( \left\lfloor \frac{n}{9} \right\rfloor + \left( \frac{n}{9} - \left\lfloor \frac{n}{9} \right\rfloor \right)^2 \right)$

I would be very grateful for help. I don't even know how to start...

  • 0
    Firstly I have tried grade school multiplication but it was hard with calculations and I thought that this way will not lead me to solve this problem and will only frustrate me.2012-02-25

2 Answers 2

7

A nice problem!

Hints:

  1. Let $n=9q+r$ with $0\le r <9$. Show that the claimed formula gives $ D_n=81q+r^2 $ for the sum of digits $D_n$ of $S_n^2$.
  2. Therefore it suffices to check the formula for $n=1,2,\ldots,9$, and to show that for all $n$ we have the recurrence relation $ D_{n+9}=D_n+81. $
  3. For $n\le9$ verify the formula using the grade school multiplication. Observe that there will be no carry for these small values of $n$.
  4. Verify the identity $ S_{n+9}^2=10^9S_n^2+\frac{10^{2n+18}-10^{2n+9}}{81}-\frac{10^9-1}{81}. $ Here the factor $10^9$ has a predictable effect on the sum of digits, and the remaining task is to check that the two additional terms give the desired contribution. There is some work to be done there, but not an awful lot, if you notice that $ \frac{10^9-1}{81}=12345679. $
  • 0
    It's because of your great hints :-) As I mentioned, I'm not as good as I would like to be and it took me a lot of time, but now I understand very well this problem, everything is clear to me. I can describe solution in a completely precise way. I had a lot of fun while solving it, love this feeling :-)2012-02-25
0

It is also possible to do it by proving that the difference between sum of the digits of $S_{n+1}^2$ and $S_n^2$ equals to $2(n \mod 9) + 1$. I see it is, but I can't prove it formally. Maybe someone would like to fill the gap in my solution :-) and then sum the differences from $S_0^2$ to $S_n^2$