S(N) denotes the sum of the digits of a base ten positive integer N.

Prove that:

S(2*N) ≤ 2*S(N) ≤ 10*S(2*N)

A property of the sum of the digits function is
S_b(x+y) = S_b(x)+S_b(y)-c*(b-1), where x, y and c are non-negative integers and c is the number of times a carry occurs in the addition of x and y, and where b is the base.

Given the three expressions and the property of the sum of the digits function:
1: S(2n)
    = S(n+n) = S(n) + S(n) - 9c = 2*S(n) - 9c
2: 2*S(n)
3: 10*S(2n)
    = 9*S(2n) + S(2n) = 9*S(2n) + 2*S(n) - 9c
    = 2*S(n) + 18*[S(n) - 5c]

Subtracting 2*S(n) from each expression (1:, 2: and 3:), they become:
1: -9c
2: 0
3: 18*[S(n)-5c]

As c is a non-negative integer, -9c must be less than or equal to 0, thus S(2n) ¡Ü 2*S(n).
Where n ¡Ý 0, S(n) ¡Ý 5c, therefore 0 ¡Ü 18*[S(n)-5c], and
thus 2*S(n) ¡Ü 10*S(2n).
Ergo, S(2n) ¡Ü 2*S(n) ¡Ü 10*S(2n)

Posted by Dej Mar on 2010-01-17 13:09:21