Question

Show that any integer n > 12 can be written as a sum 4r + 5s for some nonnegative integers r, s. (This problem is sometimes called a postage stamp problem. It says that any postage greater than 11 cents can be formed using 4 cent and 5 cent stamps.)

Answer 1

Use induction for the prove

Explanation:

Mathemathical induction is an useful method to prove things over natural numbers, you check for the first case, supose for the n and prove using your hypothesis for n+1

there says any integer bigger than 12 can be written as 4r+5s

so first number n can be is 13.

we can check n=13 = 4*2+5*1 r=2 and s=1 give 13.

Now we suppose n can be written as 4r+5s

and we can check if n+1=4r'+5s' with r' and s' integers.

we replace n as 4r+5s because that is our hypotesis

n+1=4r+5s+1

if we write that 1 as 5-4

4r+5s+1

4r+5s+5-4

then we can write

4(r-1)+5(s+1) , we got n+1= 4 (r-1) +5(s+1) where r-1 and s+1 are non negative integers. because r and s were no negative integers ( if r is not 0)

what if r=0?

if r is 0 , n is a multiple of 5 and n+1 can be written as 5s+1

first multiple of 5 we can write is 15 since n is bigger than 12 , then smaller s is 3.

for any n+1 we can write

n+1=5s+1=5 (s-3) +3*5+1=5(s-3)+4*4, s-3 is 0 or bigger.

(check 3*5+1 is 16, the same as 4*4)