Sums payable with change

[Max Alekseyev]

On Feb 19, 2008 1:01 PM, zak seidov <zakseidov at yahoo.com> wrote:

> In the case of ONE banknote there are 6 payable sums
> (no change as only ONE banknote available):
> 1,5,10,20,50,100.
> Finally with ZERO banknote only one sum is possible,
> namely zero.
> Hence, the beginning of new suggested sequence is:
> a(0)=1, a(1)=6, a(2)=33, a(3)=95.
> Can anyone check/extend this?

Seems to be correct. For a(0..10) I've got:
1, 6, 33, 95, 188, 288, 388, 488, 588, 688, 788, 888, 988, 1088, 1188, 1288

It is easy to see that for n>=4:
a(n) = 100*n - 212
This formula follows from the following theorem.

Theorem. For n>=4 the (positive) payable sums are all numbers from 1
to 100*n, except for the numbers of the form 100*n - m where m belongs
to the set S defined below.

S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 51, 52, 53,
54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
71, 72, 73, 74, 75, 76, 77, 78, 79, 81, 82, 83, 84, 85, 86, 87, 88,
89, 91, 92, 93, 94, 96, 97, 98, 102, 103, 104, 106, 107, 108, 109,
111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 123, 124, 125,
126, 127, 128, 129, 131, 132, 133, 134, 135, 136, 137, 138, 139, 141,
142, 143, 144, 146, 147, 148, 152, 153, 154, 156, 157, 158, 159, 161,
162, 163, 164, 165, 166, 167, 168, 169, 171, 172, 173, 174, 176, 177,
178, 182, 183, 184, 186, 187, 188, 192, 193, 197, 203, 207, 208, 212,
213, 214, 216, 217, 218, 222, 223, 224, 226, 227, 228, 232, 233, 234,
236, 237, 238, 242, 243, 247, 253, 257, 258, 262, 263, 264, 266, 267,
268, 272, 273, 277, 283, 287, 313, 317, 323, 327, 333, 337, 363, 367 }

This theorem can be easily proved by induction on n.

Theorem implies that for n>=4, a(n) = 1 + 100*n - |S| = 100*n - 212.

Regards,
Max



2) 100*(n-


can be proved by induction.