# Sum of digits of repunits

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...

-
@xan: My answer may actually contain too many hints - sorry about that. Before you study it, please try the following: compare e.g. the pairs $S_{14}^2$ vs. $S_5^2$, and $S_{16}^2$ vs. $S_7^2$ with the aid of a computer (or Wolfram Alpha). Generate more such pairs, and... – Jyrki Lahtonen Feb 24 '12 at 19:17
@Jyrki Lahtonen no problem. I'm not as smart as I'd like to be and it's still very difficult for me. Thank you very much for hints, I'm going to study them hard in the near future but I don't exclude the option, I will have to ask about something. Identities in 2 and 4 are definitely not trivial for me. Sorry for my English, I'm still working on it. – xan Feb 24 '12 at 22:26
@xan: My hint #4 is really a translation of the pattern that you see, when you compare, e.g. $S_6^2$ to $S_{15}^2$ and slide the former 9 positions to the left. I was a little bit surprised that you accepted my answer, because I rather suspect that an easier to follow solution is out there :-) One that comes grade school multiplication or something? – Jyrki Lahtonen Feb 25 '12 at 6:00
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. – xan Feb 25 '12 at 13:51

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.$$
-
But another approach may lead to a cleaner solution. First I tried to calculate the total carry... – Jyrki Lahtonen Feb 24 '12 at 18:52
Won't there be an overlap between $10^9 S_n^2$ and the middle term? – Aryabhata Feb 24 '12 at 19:07
@Aryabhata: No. The middle term is divisible by $10^{2n+9}$, and is thus `safely' larger than $10^9S_n^2$. The last term affects the least significant non-zero digit of $10^9S_n^2$, but the effect is easy to analyze. – Jyrki Lahtonen Feb 24 '12 at 19:11
I see. Nice :-) (you have my +1 already, in case you are wondering :-)) – Aryabhata Feb 24 '12 at 19:16
OK, I finally understand the whole structure of this proof. I am very happy, because now the problem seems to be much more fun :-) I have generated over a dozen of $S^2_n$ and I found the relation between $S^2_n$ and $S^2_{n+9}$. I also prooved this: $S^2_{n+9}=10^9 S_n + \frac{10^9-1}{81}(10^{2n+9}-1)$ but still don't know how extract from this the sum of digits relation. It is obvious that sum of digits of $10^9 S_n$ and $S_n$ is equal but despite I know what $\frac{10^9-1}{81}(10^{2n+9}-1)$ do for this number, I don't know how does this affect the sum of digits. – xan Feb 25 '12 at 13:46

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$

-