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.)

Use induction for the prove

Step-by-step 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)