Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Where did you come across this problem? Please add a homework tag to the question if appropriate. –  Henning Makholm Feb 24 '12 at 17:20
    
added. sorry, this site is compeletly new for me and I don't know how to write here yet –  xan Feb 24 '12 at 18:10
    
@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
show 1 more comment

2 Answers

up vote 3 down vote accepted

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. $$
share|improve this answer
    
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
show 4 more comments

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.