So, I'd like someone to review my 'proof' and pick on it for incompleteness, and state how it could be improved.

The question (reviewing algorithms) asks, "show that in any base b>=2, the sum of any three single-digit numbers is at most two digits long"

Edits based on suggested responses:

For any given base b, and given k digits to work with, we can represent all numbers up to b^k - 1. So with a single digit, we can represent all numbers up to b-1, and with two digits, we can represent all numbers up to (b^2) -1.

It follows that if we have three single digits, then the largest they will ever sum to (b-1 -- is the max number they can each represent) is:

(b-1) + (b-1) + (b - 1) = (3b - 3),

because we are only considering b>=2, the inequality (3b - 3) <= (b^2 -1), meaning (the sum of the three numbers) <= (the largest number that can be represented by 2 numbers), is what is in question. Showing this inequality holds will imply that the sum of these three single digit numbers can always be represented by just two numbers, proving the claim.

This inequality does in fact hold for b>=2 because:

3 <= b + 1 , holds for b>=2


3(b-1) <= (b + 1)(b-1) for b>=2, note: b -1 will be positive

(3b - 3) <= (b^2) - 1 for b>=2

which does in fact show the inequality holds, thus proving the claim made.

Am I missing anything Now?


migrated from stackoverflow.com Oct 9 '15 at 16:22

This question came from our site for professional and enthusiast programmers.

  • 1
    $\begingroup$ You could be more explicit in the "it holds that" step. $\endgroup$ – Beta Oct 4 '15 at 17:09
  • 2
    $\begingroup$ Hint: b^2-1 = (b+1)(b-1) $\endgroup$ – Beta Oct 4 '15 at 17:13
  • $\begingroup$ @Beta, thank you for these comments. $\endgroup$ – Jill Russek Oct 4 '15 at 23:19
  • $\begingroup$ @Beta ,made edits based on your suggestion $\endgroup$ – Jill Russek Oct 5 '15 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy