Let denote the sum of the digits (in base ten) of a positive integer . Compute the number of positive integers at most that satisfy
Solution
Note , so there cannot be any carries when adding and . This is equivalent to saying no two consecutive digits of sum to greater than 9 . We change the problem to nonnegative integers less than (as both 0 and satisfy the condition) so that we simply consider 4 -digit numbers, possibly with leading 0 s. Letting our number be , we need , and . Letting and , this means . Summing over all possible values of and , we want The sum over pairs with is The sum over pairs is The final answer is .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.